Papers

1. Proper Usage of the Group Signature Scheme in ISO/IEC 20008-2

Ai Ishida, Yusuke Sakai, Keita Emura, Goichiro Hanaoka, Keisuke Tanaka

AsiaCCS 2019

ISO/IEC 20008-2において複数の匿名デジタル署名が標準化されており、その内、Mechanism 6と呼ばれる方式のみが、付加的な機能のない唯一の「plainな」グループ署名方式となっている。このMechanism 6は、Intel SGXとの組み合わせで多くの応用を持つThe Intel Enhanced Privacy Identification (EPID) 方式においても実利用されている。本論文では、Mechanism 6はグループ署名の標準的な安全性モデルであるBellare-Shi-Zhangモデル [CT-RSA 2005] において匿名性を持たないことを指摘する。さらに本論文では、Mechanism 6の詳細な安全性解析を行い、どのような条件下でならMechanism 6が匿名性を持つかどうかを明らかにする。具体的には、ユーザーの署名鍵を発行する管理者（issuerと呼ばれる）が攻撃に参加しないのであれば匿名性が保たれることを示す。また、この解析から、Mechanism 6へのシンプルなパッチも得られる。

2. Attribute Based Encryption (and more) for Nondeterministic Finite Automata from Learning With Errors

Shweta Agrawal, Monosij Maitra, Shota Yamada

CRYPTO 2019

3. Exploring Constructions of Compact NIZKs from Various Assumptions

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

CRYPTO 2019

• 任意のNP言語に対する非対話ゼロ知識証明で、証明サイズがコンパクト、すなわち|C|+polyとなる方式をペアリング群上のfalsifiableな仮定の下で示した。ここで|C|はNP言語の検証に必要な回路のサイズ、polyはセキュリティパラメータに関する（固定された）多項式である。
• 任意のNP言語に対する検証者指定型非対話ゼロ知識証明で、証明サイズが|C|+polyとなる方式を、ペアリングのない群上でCDH仮定を仮定して示した。
• 任意のNPに対する非対話ゼロ知識証明で、証明作成時間が|C|よりも短い方式を、格子問題の困難性の下で提案した。
前者二つに関しては、格子や識別不可性難読化を利用しない設定では初のコンパクトな証明サイズを持つ方式である。また後者に関しても証明作成時間が|C|に依存しない初の方式である。

4. CCA Security and Trapdoor Functions via Key-Dependent-Message Security

Fuyuki Kitagawa, Takahiro Matsuda, Keisuke Tanaka

CRYPTO 2019

フルバージョン：https://eprint.iacr.org/2019/291

5. Field Extension in Secret-Shared Form and Its Applications to Efficient Secure Computation

Ryo Kikuchi, Nuttapong Attrapadung, Koki Hamada, Dai Ikarashi, Ai Ishida, Takahiro Matsuda, Yusuke Sakai, Jacob C.N. Schuldt

ACISP 2019
Best Paper Award受賞

フルバージョン：https://eprint.iacr.org/2019/386

6. Efficient Estimation of Number of Short Lattice Vectors in Search Space under Randomness Assumption

Yoshitatsu Matsuda, Tadanori Teruya, Kenji Kashiwabara

The 6th ACM ASIA Public-Key Cryptography Workshop (APKC 2019)

7. Equivalence between Non-Malleability against Replayable CCA and Other RCCA-security Notions

Junichiro Hayata, Fuyuki Kitagawa, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura

IWSEC 2019

Replayable CCA（RCCA）安全性とは、Canettiらにより定義された、暗号文の改竄が不可能であることを要求する安全性であるnon-malleabilityについて、平文を改変しない改竄だけは許容するという形で安全性を弱めることを意図して定義された安全性である。Canettiらは、この安全性に関して、IND-RCCA、NM-RCCA、UC-RCCAという3種類の異なる安全性を定義し、暗号方式の平文空間が超多項式サイズのときにそれらの安全性が等価であることを示した。このうちのNM-RCCA安全性は、「平文を改変しない改竄は除いて改竄は不可能」という直観を最も直接に捉えることを意図して定義された安全性であるが、この定義は古典的なnon-malleabilityの自然な拡張になっておらず、そのため、これら定義がその直観を捉えた定義になっているかは明らかではなかった。本研究では、古典的なnon-malleabilityの定義を直接に拡張した「平文を改変しない改竄だけは許容するnon-malleability」の定義を与え、それがCanettiらの定義と等価であることを示した。この等価性は、Canettiらの結果と異なり平文空間が多項式サイズである場合においても成立する。

8. Privacy-Preserving Deep Learning via Weight Transmission

Le Trieu Phong, Tran Thi Phuong

This paper considers the scenario that multiple data owners wish to apply a machine learning method over the combined dataset of all owners to obtain the best possible learning output but do not want to share the local datasets owing to privacy concerns. We design systems for the scenario that the stochastic gradient descent (SGD) algorithm is used as the machine learning method because SGD (or its variants) is at the heart of recent deep learning techniques over neural networks. Our systems differ from existing systems in the following features: (1) any activation function can be used, meaning that no privacy-preserving-friendly approximation is required; (2) gradients computed by SGD are not shared but the weight parameters are shared instead; and (3) robustness against colluding parties even in the extreme case that only one honest party exists. One of our systems requires a shared symmetric key among the data owners (trainers) to ensure the secrecy of the weight parameters against a central server. We prove that our systems, while privacy-preserving, achieve the same learning accuracy as SGD and hence retain the merit of deep learning with respect to accuracy. Finally, we conduct several experiments using benchmark datasets, and show that our systems outperform previous system in terms of learning accuracies.

9. Identity-Based Encryption with Security against the KGC: A Formal Model and Its Instantiation from Lattices

Keita Emura, Shuichi Katsumata, Yohei Watanabe

ESORICS 2019

IDベース暗号の実用化を阻害している大きな問題の1つとして鍵供託問題 (Key Escrow Problem), すなわちIDに対して秘密鍵を生成する鍵生成センタ (Key Generation Center, KGC) が全ての暗号文を復号する能力を有しているという問題が挙げられる. PKC 2009にて, ChowがKGCに対する安全性を定義した. これは暗号文から暗号化に使用されたIDに関する情報が得られないことを仮定したものであるが, 現実的にはKGCは鍵生成を行ったIDのリストを有するため, 妥当な仮定であるとはいえない. Chowはこの理論と現実との隔たりを埋めるため, 新たな機関であるIdentity-Certifying Authority (ICA) を導入し, 匿名鍵発行プロトコルを提案した. これはユーザ, KGC, ICAが相互的にやりとりを行い, 結果KGCにIDを知らせることなく秘密鍵を生成するプロトコルである. 残念ながら, このプロトコルは前出の安全性定義には含まれていないため, Chow (及びその追論文) は鍵供託問題を真に解決したとは言えない. 本論文では, Chowの方法論をベースとし, 鍵供託問題を解決するIDベース暗号の形式的な定義を与える. ぞれぞれユーザ, KGC, ICAが攻撃者の場合を想定した. なおChowは信頼できるICAを仮定しているが, その場合自明に (かつ意味のない) KGCに対して安全なIDベース方式が構成できてしまうことに注意されたい. 本論文では, さらにGentry–Peikert–Vaikuntanathan (GPV) IDベース暗号 (STOC 2008) 及びRuckert ブラインド署名 (ASIACRYPT 2010) を基にした格子ベースの方式を提案する.

10. Group Signatures with Message-Dependent Opening: Formal Definitions and Constructions

Keita Emura, Goichiro Hanaoka, Yutaka Kawai, Takahiro Matsuda, Kazuma Ohara, Kazumasa Omote, Yusuke Sakai

This paper introduces a new capability for group signatures called message-dependent opening. It is intended to weaken the high trust placed on the opener; i.e., no anonymity against the opener is provided by an ordinary group signature scheme. In a group signature scheme with message-dependent opening (GS-MDO), in addition to the opener, we set up an admitter that is not able to extract any user’s identity but admits the opener to open signatures by specifying messages where signatures on the specified messages will be opened by the opener. The opener cannot extract the signer’s identity from any signature whose corresponding message is not specified by the admitter. This paper presents formal definitions of GS-MDO and proposes a generic construction of it from identity-based encryption and adaptive non-interactive zero-knowledge proofs. Moreover, we propose two specific constructions, one in the standard model and one in the random oracle model. Our scheme in the standard model is an instantiation of our generic construction but the message-dependent opening property is bounded. In contrast, our scheme in the random oracle model is not a direct instantiation of our generic construction but is optimized to increase efficiency and achieves the unbounded message-dependent opening property. Furthermore, we also demonstrate that GS-MDO implies identity-based encryption, thus implying that identity-based encryption is essential for designing GS-MDO schemes.

11. MOBIUS: Model-Oblivious Binarized Neural Networks

H. Kitai, J. Cruz, N. Yanai, N. Nishida, T. Oba, Y. Unagami, T. Teruya, N. Attrapadung, T. Matsuda, G. Hanaoka

IEEE ACCESS

A privacy-preserving framework in which a computational resource provider receives encrypted data from a client and returns prediction results without decrypting the data, i.e., oblivious neural network or encrypted prediction, has been studied in machine learning.
In this work, we introduce and explore a new problem called the \textit{model-oblivious problem}, where a trainer can delegate a protected model to a resource provider without revealing the original model itself to the resource provider. The resource provider can then offer prediction on a client’s input data, which is additionally kept private from the resource provider.
To solve this problem, we present \textit{MOBIUS} (Model-Oblivious BInary neUral networkS), a new system that combines \textit{Binarized Neural Networks (BNNs)} and secure computation based on secret sharing as tools for scalable and fast privacy-preserving machine learning.
BNNs improve computational performance by binarizing values in training to $-1$ and $+1$, while secure computation based on secret sharing provides fast and various computations under encrypted forms via modulo operations with a short bit length.
However, combining these tools is not trivial because their operations have different algebraic structures.
MOBIUS uses improved procedures of BNNs and secure computation that have compatible algebraic structures without downgrading prediction accuracy.
We present an implementation of MOBIUS in C++ using the ABY library (NDSS 2015).
Then, we conduct experiments using several datasets, including the MNIST, Cancer, and Diabetes datasets, and the results show that MOBIUS outperforms SecureML (IEEE S\&P 2017),
which is the only other work that can potentially tackle the model-oblivious problem, in terms of both accuracy and computational time.
Compared with TAPAS (ICML 2018) as a state-of-the-art BNN-based system, MOBIUS is \textit{three orders of magnitude faster} without downgrading the accuracy despite solving the model-oblivious problem.

12. Client-Aided Two-party Secure Interval Test Protocol

CANS 2019

Secure interval test protocol checks if an integer is within some interval in a privacy-preserving manner. A natural application is geological location hiding, where we can check whether a person is in a certain territory without revealing any information. In addition, secure interval test protocol enables us to do arithmetic over private values with rounding errors. Therefore, it allows servers to obtain an approximation of a complicated function.
In this work, we present an efficient secure interval test protocol that checks whether a shared value is within the range of two plain values. We also show that the interval test protocol can be used as a building block to construct protocols with richer functionality such as the approximation of exponential functions or logarithmic functions.
Our protocol is constructed in the client-aided model, which is briefly mentioned in some previous work on constructing practical MPC frame- works such as SecureML (S&P’17), in which any number of clients can not only create shares of their inputs but also generate some necessary correlated randomness used in the online phase and distribute them to servers. Such correlated randomness generated by clients serves efficient protocols since servers don’t have to jointly generate randomness by themselves, which can avoid costly computation/communication.
In this paper, we improve the state-of-the-art secure interval test protocol by Nishide and Ohta (PKC’07) based on a secret sharing scheme. We use the client-aided model and tree-based techniques, which contribute to reducing communication rounds. Our proposed protocol has only 4 communication rounds regardless of the bit length of inputs. This is about 3 times fewer rounds than existing protocols. Using the proposed protocol, we further introduce a secure look-up table technique that can be utilized to securely compute some richer functions.

13. A New Combiner for Key Encapsulation Mechanisms

Goichiro HANAOKA,Takahiro Matsuda, Jacob C.N. Schuldt

IEICE Transactions
Volume and Number: Vol.E102-A,No.12,pp.-,Dec. 2019.

Giaconら(PKC 2018)は、Key Encapsulation Combiner (KEM) Combinerという概念を導入した。KEM Combinerは、複数のKEM(および必要ならば他の”軽い”要素技術)を構成要素として一つのKEMを構成するもので、少なくとも一つの構成要素のKEMが安全ならば、構成されたKEMの安全性を保証できる。本研究では、「1回の使用時に関連鍵攻撃に対する安全性を保証できるMAC」と「二つの関連入力の下での出力の疑似ランダム性」を満たすハッシュ関数を用いた、新たなKEM Combinerを提案した。前者の構成要素は、(関連鍵攻撃を考えない)One-time MACのみから構成でき、後者の要素技術は情報理論的に構成できる一方、Giaconらの構成では疑似ランダム関数を用いるため、提案構成は、Giaconらの構成よりも構成要素の実現に必要な要件が弱い。また、GiaconらのKEM Combinerでは、n個のKEMを組み合わせる場合、暗号文作成の際にn回の”全構成要素KEMの暗号文に依存する演算”を行う必要があるが、提案構成では同操作が一回のみでよいため、計算コストも効率的と考えられる。

14. Simulation-based receiver selective opening CCA secure PKE from standard computational assumptions

Keisuke Hara, Fuyuki Kitagawa, Takahiro Matsuda, Goichiro Hanaoka, Keisuke Tanaka

15. Simple and Efficient KDM-CCA Secure Public Key Encryption

Fuyuki Kitagawa, Takahiro Matsuda, Keisuke Tanaka

ASIACRYPT 2019

16. CPA-to-CCA Transformation for KDM Security

Fuyuki Kitagawa, Takahiro Matsuda

TCC 2019

17. Practical Public-Key Encryption Scheme Tightly Secure in the Random Oracle Model

Yusuke SAKAI, Goichiro HANAOKA

18. Attribute Based Encryption for Deterministic FiniteAutomata fromDLIN

Shweta Agrawal, Monosij Maitra, Shota Yamada

TCC 2019

19. Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications

Hiraku Morita, Nuttapong Attrapadung, Tadanori Teruya, Satsuya Ohata, Koji Nuida, Goichiro Hanaoka

IEICE Transactions, Vol.E103-A,No.01,pp.-,Jan. 2020.

提案プロトコルはC++を用いて実装し，通信遅延の大きいWANのような設定では今回の低ラウンド構成に理があることを示した．

20. Communication-Efficient (Client-Aided) Secure Two-Party Protocols and Its Application

Satsuya Ohata, Koji Nuida

FC’ 20.

21. Generic Construction of Adaptively Secure Anonymous Key-Policy Attribute-Based Encryption from Public-Key Searchable Encryption

Junichiro Hayata, Masahito Ishizaka, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura

22. Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512

Ali El Kaafarani, Shuichi Katsumata, Federico Pintore

PKC 2020

23. Non-Interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions

Geoffroy Couteau, Shuichi Katsumata, Bogdan Ursu

EUROCRYPT 2020

24. Compact NIZKs from Standard Assumptions on Bilinear Maps

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

EUROCRYPT 2020

これは、同じ著者のEUROCRYPT 2019とCRYPTO 2019の結果を拡張した結果である。一連の研究は、bilinear mapをベースにしたNIZK for NPの証明サイズを標準的な仮定からどこまで小さくできるかを一つの焦点としていた。現状、bilinear map上のもっとも標準的な仮定の一つであるDLIN仮定から証明サイズが|C| + poly(\secpar)の方式は未解決問題として残されていた。ただし、ここでCはNP言語を計算する回路を表す。参考に、同仮定から知られているNIZKはGroth-Sahai-NIZKで、証明サイズは|C| x poly(\secpar)である。

EUROCRYPT 2020

26. Exposing Private User Behaviors of Collaborative Filtering via Model Inversion Techniques

Seira Hidano, Takao Murakami, Shuichi Katsumata, Shinsaku Kiyomoto, Goichiro Hanaoka

PoPETS/PETS 2020

27. Lattice-based revocable (Hierarchical) IBE with decryption key exposure resistance

Shuichi Katsumata, Takahiro Matsuda, Atsushi Takayasu

PKC2019

ID ベース暗号を効果的に実利用するために，悪意のあるユーザーをシステムから除外する鍵失効機 能は必須要件である.Boldyreva ら (ACM CCS’08) は，鍵失効機能を持つ ID ベース暗号 (RIBE) を初め て提案した.さらに，Seo と Emura (PKC’13) は，現実的に起こりうる人為的過失を考慮に入れ，復号鍵 漏洩耐性 (DKER) を持つ RIBE 方式を初めて提案した.Seo と Emura の構成では，DKER を達成するた めには RIBE の秘密鍵がリランダマイズ可能であることが本質的であり，これに倣い，ペアリングを用い てこれまで数多くの方式が提案されてきた.だが，格子に基づく RIBE では，秘密鍵をリランダマイズす ることが困難であるため，DKER を持つ格子 RIBE がこれまで提案されていない.本稿で我々は，DKER を持つ RIBE の一般的な構成法を示す.より正確には，DKER を持つ RIBE は，DKER を持たない RIBE と 2 階層の階層型 IBE (HIBE) を組み合わせることで，一般的に構成できることを示す.提案構成法は， 一般的構成であること・従来のように RIBE に秘密鍵リランダマイズを要求しないという意味で理論的に 興味深い結果である.また，この構成によって初めて得られる DKER を持つ格子 RIBE は，DKER を持 たない方式とほぼ同等の効率であるという点で，実用的にも意義深い結果である.

28. Adaptively Secure Constrained Pseudorandom Functions in the Standard Model

Alex Davidson, Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

CRYPTO 2020

29. Enhanced Secure Comparison Schemes Using Homomorphic Encryption

Lihua Wang, Tushar Kanti Saha, Yoshinori Aono, Takeshi Koshiba, Shiho Moriai

NBiS2020

Sahaと小柴は[NBiS2017]で、Ring-LWEベース実用的なセキュアな大小比較アプローチ-SK17-を提案している。これは、2つのクライアント(一方は復号鍵を持つ)がデータを公開せずに外部のクラウドサーバを介してデータを比較する3者間計算モデルの下で確立されたものである。本研究では、効率性、安全性、柔軟性を向上させるために、SK17を改良した3つの方式を提案する。Protocol-1はSK17と同じく3者間の計算モデルに基づくものである。両者を実装し、Lauterらが提案しているRing-LWEベース暗号化方式を用いてProtocol-1の効率性を示す。Protocol-2はOne-roundで大小比較を行うことで、Protocol-1と比べより大きいパラメータ選択が必要であるが、より安全的な方式である。Protocol-3はProtocol-2から変形し、2者間大小比較に適用可能。この2つのプロトコルについては理論的なセキュリティ解析と実用性評価を行う。

Keita Emura

31. Privacy-Preserving Data Analysis: Providing Traceability without Big Brother

Hiromi Arai, Keita Emura,  Takuya Hayashi

データ収集時に提供者を匿名とすることで提供者のプライバシーが保護される一方で, データが異常値である場合に提供者を特定する必要がある. グループ署名を用いることで匿名性と追跡性を両立することが可能ではあるが、追跡者はデータが異常値であるなしに関わらず提供者を特定できてしまう。本論文では、このBig brotherを排除したプライバシー保護異常検知方式を提案する. メッセージ依存開示グループ署名 (GS-MDO) を用いることで, 異常データを提出した提供者のみを特定し, それ以外の提供者は依然匿名のままとなる. 一般的構成を与えるとともに, 大原らのGS-MDO (with 阿部-星野-大久保変換) を使用した場合のUCI-Pimaデータを用いた実装評価を与える.

32. Adaptively Secure Inner Product Encryption from LWE

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

ASIACRYPT 2020

33. Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices

Ward Beullens, Shuichi Katsumata, Federico Pintore

ASIACRYPT 2020

34. Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications

Shuichi Katsumata, Kris Kwiatkowski, Federico Pintore, Thomas Prest.

ASIACRYPT 2020

35. Circular Security Is Complete for KDM Security

Fuyuki Kitagawa, Takahiro Matsuda

ASIACRYPT 2020

36. Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

ASIACRYPT 2020

At Eurocrypt’19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner (including those that resolved some open problems at the time). However, his approach heavily relies on so-called q-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem.In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung.Our framework significantly expands areas of ABEs that are realizable from standard assumptions. These include the following adaptively secure large-universe ABEs for Boolean formulae under MDDH.- The first completely unbounded monotone key-policy (KP)/ciphertext-policy (CP) ABE. Previously, such ABE has been only recently proposed, but only for the KP and small-universe flavor (Kowalczyk and Wee, Eurocrypt’19).

– The first completely unbounded non-monotone KP/CP-ABE. Especially, our ABEs support a new type of non-monotonicity that subsumes previous two types of non-monotonicity, namely, by Ostrovsky et al. (CCS’07) and by Okamoto and Takashima (CRYPTO’10).

– The first non-monotone KP and CP-ABE with constant-size ciphertexts and secret keys, respectively.- The first monotone KP and CP-ABE with constant-size secret keys and ciphertexts, respectively.At the core of our framework lies a new \emph{partially symmetric} design of the core 1-key/1-ciphertext oracle component called Key Encoding Indistinguishability, which exploits the symmetry so as to obtain compositions.

37. Semantic Definition of Anonymity in Identity-Based Encryption and Its Relation to Indistinguishability-Based Definition

Goichiro Hanaoka, Misaki Komatsu, Kazuma Ohara, Yusuke Sakai, Shota Yamada

ESORICS 2020

38. Equivalence between Non-Malleability against Replayable CCA and Other RCCA-Security Notions

Junichiro HAYATA, Fuyuki KITAGAWA, Yusuke SAKAI, Goichiro HANAOKA, Kanta MATSUURA

Replayable CCA（RCCA）安全性は、Canettiらにより定義された、平文を変更しない暗号文の改ざんのみは許容するnon-malleabilityを持つ暗号化方式を取り扱うことを意図した安全性である。RCCA安全性はCCA安全性を緩めることで定義されており、認証や鍵交換には十分な強さであることが知られている。Canettiらは、RCCA攻撃に対するnon-malleabiltiy（NM-RCCA）、RCCA攻撃に対する識別不可能性（IND-RCCA）、RCCA攻撃に対する汎用結合可能性（UC-RCCA）を定義し、それらが（平文空間が超多項式的に大きい）公開鍵暗号方式について同値であることを示した。これら定義の中で、NM-RCCA安全性は、RCCA安全性の「平文を変更しない暗号文の改ざんのみは許容するnon-malleability」を取り扱いたいという動機に照らし合わせて重要な役割を持つ。しかしながら、CanettiらのNM-RCCA安全性は、従来のnon-malleabilityの自然な拡張になっておらず、このNM-RCCA安全性がnon-malleabilityといったときに直観的に期待する安全性を確かに捉えているかどうはは不確かである。本論文では、識別不可能性およびシミュレーションに基づくRCCA攻撃に対するnon-malleabilityを従来のnon-malleabilityの自然な拡張として定義し、それらが（平文空間の大きさによらず）IND-RCCAと同値であることを示す。

39. Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers

Kaoru Takemure, Yusuke Sakai, Bagus Santoso, Goichiro Hanaoka, Kazuo Ohta

Provsec 2020

40. NIZK from SNARG

Fuyuki Kitagawa, Takahiro Matsuda, Takashi Yamakawa

TCC 2020

TCC 2020

42. ” Optimal Broadcast Encryption from LWE and Pairings in the Standard Model”

Shweta Agrawal; Daniel Wichs; Shota Yamada

TCC 2020

44. Distributed SignSGD with Improved Accuracy and Network-Fault Tolerance

Le Trieu Phong, Tran Thi Phuong

IEEE Access

45. New Approaches to Federated XGBoost Learning for Privacy-Preserving Data Analysis

Fuki Yamamoto, Lihua Wang, and Seiichi Ozawa

ICONIP2020

46. Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers

Kaoru Takemure, Yusuke Sakai, Bagus Santoso, Goichiro Hanaoka, Kazuo Ohta

47. Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model.

Shuichi Katsumata, Shota Yamada, Takashi Yamakawa.

ASIACRYPT2018のfull versionです。格子ベース暗号を代表するGentry-Peikert-VaikuntanathanのIDベース暗号の方式を何も変えず、量子ランダムオラクルにおいて緊密な帰着を与えた論文です。会議版との差分は、通常の格子よりも効率性が高い、構造を持った格子（ring lattice）を使った際のIDベース方式に関する考察を載せたことです。

48. Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions.

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa.

EUROCRYPT 2021

ブラインド署名は、署名者がメッセージを知らずに、メッセージに対して署名を与えられる暗号学的道具である。ブラインド署名は、メッセージを署名してもらいたい人（受信者）が署名者に情報を送り、署名者が署名を受信者に返す必要があるため、理論的に2-roundが最適である。このようなブラインド署名をround optimalと呼ぶ。現在、round optimalなブラインド署名を構成するには、信頼できる第三者を設けたり、強い（quasi-polynomial hardness）仮定等を要する。本論文では、初めて、標準的な（polynomial hardness）仮定に基づくround optimalなブラインド署名を構成した。

49. An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable.

Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, Thomas Prest.

PKC 2021

Signalアプリは、現在世界的に利用されているセキュア・メッセージング・アプリ（SMI）である。Signalアプリの内部で実行されているSignalプロトコルは、X3DHと呼ばれる初期非対話型鍵共有プロトコルと、Double Ratchetと呼ばれる継続的な非対話型鍵共有プロトコルからなる。既存研究では、Double Ratchetに関する研究は盛んに行われ、現在我々のDouble Ratchetに対する理解はだいぶ深まっている。例えば、耐量子安全なDouble Ratchetの一般的構成が知られている。しかし、一方で、X3DHは現在未だにDiffie-Hellman仮定による構成しか知られていない。

50. Revisiting Fuzzy Signatures: Towards a More Risk-Free Cryptographic Authentication System based on Biometrics.

Shuichi Katsumata,  Takahiro Matsuda, Wataru Nakamura, Kazuma Ohara, Kenta Takahashi.

ACM CCS 2021

ファジー署名は、生体認証のみで署名を打つことができる電子署名の亜種である。ユーザーは、署名を打つ際に自分の生体以外を必要としないため、パスワード漏洩の心配もなく、応用は非常に幅広い。しかしながら、現在ファジー署名に関する研究は限られており、応用よりのテーマであるにも関わらず、現在知られている研究は全て理論面に重きを置いている。例えば、実際どの程度の生体情報があれば、112-bit安全性が担保できるか？等の根源的な問いに対する答えはない。

51. Receiver Selective Opening Chosen Ciphertext Secure Identity-based Encryption

Keisuke Hara, Takahiro Matsuda, Keisuke Tanaka.

APKC 2021

IDベース暗号(IBE)における受信者選択的開示攻撃に対する安全性(Security against Receiver Selective Opening Attack, RSO Security)は、一人の送信者が多数の異なるID(=受信者)に対して暗号文を送信した後に、一部の受信者の秘密鍵が漏洩する状況における、秘密鍵が漏洩していない受信者に充てた暗号化メッセージの秘匿性を保証できる安全性である。本論文では、IBEの選択暗号文攻撃下でのRSO安全性(RSO-CCA安全性)を定式化し、同安全性を満たす初の方式を提案する。より詳細には、IND-ID-CPA安全なIBEと非対話型ゼロ知識証明(NIZK)を構成要素とする、RSO-CCA安全なIBEの一般的な構成を示す。さらにその一般的構成の構成要素を具体的な数論的設定・仮定に基づく方式で具現化することで、双線形写像に基づく方式や、格子に基づくRSO-CCA安全なIBEの初の方式が得られる。

52. Recent Advances in Practical Secure Multi-Party Computation

Satsuya Ohata

Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. MPC has been actively studied, and there are many research results both in the theoretical and practical research fields. In this paper, we introduce the basic matters on MPC and show recent practical advances. We first explain the settings, security notions, and cryptographic building blocks of MPC. Then, we show and discuss current situations on higher-level secure protocols, privacy-preserving data analysis, and frameworks/compilers for implementing MPC applications with low-cost.

53. Efficiency and Accuracy Improvements of Secure Floating-Point Addition over Secret Sharing

Kota Sasaki and Koji Nuida

IWSEC 2020
Best Paper Award受賞 Best Student Paper Award受賞

In secure multiparty computation (MPC), floating-point numbers should be handled in many potential applications, but these are basically expensive. In particular, for MPC based on secret sharing (SS), the floating-point addition takes many communication rounds though the addition is the most fundamental operation. In this paper, we propose an SS-based two-party protocol for floating-point addition with 13 rounds (for single/double precision numbers), which is much fewer than the milestone work of Aliasgari et al. in NDSS 2013 (34 and 36 rounds, respectively) and also fewer than the state of the art in the literature. Moreover, in contrast to the existing SS-based protocols which are all based on “roundTowardZero” rounding mode in the IEEE 754 standard, we propose another protocol with 15 rounds which is the first result realizing more accurate “roundTiesToEven” rounding mode. We also discuss possible applications of the latter protocol to secure Validated Numerics (a.k.a. Rigorous Computation) by implementing a simple example.

54. RintC: fast and accuracy-aware decomposition of distributions of RNA secondary structures with extended logsumexp

Hiroki Takizawa, Junichi Iwakiri, and Kiyoshi Asai

(quoted from the abstract of the paper, which is licenced under the CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/ ) Analysis of secondary structures is essential for understanding the functions of RNAs. Because RNA molecules thermally fluctuate, it is necessary to analyze the probability distributions of their secondary structures. Existing methods, however, are not applicable to long RNAs owing to their high computational complexity. Additionally, previous research has suffered from two numerical difficulties: overflow and significant numerical errors. In this research, we reduced the computational complexity of calculating the landscape of the probability distribution of secondary structures by introducing a maximum-span constraint. In addition, we resolved numerical computation problems through two techniques: extended logsumexp and accuracy-guaranteed numerical computation. We analyzed the stability of the secondary structures of 16S ribosomal RNAs at various temperatures without overflow. The results obtained are consistent with previous research on thermophilic bacteria, suggesting that our method is applicable in thermal stability analysis. Furthermore, we quantitatively assessed numerical stability using our method. These results demonstrate that the proposed method is applicable to long RNAs.

55. Finding the direct optimal RNA barrier energy and improving pathways with an arbitrary energy model

Hiroki Takizawa, Junichi Iwakiri, Goro Terai, and Kiyoshi Asai

Bioinformatics

(quoted from the abstract of the paper, which is licenced under the CC-BY-NC 4.0. https://creativecommons.org/licenses/by-nc/4.0/ ) RNA folding kinetics plays an important role in the biological functions of RNA molecules. An important goal in the investigation of the kinetic behavior of RNAs is to find the folding pathway with the lowest energy barrier. For this purpose, most of the existing methods use heuristics because the number of possible pathways is huge even if only the shortest (direct) folding pathways are considered. In this study, we propose a new method using a best-first search strategy to efficiently compute the exact solution of the minimum barrier energy of direct pathways. Using our method, we can find the exact direct pathways within a Hamming distance of 20, whereas the previous methods even miss the exact short pathways. Moreover, our method can be used to improve the pathways found by existing methods for exploring indirect pathways.

56. Non-zero Inner Product Encryption Schemes from Various Assumptions: LWE, DDH and DCR

PKC 2019

In non-zero inner product encryption (NIPE) schemes, ciphertexts and secret keys are associated with vectors and decryption is possible whenever the inner product of these vectors does not equal zero. So far, much effort on constructing bilinear map-based NIPE schemes have been made and this has lead to many efficient schemes. However, the constructions of NIPE schemes without bilinear maps are much less investigated. The only known other NIPE constructions are based on lattices, however, they are all highly inefficient due to the need of converting inner product operations into circuits or branching programs.

To remedy our rather poor understanding regarding NIPE schemes without bilinear maps, we provide two methods for constructing NIPE schemes: a direct construction from lattices and a generic construction from schemes for inner products (LinFE). For our first direct construction, it highly departs from the traditional lattice-based constructions and we rely heavily on new tools concerning Gaussian measures over multi-dimensional lattices to prove security. For our second generic construction, using the recent constructions of LinFE schemes as building blocks, we obtain the first NIPE constructions based on the DDH and DCR assumptions. In particular, we obtain the first NIPE schemes without bilinear maps or lattices.

57. Adaptively Single-Key Secure Constrained PRFs for $$\mathrm {NC}^1$$

PKC 2019

We present a construction of an adaptively single-key secure constrained PRF (CPRF) for NC1NC1 assuming the existence of indistinguishability obfuscation (IO) and the subgroup hiding assumption over a (pairing-free) composite order group. This is the first construction of such a CPRF in the standard model without relying on a complexity leveraging argument.

To achieve this, we first introduce the notion of partitionable CPRF, which is a CPRF accommodated with partitioning techniques and combine it with shadow copy techniques often used in the dual system encryption methodology. We present a construction of partitionable CPRF for NC1NC1 based on IO and the subgroup hiding assumption over a (pairing-free) group. We finally prove that an adaptively single-key secure CPRF for NC1NC1 can be obtained from a partitionable CPRF for NC1NC1 and IO.

58. Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions

EUROCRYPT 2019

In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. Thus far, numerous constructions of NIZKs have been provided in the common reference string (CRS) model (CRS-NIZK) from various assumptions, however, it still remains a long standing open problem to construct them from tools such as pairing-free groups or lattices. Recently, Kim and Wu (CRYPTO’18) made great progress regarding this problem and constructed the first lattice-based NIZK in a relaxed model called NIZKs in the preprocessing model (PP-NIZKs). In this model, there is a trusted statement-independent preprocessing phase where secret information are generated for the prover and verifier. Depending on whether those secret information can be made public, PP-NIZK captures CRS-NIZK, designated-verifier NIZK (DV-NIZK), and designated-prover NIZK (DP-NIZK) as special cases. It was left as an open problem by Kim and Wu whether we can construct such NIZKs from weak paring-free group assumptions such as DDH. As a further matter, all constructions of NIZKs from Diffie-Hellman (DH) type assumptions (regardless of whether it is over a paring-free or paring group) require the proof size to have a multiplicative-overhead |C|⋅poly(κ)|C|⋅poly(κ), where |C| is the size of the circuit that computes the NPNP relation.In this work, we make progress of constructing (DV, DP, PP)-NIZKs with varying flavors from DH-type assumptions. Our results are summarized as follows:

• DV-NIZKs for NPNP from the CDH assumption over pairing-free groups. This is the first construction of such NIZKs on pairing-free groups and resolves the open problem posed by Kim and Wu (CRYPTO’18).
• DP-NIZKs for NPNP with short proof size from a DH-type assumption over pairing groups. Here, the proof size has an additive-overhead |C|+poly(κ)|C|+poly(κ) rather then an multiplicative-overhead |C|⋅poly(κ)|C|⋅poly(κ). This is the first construction of such NIZKs (including CRS-NIZKs) that does not rely on the LWE assumption, fully-homomorphic encryption, indistinguishability obfuscation, or non-falsifiable assumptions.
• PP-NIZK for NPNP with short proof size from the DDH assumption over pairing-free groups. This is the first PP-NIZK that achieves a short proof size from a weak and static DH-type assumption such as DDH. Similarly to the above DP-NIZK, the proof size is |C|+poly(κ)|C|+poly(κ). This too serves as a solution to the open problem posed by Kim and Wu (CRYPTO’18).

Along the way, we construct two new homomorphic authentication (HomAuth) schemes which may be of independent interest.

59. Group Signatures Without NIZK: From Lattices in the Standard Model

EUROCRYPT 2019

In a group signature scheme, users can anonymously sign messages on behalf of the group they belong to, yet it is possible to trace the signer when needed. Since the first proposal of lattice-based group signatures in the random oracle model by Gordon, Katz, and Vaikuntanathan (ASIACRYPT 2010), the realization of them in the standard model from lattices has attracted much research interest, however, it has remained unsolved. In this paper, we make progress on this problem by giving the first such construction. Our schemes satisfy CCA-selfless anonymity and full traceability, which are the standard security requirements for group signatures proposed by Bellare, Micciancio, and Warinschi (EUROCRYPT 2003) with a slight relaxation in the anonymity requirement suggested by Camenisch and Groth (SCN 2004). We emphasize that even with this relaxed anonymity requirement, all previous group signature constructions rely on random oracles or NIZKs, where currently NIZKs are not known to be implied from lattice-based assumptions. We propose two constructions that provide tradeoffs regarding the security assumption and efficiency:

• Our first construction is proven secure assuming the standard LWE and the SIS assumption. The sizes of the public parameters and the signatures grow linearly in the number of users in the system.
• Our second construction is proven secure assuming the standard LWE and the subexponential hardness of the SIS problem. The sizes of the public parameters and the signatures are independent of the number of users in the system.

Technically, we obtain the above schemes by combining a secret key encryption scheme with additional properties and a special type of attribute-based signature (ABS) scheme, thus bypassing the utilization of NIZKs. More specifically, we introduce the notion of indexed ABS, which is a relaxation of standard ABS. The above two schemes are obtained by instantiating the indexed ABS with different constructions. One is a direct construction we propose and the other is based on previous work.

60. A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions

Nuttapong ATTRAPADUNG,Goichiro HANAOKA,Shinsaku KIYOMOTO,Tomoaki MIMOTO,Jacob C. N. SCHULDT

Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols. We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.

61. Shortening the Libert-Peters-Yung Revocable Group Signature Scheme by Using the Random Oracle Methodology

Kazuma OHARA,Keita EMURA,Goichiro HANAOKA,Ai ISHIDA,Kazuo OHTA,Yusuke SAKAI

At EUROCRYPT 2012, Libert, Peters and Yung (LPY) proposed the first scalable revocable group signature (R-GS) scheme in the standard model which achieves constant signing/verification costs and other costs regarding signers are at most logarithmic in N, where N is the maximum number of group members. However, although the LPY R-GS scheme is asymptotically quite efficient, this scheme is not sufficiently efficient in practice. For example, the signature size of the LPY scheme is roughly 10 times larger than that of an RSA signature (for 160-bit security). In this paper, we propose a compact R-GS scheme secure in the random oracle model that is efficient not only in the asymptotic sense but also in practical parameter settings. We achieve the same efficiency as the LPY scheme in an asymptotic sense, and the signature size is nearly equal to that of an RSA signature (for 160-bit security). It is particularly worth noting that our R-GS scheme has the smallest signature size compared to those of previous R-GS schemes which enable constant signing/verification costs. Our technique, which we call parallel Boneh-Boyen-Shacham group signature technique, helps to construct an R-GS scheme without following the technique used in LPY, i.e., we directly apply the Naor-Naor-Lotspiech framework without using any identity-based encryption.

62. A Fast Privacy-Preserving Multi-Layer Perceptron Using Ring-LWE-Based Homomorphic Encryption

Takehiro Tezuka, Lihua Wang, Takuya Hayashi, Seiichi Ozawa

ICDMW2019

Concerns about leaking privacy from data have been preventing from making good use of so-called big data, while privacy-preserving data analysis would still be a promising research direction. In this paper, we propose Privacy-Preserving Multi-Layer Perceptron (PP-MLP) that can compute the prediction real-time using Ring-LWE-based homomorphic encryption. We implement the proposed PP-MLP in the form of a two-party model consisting of client and server. The former encrypts input data and receives a classification result from a server, and the latter performs prediction over encrypted data. This scheme enables a client to acquire prediction without revealing actual data contents against a server. The proposed PP-MLP can make a fast prediction that requires up to 80 msec per input without a significant drop in classification accuracy compared to the convention multi-layer perceptron for plaintexts.

63. Exploring and Identifying Malicious Sites in Dark Web Using Machine Learning

Yuki Kawaguchi and Seiichi Ozawa

ICONIP 2019

In recent years, various web-based attacks such as Drive-by-Download attacks are becoming serious. To protect legitimate users, it is important to collect information on malicious sites that could provide a blacklist-based detection software. In our study, we propose a system to collect URLs of malicious sites in the dark web. The proposed system automatically crawls dark web sites and collects malicious URLs that are judged by using VirusTotal and the Gred engine. We also predict dangerous categories of collected web sites that are potentially malicious using a document embedding with a gradient boosting decision tree model. In the experiments, we demonstrate that the proposed system can predict dangerous site categories with 0.82 accuracy in F1-score.

64. Lattice-based revocable (hierarchical) IBE with decryption key exposure resistance

Shuichi Katsumata,Takahiro Matsuda,Atsushi Takayasu

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism, which is an indispensable feature for practical cryptographic schemes. Due to this extra feature, RIBE is often required to satisfy a strong security notion unique to the revocation setting called decryption key exposure resistance (DKER). Additionally, hierarchal IBE (HIBE) is another orthogonal extension of IBE that supports key delegation functionalities allowing for scalable deployments of cryptographic schemes. So far, R(H)IBE constructions with DKER are only known from bilinear maps, where all constructions rely heavily on the so-called key re-randomization property to achieve the DKER and/or hierarchal feature. Since lattice-based schemes seem to be inherently ill-fit with the key re-randomization property, no construction of lattice-based R(H)IBE schemes with DKER are known.

In this paper, we propose the first lattice-based RHIBE scheme with DKER without relying on the key re-randomization property, departing from all the previously known methods. We start our work by providing a generic construction of RIBE schemes with DKER, which uses as building blocks any two-level standard HIBE scheme and (weak) RIBE scheme without DKER. Based on previous lattice-based RIBE constructions without DKER, our result implies the first lattice-based RIBE scheme with DKER. Then, building on top of our generic construction, we construct the first lattice-based RHIBE scheme with DKER, by further exploiting the algebraic structure of lattices. To this end, we prepare a new tool called the level conversion keys, which enables us to achieve the hierarchal feature without relying on the key re-randomization property. In this full version, we give the formal proofs of our proposed schemes.

65. Simple Black-box Adversarial Examples Generation with Very Few Queries

Yuya Senzaki, Satsuya Ohata, Kanta Matsuura

Research on adversarial examples for machine learning has received much attention in recent years. Most of previous approaches are white-box attacks; this means the attacker needs to obtain before-hand internal parameters of a target classifier to generate adversarial examples for it. This condition is hard to satisfy in practice. There is also research on black-box attacks, in which the attacker can only obtain partial information about target classifiers; however, it seems we can prevent these attacks, since they need to issue many suspicious queries to the target classifier. In this paper, we show that a naive defense strategy based on surveillance of number query will not suffice. More concretely, we propose to generate not pixel-wise but block-wise adversarial perturbations to reduce the number of queries. Our experiments show that such rough perturbations can confuse the target classifier. We succeed in reducing the number of queries to generate adversarial examples in most cases. Our simple method is an untargeted attack and may have low success rates compared to previous results of other black-box attacks, but needs in average fewer queries. Surprisingly, the minimum number of queries (one and three in MNIST and CIFAR-10 dataset, respectively) is enough to generate adversarial examples in some cases. Moreover, based on these results, we propose a detailed classification for black-box attackers and discuss countermeasures against the above attacks.

66. Generic hardness of inversion on ring and its relation to self-bilinear map

Takashi Yamakawa, Shota Yamada, Goichiro Hanaoka, and Noboru Kunihiro

In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime c by just using additions, subtractions and multiplications on the ring. If the characteristic of an underlying ring is public and coprime to c, then it is easy to compute the inverse of c by using the extended Euclidean algorithm. On the other hand, if the characteristic is hidden, it seems difficult to compute it. For discussing the generic hardness of the inversion problem, we first extend existing generic ring models to capture a ring of an unknown characteristic. Then we prove that there is no generic algorithm to solve the inversion problem in our model when the underlying ring is isomorphic to Zp for a randomly chosen prime p assuming the hardness of factorization of an unbalanced modulus. We also study a relation between the inversion problem on a ring and a self-bilinear map. Namely, we give a construction of a self-bilinear map based on a ring on which the inversion problem is hard, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t. the resulting sef-bilinear map.

67. An Efficient Secure Division Protocol Using Approximate Multi-Bit Product and New Constant-Round Building Blocks

Keitaro Hiwatashi, Satsuya Ohata and Koji Nuida

ACNS 2020

Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.

68. On Private Information Retrieval Supporting Range Queries

Junichiro Hayata, Jacob C. N. Schuldt, Goichiro Hanaoka, and Kanta Matsuura

ESORICS 2020

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data is being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries, is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing – while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. Finally, we report on the practical performance of our direct construction.

69. Efficient Secure Neural Network Prediction Protocol Reducing Accuracy Degradation

Naohisa Nishida, Tatsumi Oba, Yuji Unagami, Jason Paul Cruz, Naoto Yanai, Tadanori Teruya, Nuttapong Attrapadung, Takahiro Matsuda, and Goichiro Hanaoka

Machine learning models inherently memorize significant amounts of information, and thus hiding not only prediction processes but also trained models, i.e., model obliviousness, is desirable in the cloud setting. Several works achieved model obliviousness with the MNIST dataset, but datasets that include complicated samples, e.g., CIFAR-10 and CIFAR-100, are also used in actual applications, such as face recognition. Secret sharing-based secure prediction for CIFAR-10 is difficult to achieve. When a deep layer architecture such as CNN is used, the calculation error when performing secret calculation becomes large and the accuracy deteriorates. In addition, if detailed calculations are performed to improve accuracy, a large amount of calculation is required. Therefore, even if the conventional method is applied to CNN as it is, good results as described in the paper cannot be obtained. In this paper, we propose two approaches to solve this problem. Firstly, we propose a new protocol named Batch-normalizedActivation that combines BatchNormalization and Activation. Since BatchNormalization includes real number operations, when performing secret calculation, parameters must be converted into integers, which causes a calculation error and decrease accuracy. By using our protocol, calculation errors can be eliminated, and accuracy degradation can be eliminated. Further, the processing is simplified, and the amount of calculation is reduced. Secondly, we explore a secret computation friendly and high accuracy architecture. Related works use a low-accuracy, simple architecture, but in reality, a high accuracy architecture should be used. Therefore, we also explored a high accuracy architecture for the CIFAR10 dataset. Our proposed protocol can compute prediction of CIFAR-10 within 15.05 seconds with 87.36% accuracy while providing model obliviousness.

70. Constructive t-secure Homomorphic Secret Sharing for Low Degree Polynomials

Kittiphop Phalakarn, Vorapong Suppakitpaisarn, Nuttapong Attrapadung, and Kanta Matsuura

INDOCRYPT 2020

This paper proposes t-secure homomorphic secret sharing schemes for low degree polynomials. Homomorphic secret sharing is a cryptographic technique to outsource the computation to a set of servers while restricting some subsets of servers from learning the secret inputs. Prior to our work, at Asiacrypt 2018, Lai, Malavolta, and Schröder proposed a 1-secure scheme for computing polynomial functions. They also alluded to t-secure schemes without giving explicit constructions; constructing such schemes would require solving set cover problems, which are generally NP-hard. Moreover, the resulting implicit schemes would require a large number of servers. In this paper, we provide a constructive solution for threshold-t structures by combining homomorphic encryption with the classic secret sharing scheme for general access structure by Ito, Saito, and Nishizeki. Our scheme also quantitatively improves the number of required servers from O(t2)O(t2) to O(t), compared to the implicit scheme of Lai et al. We also suggest several ideas for future research directions.

71. Efficient Noise Generation to Achieve Differential Privacy with Applications to Secure Multiparty Computation

Reo Eriguchi, Atsunori Ichikawa, Noboru Kunihiro, and Koji Nuida

FC 2021

This paper studies the problem of constructing secure multiparty computation protocols whose outputs satisfy differential privacy. We first provide a general framework for multiparty protocols generating shares of noise drawn from distributions capable of achieving differential privacy. Then, using this framework, we propose two kinds of protocols based on secret sharing. The first one is a constant-round protocol which enables parties to jointly generate shares of noise drawn from the discrete Laplace distribution. This protocol always outputs shares of noise while the previously known protocol fails with non-zero probability. The second protocol allows the parties to non-interactively obtain shares of noise following the binomial distribution by predistributing keys for pseudorandom functions in the setup phase. As a result, the parties can compute a share of noise enough to provide the computational analogue of ε-differential privacy with communication complexity independent of ε. It is much more efficient than the previous protocols which require communication complexity proportional to εε−2 to achieve (information-theoretic) (ε,δ)-differential privacy for some δ>0.

72. On Limitation of Plausible Deniability

Atsushi Waseda, Ryo Nojima

IWSEC 2020

Recently, a new security definition, named plausible deniability, for synthetic records has been proposed by Bindschaedler et al. Intuitively, the synthetic record r is said to satisfy plausible deniability if there are multiple “original” records that may become r. In this paper, we show that even if each synthetic record satisfies the plausible deniability, there is a possibility that the collection of these records will not have the plausible deniability, i.e., some of these records are re-identifiable.

73. Communication-Efficient Distributed SGD with Error-Feedback, Revisited

Tran Thi Phuong, Le Trieu Phong

We show that the convergence proof of a recent algorithm called dist-EF-SGD for distributed stochastic gradient descent with communication efficiency using error-feedback of Zheng et al. (NeurIPS 2019) is problematic mathematically. Concretely, the original error bound for arbitrary sequences of learning rate is unfortunately incorrect, leading to an invalidated upper bound in the convergence theorem for the algorithm. As evidences, we explicitly provide several counter-examples, for both convex and non-convex cases, to show the incorrectness of the error bound. We fix the issue by providing a new error bound and its corresponding proof, leading to a new convergence theorem for the dist-EF-SGD algorithm, and therefore recovering its mathematical analysis.

74. A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs.

Shuichi Katsumata.

CRYPTO 2021

75. Functional Encryption for Turing Machines with Dynamic Bounded Collusion from LWE.

Shweta Agrawal, Monosij Maitra, Narasimha Sai Vempati, and Shota Yamada.

CRYPTO 2021

76. Non-Interactive Secure Multiparty Computation for Symmetric Functions, Revisited: More Efficient Constructions and Extensions

Reo Eriguchi, Kazuma Ohara, Shota Yamada, Koji Nuida

CRYPTO 2021

77. A Concrete Treatment of Efficient Continuous Group Key Agreement via Multi-Recipient PKEs.

Keitaro Hashimoto, Shuichi Katsumata, Eamonn W. Postlethwaite, Thomas Prest, Bas Westerbaan.

ACM CCS 2021

Continuous group key exchange （CGKA）とは、グループ間でのメッセージングを高い安全性で可能にする暗号学的道具である。SignalやMLS等の様々なメッセージングプロトコルの根幹にCGKAプロトコルにTreeKEMと呼ばれる方式があるが、本研究では、Chained Committing multi-PKE (Chained CmPKE)という新しいCGKAプロトコルを提案する。各グループメンバーが送信するデータサイズはTreeKEMとChained CmPKEでは同じだが、受信するデータサイズをO(N)からO(1)の削減に成功した。ただし、Nはグループメンバー数である。本研究では、耐量子安全なCGKAプロトコルを目的に、格子に特化した効率的なmulti-PKEも構成し、様々な環境での実装実験を行なって、実効率性を計測した。例えば、N = 2^10の場合でも、送信メッセージを100ms以下で計算可能である。

78. An Efficient Secure Division Protocol Using Approximate Multi-Bit Product and New Constant-Round Building Blocks

Keitaro Hiwatashi, Satsuya Ohata, Koji Nuida

Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2nZ2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds →→ 31 rounds) for 64-bit integers in comparison with the most efficient previous one.

79. Efficiency and Accuracy Improvements of Secure Floating-Point Addition over Secret Sharing

Kota Sasaki, Koji Nuida

In secure multiparty computation (MPC), floating-point numbers should be handled in many potential applications, but these are basically expensive. In particular, for MPC based on secret sharing (SS), the floating-point addition takes many communication rounds though the addition is the most fundamental operation. In this paper, we propose an SS-based two-party protocol for floating-point addition with 13 rounds (for single/double precision numbers), which is much fewer than the milestone work of Aliasgari et al. in NDSS 2013 (34 and 36 rounds, respectively) and also fewer than the state of the art in the literature. Moreover, in contrast to the existing SS-based protocols which are all based on “roundTowardZero” rounding mode in the IEEE 754 standard, we propose another protocol with 15 rounds which is the first result realizing more accurate “roundTiesToEven” rounding mode. We also discuss possible applications of the latter protocol to secure Validated Numerics (a.k.a. Rigorous Computation) by implementing a simple example.

80. Homomorphic Secret Sharing for Multipartite and General Adversary Structures Supporting Parallel Evaluation of Low-Degree Polynomials

Reo Eriguchi, Koji Nuida

ASIACRYPT 2021

Homomorphic secret sharing (HSS) for a function ff allows input parties to distribute shares for their private inputs and then locally compute output shares from which the value of ff is recovered. HSS can be directly used to obtain a two-round multiparty computation (MPC) protocol for possibly non-threshold adversary structures whose communication complexity is independent of the size of ff. In this paper, we propose two constructions of HSS schemes supporting parallel evaluation of a single low-degree polynomial and tolerating multipartite and general adversary structures. Our multipartite scheme tolerates a wider class of adversary structures than the previous multipartite one in the particular case of a single evaluation and has exponentially smaller share size than the general construction. While restricting the range of tolerable adversary structures (but still applicable to non-threshold ones), our schemes perform ℓℓ parallel evaluations with communication complexity approximately ℓ/logℓℓ/log⁡ℓ times smaller than simply using ℓℓ independent instances. We also formalize two classes of adversary structures taking into account real-world situations to which the previous threshold schemes are inapplicable. Our schemes then perform O(m)O(m) parallel evaluations with almost the same communication cost as a single evaluation, where mm is the number of parties.

81. Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic

Koji Nuida

PKC 2021

Randomness is an essential resource for cryptography. For practical randomness generation, the security notion of pseudorandom generators (PRGs) intends to automatically preserve (computational) security of cryptosystems when used in implementation. Nevertheless, some opposite case such as in computational randomness extractors (Barak et al., CRYPTO 2011) is known (but not yet systematically studied so far) where the security can be lost even by applying secure PRGs. The present paper aims at pushing ahead the observation and understanding about such a phenomenon; we reveal such situations at layers of primitives and protocols as well, not just of building blocks like randomness extractors. We present three typical types of such cases: (1) adversaries can legally see the seed of the PRGs (including the case of randomness extractors); (2) the set of “bad” randomness may be not efficiently recognizable; (3) the formulation of a desired property implicitly involves non-uniform distinguishers for PRGs. We point out that the semi-honest security of multiparty computation also belongs to Type 1, while the correctness with negligible decryption error probability for public key encryption belongs to Types 2 and 3. We construct examples for each type where a secure PRG (against uniform distinguishers only, for Type 3) does not preserve the security/correctness of the original scheme; and discuss some countermeasures to avoid such an issue.

82. Accelerating Secure (2+1)-Party Computation by Insecure but EfficientBuilding Blocks

Keitaro Hiwatashi, Ken Ogura, Satsuya Ohata, Koji Nuida

ACM AsiaCCS 2021

Secure multi-party computation (MPC) is a cryptographic tool that enables a set of parties to compute a function jointly while keeping each input secret. Since MPC based on secret sharing (SS) achieves high throughput and works fast, many applications have been developed. However, SS-based MPC requires many communication rounds in general, and this becomes a performance bottleneck in real-world applications under high-latency networks. In this paper, we propose SS-based secure three-party computation with almost no preprocessing based on our new (small-)constant-round fundamental gates, by revisiting a framework in a few previous works where a number of parties are assisted by another party who may partially learn secret information. Instead of ordinary logical gates, our fundamental gate is an efficient Equality, for which the result leaks to the third party, and we develop novel two-round constructions of secure building-block protocols (LessThan Comparison, RightShift, Table LookUp, etc.) from the insecure Equality. To show the practicality of our protocols, we implement a secure exact edit distance protocol for two genome strings. Our experiments show that in some network setting our protocol is about 2 times faster (14 times faster taking preprocessing into consideration) than the state-of-the-art SS-based protocol (Ohata and Nuida, FC 2020).

83. Evolving Homomorphic Secret Sharing for Hierarchical Access Structures

Kittiphop Phalakarn, Vorapong Suppakitpaisarn, Nuttapong Attrapadung, and Kanta Matsuura

Secret sharing is a cryptographic primitive that divides a secret into several shares, and allows only some combinations of shares to recover the secret. As it can also be used in secure multi-party computation protocol with outsourcing servers, several variations of secret sharing are devised for this purpose. Most of the existing protocols require the number of computing servers to be determined in advance. However, in some situations we may want the system to be “evolving”. We may want to increase the number of servers and strengthen the security guarantee later in order to improve availability and security of the system. Although evolving secret sharing schemes are available, they do not support computing on shares. On the other hand, “homomorphic” secret sharing allows computing on shares with small communication, but they are not evolving. As the contribution of our work, we give the definition of “evolving homomorphic” secret sharing supporting both properties. We propose two schemes, one with hierarchical access structure supporting multiplication, and the other with partially hierarchical access structure supporting computation of low degree polynomials. Comparing to the work with similar functionality of Choudhuri et al. (IACR ePrint 2020), our schemes have smaller communication costs.

84. Statistical ZAPs from Group-Based Assumptions

Geoffroy Couteau, Shuichi Katsumata, Elahe Sadeghi, and Bogdan Ursu

Theory of Cryptography, TCC 2021, Lecture Notes in Computer Science

We put forth a template for constructing statistical ZAPs for NP. Our template compiles NIZKs for NP in the hidden bit model (which exist unconditionally) into statistical ZAPs using a new notion of interactive hidden-bit generator (IHBG), which adapts the notion of hidden-bit generator to the plain model by building upon the recent notion of statistically-hiding extractable commitments. We provide a construction of IHBG from the explicit hardness of the decision Diffie-Hellman assumption (where explicit refers to requiring an explicit upper bound on the advantage of any polynomial-time adversary against the assumption) and the existence of statistical ZAPs for a specific simple language, building upon the recent construction of dual-mode hidden-bit generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations of the underlying simple ZAP: 1. Using the recent statistical ZAP for the Diffie-Hellman language of (Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP assuming (the explicit hardness of) DDH in G1G1 and kernel-DH in G2G2 (a search assumption which is weaker than DDH), where (G1,G2)(G1,G2) are groups equipped with an asymmetric pairing. This improves over the recent work of (Lombardi et al., EUROCRYPT 2020) which achieved a relaxed variant of statistical ZAP for NP, under a stronger assumption. 2. Using the recent work of (Couteau et al., EUROCRYPT 2020), we obtain statistical ZAPs for NP assuming the explicit hardness of DDH, together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size 2\secpar2\secpar with probability better than \poly(\secpar)/2(c+o(1))⋅\secpar\poly(\secpar)/2(c+o(1))⋅\secpar, denoted 2−c\secpar2−c\secpar-\OWKDM, for a constant c = 1/2, in pairing-free groups. Note that the latter is a search discrete-log-style falsifiable assumption, incomparable to DDH (in particular, it is not known to imply public-key encryption).

85. Secure Graph Analysis at Scale

Toshinori Araki, Jun Furukawa, Benny Pinkas, Kazuma Ohara, Hanan Rosemarin, and Hikaru Tsuchida

Proceedings of the 28th ACM Conference on Computer and Communications Security (ACM CCS 2021)

86. Oblivious Linear Group Actions and Applications

Nuttapong Attrapadung, Goichiro Hanaoaka, Takahiro Matsuda, Hiraku Morita, Kazuma Ohara, Jacob Schuldt, Tadanori Teruya, and Kazunari Tozawa

Proceedings of the 28th ACM Conference on Computer and Communications Security (ACM CCS 2021)

87. Outlier Detection by Privacy-Preserving Ensemble Decision Tree Using Homomorphic Encryption

Kengo Itokazu, Lihua Wang, Seiichi Ozawa

Proc. of International Joint Conference on Neural Network 2021

88. Efficient Privacy-Preserving Variable-Length Substring Match for Genome Sequence

Yoshiki Nakagawa, Satsuya Ohata, Kana Shimizu

Finding a similar substring that commonly appears in query and database sequences is an essential task for genome data analysis. This study proposes a secure two-party variable-length string search protocol based on secret sharing. The unique feature of our protocol is that time, communication, and round complexities are not dependent on the database length N, after the query input. This property brings dramatic performance improvements in search time, since N is usually quite large in an actual genome database, and the same database is repeatedly used for many queries. Our concept hinges on a technique that efficiently applies the compressed full-text index (FOCS 2000) for a secret-sharing scheme. We conducted an experiment using a human genomic sequence with the length of 10 million as the database and a query with the length of 100 and found that the query response time of our protocol was at least three orders of magnitude faster than a well-designed baseline protocol under the realistic computation/network environment.

89. How to Handle Invalid Queries for Malicious-Private ProtocolsBased on Homomorphic Encryption

Koji Nuida

Proceedings of The 9th ACM ASIA Public-Key Cryptography Workshop(APKC 2022)

We consider a setting of two-party computation between a server and a client where every message
received by the server is encrypted by a fully homomorphic encryption (FHE) scheme and its decryption
key is held by the client only. Akavia and Vald (IACR ePrint Archive, 2021) revisited the privacy problem
in such protocols against malicious servers and revealed (as opposed to a naive expectation) that under
certain condition, a malicious server can recover the client’s input even if the underlying FHE scheme is
IND-CPA secure. They also gave some sufficient conditions for the FHE scheme to ensure the privacy
against malicious servers. However, their argument did not consider the possibility that a query from a
malicious server to a client involves an invalid ciphertext. In this paper, we show, by giving a concrete
example, that if such an invalid query is just rejected by the client, then the sufficient conditions in
Akavia and Vald’s result do not in general ensure the privacy against malicious servers. We also propose
another option to handle an invalid query in a way that the client returns a random ciphertext (without
explicitly rejecting the query), and show that such a protocol is private against malicious servers if the
underlying FHE scheme is IND-CPA secure, sanitizable (in the sense of Ducas and Stehl´e, EUROCRYPT
2016), and circular secure.

90. Decentralized Descent Optimization with Stochastic Gradient Signs for Device-to-Device Networks

Tran Thi Phuong and Le Trieu Phong

We propose an algorithm for decentralized optimization in wireless device-to-device (D2D) networks of pervasive devices such as sensors or 5G handsets, in which the signs of stochastic gradient are used for descent steps. Our algorithm has the convergence rate of O (1/( nT )) in which n is the number of devices and T is the number of learning iterations, saving the communication efficiency by at least 64 times when compared with previous results, and being relatively robust to unexpected errors of adversarial scaling in communication. Theoretical claims are verified by numerical results on a standard benchmark dataset.

91. Adaptively secure revocable hierarchical IBE from k-linear assumption

Keita Emura, Atsushi Takayasu, Yohei Watanabe

Revocable identity-based encryption (RIBE) is an extension of IBE with an efficient key revocation mechanism. Revocable hierarchical IBE (RHIBE) is its further extension with key delegation functionality. Although there are various adaptively secure pairing-based RIBE schemes, all known hierarchical analogues only satisfy selective security. In addition, the currently known most efficient adaptively secure RIBE and selectively secure RHIBE schemes rely on non-standard assumptions, which are referred to as the augmented DDH assumption and q-type assumptions, respectively. In this paper, we propose a simple but effective design methodology for RHIBE schemes. We provide a generic design framework for RHIBE based on an HIBE scheme with a few properties. Fortunately, several state-of-the-art pairing-based HIBE schemes have the properties. In addition, our construction preserves the sizes of master public keys, ciphertexts, and decryption keys, as well as the complexity assumptions of the underlying HIBE scheme. Thus, we obtain the first RHIBE schemes with adaptive security under the standard k-linear assumption. We prove adaptive security by developing a new proof technique for RHIBE. Due to the compactness-preserving construction, the proposed R(H)IBE schemes have similar efficiencies to the most efficient existing schemes.

92. Implementation and Evaluation of an Identity-Based Encryption with Security Against the KGC

Shuntaro Ema, Yuta Sato, Keita Emura, Toshihiro Ohigashi

In identity-based encryption (IBE), a key generation center (KGC) issues a secret key for an identity. Although any value can be used as a public key, the KGC has the potential to decrypt all ciphertexts even if it is not the actual destination. To solve this key escrow problem, Emura, Katsumata, and Watanabe (EKW) proposed an IBE scheme with security against KGC (ESORICS 2019) and provided a pairing-based construction by extending the Boneh-Franklin IBE scheme (CRYPTO 2001). Briefly, they used the Chow framework (PKC 2009), which introduced a new type of authority known as an identity-certifying authority (ICA). Each user obtains an identity certificate from the ICA and can anonymously obtain a secret key from the KGC through an interactive protocol. Though the KGC can issue a secret key without knowing the user’s identity, an additional communication (between the user and the ICA) and computation by the KGC are required compared to the conventional IBE scheme. In this paper, we implement the pairing-based EKW IBE scheme and show that the additional costs are insignificant compared to the Boneh-Franklin IBE scheme.

93. Verifiable Functional Encryption Using Intel SGX.

Tatsuya Suzuki, Keita Emura, Toshihiro Ohigashi, Kazumasa Omote

Most functional encryption schemes implicitly assume that inputs to decryption algorithms, i.e., secret keys and ciphertexts, are generated honestly. However, they may be tampered by malicious adversaries. Thus, verifiable functional encryption (VFE) was proposed by Badrinarayanan et al. in ASIACRYPT 2016 where anyone can publicly check the validity of secret keys and ciphertexts. They employed indistinguishability-based (IND-based) security due to an impossibility result of simulation-based (SIM-based) VFE even though SIM-based security is more desirable. In this paper, we propose a SIM-based VFE scheme. To bypass the impossibility result, we introduce a trusted setup assumption. Although it appears to be a strong assumption, we demonstrate that it is reasonable in a hardware-based construction, e.g., Fisch et al. in ACM CCS 2017. Our construction is based on a verifiable public-key encryption scheme (Nieto et al. in SCN 2012), a signature scheme, and a secure hardware scheme, which we refer to as VFE-HW. Finally, we discuss an implementation of VFE-HW using Intel Software Guard Extensions (Intel SGX).

94. Revisiting Fuzzy Signatures: Towards a More Risk-Free Cryptographic Authentication System based on Biometrics

Shuichi Katsumata, Takahiro Matsuda, Wataru Nakamura, Kazuma Ohara, Kenta Takahashi.

Proceedings of the 28th ACM Conference on Computer and Communications Security (ACM CCS 2021)

Biometric authentication is one of the promising alternatives to standard password-based authentication offering better usability and security. In this work, we revisit the biometric authentication based on fuzzy signatures introduced by Takahashi et al. (ACNS’15, IJIS’19). These are special types of digital signatures where the secret signing key can be a ”fuzzy” data such as user’s biometrics. Compared to other cryptographically secure biometric authentications as those relying on fuzzy extractors, the fuzzy signature-based scheme provides a more attractive security guarantee. However, despite their potential values, fuzzy signatures have not attracted much attention owing to their theory-oriented presentations in all prior works. For instance, the discussion on the practical feasibility of the assumptions (such as the entropy of user biometrics), which the security of fuzzy signatures hinges on, is completely missing.

In this work, we revisit fuzzy signatures and show that we can indeed efficiently and securely implement them in practice. At a high level, our contribution is threefold: (i) we provide a much simpler, more efficient, and direct construction of fuzzy signature compared to prior works; (ii) we establish novel statistical techniques to experimentally evaluate the conditions on biometrics that are required to securely instantiate fuzzy signatures; and (iii) we provide experimental results using a real-world finger-vein dataset to show that finger-veins from a single hand are sufficient to construct efficient and secure fuzzy signatures. Our performance analysis shows that in a practical scenario with 112-bits of security, the size of the signature is 1256 bytes, and the running time for signing/verification is only a few milliseconds.

95. Identity-based encryption with security against the KGC: A formal model and its instantiations

Keita Emura, Shuichi Katsumata, Yohei Watanabe

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem.

In this paper, based on Chow’s work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow’s work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry–Peikert–Vaikuntanathan IBE scheme (STOC 2008) and Rückert’s lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh–Franklin IBE scheme (CRYPTO 2001) and Boldyreva’s blind signature scheme (PKC 2003).