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

属性ベース暗号は、暗号文の復号権限の柔軟な制御を可能とする技術である。属性ベース暗号においては、暗号文は属性x、秘密鍵はポリシーPと関連付けられ、復号は属性ｘがポリシーPを充足する際にのみ可能である。本研究では、Pが非決定性有限オートマトン、xがその入力である場合に関して、（対象鍵）属性ベース暗号の構成を、最悪時格子問題の困難性の仮定のもと示した。本方式は、識別不可性難読化などの非標準的仮定を用いない、初の非決定性有限オートマトンを利用可能な属性ベース暗号方式である。

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

公開鍵暗号方式の研究では、選択暗号文攻撃に対する安全性(IND-CCA)と呼ばれる強力な安全性を満たす公開鍵暗号方式や、落とし戸付き関数(Trapdoor Function)と呼ばれる基礎的な暗号要素技術を、最低限の受動的な安全性である選択平文攻撃に対する安全性(IND-CPA)を満たす公開鍵暗号方式のみから構成できるかどうか、が重要な理論的未解決問題となっている。本研究では、その問題の解決に向けた一歩として、IND-CPA安全な公開鍵暗号方式以外に、「一度だけ秘密鍵に依存した平文を安全に暗号化できる共通鍵暗号方式」を構成要素として用いて組み合わせることで、IND-CCA安全な公開鍵暗号方式を構成できることを示した。さらに、構成要素のIND-CPA安全な公開鍵暗号方式及び共通鍵暗号方式に、ある基礎的で簡素な追加の要件を満たす方式を用いることで、Trapdoor Functionを構成できることも示した。

フルバージョン：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受賞

有限体の要素を入力として扱う秘密分散ベースの算術回路の秘匿計算プロトコルでは、(1)効率化のために計算に必要な最低限の精度を保てるほどに体のサイズを小さくしたい、という要求がある反面、(2)能動的な攻撃者(Malicious攻撃者)に対する安全性を達成するためには様々なプロトコル途中での「検証操作」が必要であり、それは通常は体の要素の等号判定に帰着されるため、体のサイズを小さくしすぎると攻撃者の不正を検知失敗する確率が無視できなくなってしまう、というジレンマが存在する。本研究では、そのジレンマを取り払うため、計算したい算術回路の「主たる計算」の実行は基の体で行いつつ、(例えば計算の正しさの検証操作のため、などの)必要に応じて秘密分散の値を拡大体上の秘密分散のシェアへと変換して取り扱うことができるテクニックを考案した。そして、CRYPTO 2018でChidaらが提案した効率的な、能動的攻撃者に対する安全性を満たす算術回路の秘匿計算プロトコルへと適用し、彼らの方式が持っていた体のサイズの下限に関する制限を取り払ったより柔軟な体の選択が可能な秘匿計算プロトコルを提案した。

フルバージョン：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)

格子の基底と自然数列の集合で表現される探索空間から格子ベクトルの集合を出力するサンプリングアルゴリズムについて，あるノルム以下の格子ベクトルが出力される集合にいくつ含まれているかを推定する方法を提案する．提案方法は，randomness仮定の元で構成され，確率分布に対する高次キュムラントを使用した漸近級数展開の一つであるGram-Charlier A型級数展開を利用したパラメトリックな推定方法であり，興味があるノルムに対する相対頻度分布の累積分布関数を推定結果として出力する．提案方法の計算は既存の方法よりも高速であり，実験の上では観測値に対して一定の精度がある．さらに，提案方法の出力について，randomness仮定の元で，級数展開が有限な場合の真値への理論的な収束速度を与える．

URL: https://doi.org/10.1145/3327958.3329543

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

採録先 :
IEEE Transactions on Information Forensics and Security

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

採録先 :
Security and Communication Networks

本論文では、メッセージ依存開示可能グループ署名という新たな暗号要素技術を提案する。通常のグループ署名においては、グループのメンバーが匿名で署名を生成することができ、かつ、必要に応じてグループの管理者だけは署名データから署名を生成したメンバーのIDを特定することができた。しかし、この管理者の特権は応用によっては過剰な権限集中となっている場合もある。メッセージ依存開示可能グループ署名においては、グループ管理者とは異なる第二の管理者（admitterと呼ぶ）を設置することができ、admitterに許可された文書に対する署名についてのみグループ管理者が署名を生成したメンバーのIDを特定することができる、という形で、グループ管理者の権限を弱めることができるようになる。本論文では、この暗号要素技術のモデルを定義し、IDベース暗号と非対話ゼロ知識証明とからの一般的構成を与えた。また逆に、このモデルのもとで安全な任意のメッセージ依存開示可能グループ署名から、IDベース暗号が構成できることを示した。さらに、ペアリング群を用いた具体的構成も2つ与えた。一つは標準モデルで安全だが開示を許可できるメッセージの個数に事前の制約がある方式であり、もう一方はランダムオラクルモデルで安全だが前者の方式のような事前の制約はない方式である。
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.

URL: https://www.hindawi.com/journals/scn/2019/4872403/

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

著者：
Hiraku Morita, Nuttapong Attrapadung

採録先：
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

採録先：
Theoretical Computer Science

公開鍵暗号方式のReceiver Selective Opening (RSO)安全性は、一人の送信者と多数の受信者がいる状況において、攻撃者が一部の受信者の秘密鍵と受信した平文を取得できる際に、その他の受信者の暗号文の秘匿性を保証する安全性である。RSO安全性に対して、識別不可能性(IND)に基づく定義とシミュレーション(SIM)に基づく定義、及び、選択平文攻撃(CPA)と選択暗号文攻撃(CCA)を考えることができ、SIM-RSO-CCA安全性はRSO安全性において最も強い安全性である。本研究以前には、SIM-RSO-CCA安全性を満たす公開鍵暗号方式は、識別不可能性難読化を用いたものしか知られていなかった。本研究では、標準的な仮定に基づきSIM-RSO-CCA安全性を満たす公開鍵暗号方式を目指し、二つの構成を示した。第一の構成は、IND-CPA安全性を満たす公開鍵暗号方式と一回シミュレーション健全性を満たす非対話型ゼロ知識証明システムを用いた一般的な構成である。第二の構成は、Cramer-Shoup暗号を構成の基礎としたDDH仮定に基づく構成である。また、ジャーナル版の差分として、第二の構成を基に、長い平文を暗号化する際でも暗号文オーバヘッド(暗号文サイズと平文サイズの差)が定数個の群要素とできる構成を示した。

URL : https://www.sciencedirect.com/science/article/pii/S0304397519305055?via%3Dihub

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

著者：
Fuyuki Kitagawa, Takahiro Matsuda, Keisuke Tanaka

採録先：
ASIACRYPT 2019

秘密鍵に依存した平文を暗号化しても暗号文から平文の情報が漏れないことを保証する安全性は、鍵依存平文安全性(Key-Dependent Message (KDM)安全性)と呼ばれる。KDM安全性においても標準的な”識別不可能性”(IND)と同様、選択平文攻撃(CPA)と選択暗号文攻撃(CCA)を考えることができる。本研究では、KDM-CCAを満たす、効率的な公開鍵暗号方式を二つ提案した。第一の方式は、アフィン関数についてのKDM-CCA安全性(すなわち、秘密鍵のアフィン関数を安全に暗号化できる、という安全性)を満たす方式であり、第二の方式は、多項式についてのKDM-CCA安全性を見たす。提案構成は、共にMalkinら(EUROCRYPT’11)のDCR仮定に基づくKDM-CPA安全と、IND-CCA安全なPKEを適切に組み合わせて構成したものであり、さらに安全性証明における、DCR仮定と構成要素の公開鍵暗号方式のIND-CCA安全性への帰着はタイトである。

16. CPA-to-CCA Transformation for KDM Security

著者：
Fuyuki Kitagawa, Takahiro Matsuda

採録先：
TCC 2019

秘密鍵に依存した平文を暗号化しても暗号文から平文の情報が漏れないことを保証する安全性は、鍵依存平文安全性(Key-Dependent Message (KDM)安全性)と呼ばれる。KDM安全性においても標準的な”識別不可能性”(IND)と同様、選択平文攻撃(CPA)と選択暗号文攻撃(CCA)を考えることができる。本研究では、KDM-CPA安全な公開鍵暗号方式を構成要素として、KDM-CCA安全な公開鍵暗号方式を一般的に構成できることを示した。(より詳細には、提案方式は、IND-CPA安全な公開鍵暗号方式と、(One-time) KDM-CPA安全な共通鍵暗号方式に基づくKDM-CCA安全な公開鍵暗号方式の構成であるが、構成要素はともにKDM-CPA安全な公開鍵暗号方式に含意されている。)本成果により、KDM-CPA安全な公開鍵暗号方式とKDM-CCA安全な公開鍵暗号方式の存在性は等価であるといえる。また、既存の結果と組み合わせると、初のCDH仮定やLPN仮定に基づくKDM-CCA安全な公開鍵暗号方式が得られる。

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

著者：
Yusuke SAKAI, Goichiro HANAOKA

採録先：
IEICE Trans. Fundamentals

選択暗号文攻撃に対する安全性は公開鍵暗号の設計において中心的なゴールである。また同時に、よく知られた困難な問題に安全性を緊密に帰着させることも、加えて重要である。さらに、緊密な帰着を複数ユーザ複数チャレンジの設定で行うことが、単一ユーザ単一チャレンジの設定での安全性は複数ユーザ複数チャレンジの安全性を必ずしも緊密には保証しないため、なお重要である。本論文では、実用的な性能を持つ、完全に緊密に安全で選択暗号文攻撃に対して安全な公開鍵暗号をランダムオラクルモデルにおいて提案する。提案方式は、ペアリングなしの群で判定Diffie-Hellman仮定のもとで安全である。暗号文オーバーヘッドは2つの群要素と2つの指数からなる。

18. Attribute Based Encryption for Deterministic FiniteAutomata fromDLIN

著者：
Shweta Agrawal, Monosij Maitra, Shota Yamada

採録先：
TCC 2019

属性ベース暗号は、暗号文の復号権限の柔軟な制御を可能とする技術である。属性ベース暗号においては、暗号文は属性x、秘密鍵はポリシーPと関連付けられ、復号は属性ｘがポリシーPを充足する際にのみ可能である。本研究では、Pが決定性有限オートマトン、xがその入力である場合に関して、属性ベース暗号の構成を、decisional linear assumptionの下で示した。本方式は、ペアリング群上の標準的仮定を用いた初の決定性有限オートマトンを利用可能な属性ベース暗号方式である。

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.

秘匿計算の最も基本的な関数の一つである秘匿整数比較を2者間で行う，効率的な5ラウンドのプロトコルを構成した．これは既存の最良の方式と比べて，通信ラウンドを約1/5にした．構成のテクニックは，クライアント補助型の性質を用いて，計算に必要な乱数を前もって作成しておくことと，複数入力の乗算を少ラウンドで実行すること，木構造ベースのエンコード法を採用したこと，である．

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

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

著者：
Satsuya Ohata, Koji Nuida

採録先：
FC’ 20.

秘密分散ベースのMPCはベクトル化が容易で高スループットを達成可能であるが、通信ラウンド数が回路の深さに依存するため、遅延の大きいWAN環境などでは性能が落ちてしまう。本研究では、通常の秘密分散ベース2PCと比較したときに、計算量およびメモリ使用量は指数的に増加するが、通信データ量およびラウンド数が少なくなるプロトコル（一致判定、大小比較、最大値抽出など）の構成法を提案した。鍵となるのはBeaver Triple Extensionと呼んでいるMulti-fan-in ANDゲート用に拡張された特殊な事前計算と、その効率的な利用法である。提案プロトコルの通信ラウンド数は（2者間秘密分散ベースMPCにおいて）我々が知る限り最も少なく、例えば64ビット整数の大小比較を3ラウンドで実行できる。論文中では提案したMulti-fan-in ANDゲートおよび構成したプロトコルの性能評価を行っている他、動的計画法によるプライバシ保護編集距離計算プロトコルを実装し、1024文字のゲノム文字列同士の編集距離をWAN環境でも約6分（オンライン計算時間）で処理可能であることを示した。

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

採録先：
EICE Trans. Fundamentals

公開鍵型検索可能暗号（Public-key encryption with keyword search, PEKS）とは、暗号文上でのキーワード検索を可能とする暗号要素技術である。PEKSを用いることで、データを暗号化しつつ、かつ検索の機能性を損なわないまま、データをクラウドに預けることが可能となる。論理和／論理積を検索条件として用いることができるようなPEKSの匿名性を持つ属性ベース暗号（ABE）からの一般的構成が知られているが、そのようなABEに起因する大きなオーバーヘッドを避けた構成が可能かどうかは明らかではない。本論文では、ABEのような強力な暗号要素技術が上述のようなPEKSを構成するのに不可避であることを示す。具体的には、匿名性を持つ鍵ポリシー属性ベース暗号の、上述のようなPEKSからの一般的構成を示す。本結果は、上述のようなPEKSはABE相当の計算量／通信量や数学的仮定を本質的に要求することを示唆している。

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

著者：
Ali El Kaafarani, Shuichi Katsumata, Federico Pintore

採録先：
PKC 2020

去年のAsiacrypt19で、Buellens, Kleinjung, and Vercauteren等は、初めての効率的なFiat-Shamir (FS)署名をisogenyから構成した。彼らは、特殊なCSIDH-512というclass groupを計算することで、この結果を得た。しかし、ほとんどのFS署名の証明がそうであるように、彼らの方式の帰着効率は非常にゆるく、安全性はヒューリスティックに基づいて与えられている。
本論文では、彼らの方式に少しだけ変更を加えることで、理論的に安全、かつ、効率的な署名をisogenyから構成する。例えば、短い署名長の方式が欲しい場合は、我々の方式は署名と検証にだいたい800msかかり、署名サイズは280byteである。これはBuellens等の方式と比べ、署名と検証時間が二倍で、署名サイズは同じである。最後に、我々の方式は、ROMでもQROMでも理論的に安全である。

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

著者：
Geoffroy Couteau, Shuichi Katsumata, Bogdan Ursu

採録先：
EUROCRYPT 2020

本論文では、NIZK for NPをdiscrete log系の仮定から構成する。一番近い既存研究として、Canetti等＠EC18は、NIZK for NPをDL仮定から構成できる「復号機能が制限された」ElGamal暗号のoptimal KDM安全性を仮定することで構成した。しかし、この仮定は非常に強く、公開鍵プリミティブをimplyすることが知られている。従って、現状NIZK for NPは、公開鍵プリミティブをimplyする仮定からしか構成がしられていない。
本論文では、公開鍵プリミティブをimplyするとは信じられていDL系の仮定からNIZK for NPを構成する。具体的に、CDH仮定が成り立つ場合のNIZK for NPの構成、および、CDH仮定が成り立たないが、特殊なDL系の仮定が場合のNIZK for NPの構成の両者を与えることで、CDH仮定の成立に関係なく、NIZK for NPが構成できることを示した。後者の構成に関しては、CDH仮定が成立しない世界では、CDHソルバーを利用したself bilinear mapが存在することを利用している。

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)である。
本論文では、初めてDLIN仮定から証明サイズが|C| + poly(\secpar)となるNIZK for NPを構成した。これに伴い、DLIN仮定からdecomposable online-offline効率性を持つconstrained署名を構成した。

25. Optimal Broadcast Encryption from Pairings and LWE

著者：
Shweta Agrawal, Shota Yamada

採録先：
EUROCRYPT 2020

本論文では、システム全体のユーザの数をNとしたときに公開鍵長、暗号文長、秘密鍵長の全てがNに依存しないような放送型暗号を、格子構造と双線形写像群を組み合わせることによって構成した。本方式は、同様のパラメータ長と安全性を達成していてかつ識別不可性難読化を用いない初の方式である。本方式の安全性はGeneric group modelでLWE仮定の下で証明される。上記の方式を得るために本研究では、全てのパラメータサイズが暗号文に紐づけられたポリシーの記述長に依存しない初の暗号文ポリシー属性ベース暗号方式を構成した。上記の放送型暗号は適切に暗号文属性や鍵属性をencodeすることにより当該暗号文ポリシー属性ベース暗号方式の特殊ケースとして得られる。また、類似のencode方法により、同様の効率性をもつIDベース放送型暗号も得ることができる。

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

協調フィルタリングに基づき，ユーザの評価データ(あるいは購買履歴)からおすすめのアイテムを提示する推薦システムが利用されている.推薦システムの安全性に関する研究として，特定のアイテムを評価する(あるいは購入する)ことで，推薦精度の低下や特定アイテムの人気向上を引き起こすポイゾニング攻撃が提案されているが，それらはユーザのプライバシーの暴露を意図していない.そこで，本稿では，推薦システムに潜在するプライバシーリスクを明らかにすることを目的とし，ポイゾニングによりユーザのプライバシーを暴露する新たな攻撃として協調フィルタリングに対する Model Inversion 攻撃を提案する.本攻撃は，推薦システムがユーザに提示したアイテムから当該ユーザが過去に高く評価した(あるいは購入した)センシティブなアイテムを暴露する.

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

本論文では、標準的モデルで適応的に安全な制約付き擬似乱数関数（CPRF）を提案した。より具体的には、三つの制約に対して（bit-fixing, inner-product, P/poly）、三種類のCPRFの構成を与えた。CPRFは、普通のPRFに加えて、制約付きの鍵（sk_F）を発行することができ、制約付きの鍵から生成される擬似乱数CPRF(sk_F, x)はマスター秘密鍵skで計算した擬似乱数CPRF(sk, x)と、制約が満たされたときのみ（F(x)=1）一致する。従来のCPRFは、非常に弱い制約、または、ランダムオラクルモデルを除いたら全て選択的にしか安全ではなかった。一つ目のbit-fixing制約CPRFは、一方向性関数のみから構成できる。二つ目のinner-product制約CPRFは、learning with errors (LWE)仮定に基づいて構成できる。最後のP/poly制約CPRFは、indistinguishable obfuscationとLWE仮定に基づいて構成できる。

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つのプロトコルについては理論的なセキュリティ解析と実用性評価を行う。

30. On the Security of Keyed-Homomorphic PKE: Preventing Key Recovery Attacks and Ciphertext Validity Attacks

著者：
Keita Emura

採録先：
IEICE Trans. Fundamentals

準同型暗号では誰もが準同型演算を行うことが可能であり, そのためCCA安全性を満たさないことが知られている. 対して鍵付き準同型暗号 (Emura et al. (PKC 2013)) では, 準同型演算に秘密鍵を要求することで, この準同型演算鍵を持たない攻撃者に対するCCA安全性が定義される. 本論文では, 鍵付き準同型暗号が (完全準同型暗号に対する攻撃として知られる) 鍵回復攻撃 (Dahab et al. (ICITS2015)) と暗号文正当性検証攻撃 (Loftus et al. (SAC 2011)) に対する耐性を持つことを示す.

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

著者：
Hiromi Arai, Keita Emura, Takuya Hayashi

採録先：
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences.

データ収集時に提供者を匿名とすることで提供者のプライバシーが保護される一方で, データが異常値である場合に提供者を特定する必要がある. グループ署名を用いることで匿名性と追跡性を両立することが可能ではあるが、追跡者はデータが異常値であるなしに関わらず提供者を特定できてしまう。本論文では、この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

属性ベース暗号（ABE）とは、暗号文にアクセスポリシーを埋め込むことができる高機能暗号の一種であり、格子とペアリングに基づいた、様々な種類のアクセスポリシーをサポートするABEが数多く知られている。しかし、現状、ペアリングに基づくABEは幅広いアクセスポリシーに関して適応的（adaptive）安全性が示されている一方、格子に基づくABEはほとんどが選択的（selective）安全性しか示されていない。格子に基づく適応的安全なABEは現在のところ、（IDベース暗号を除いて、）Katsumata Yamada (PKC’19)のnon-zero inner-producut-encryptionとTsabary (Crypto’19)のABE for t-CNF（conjunctive-normal form)に限られている。
本論文では、Tsabary (Crypto’19)の方式で使われたアイデアと、Davidson et al. (Crypto’20)で我々が構成した格子に基づく適応的安全な内積述語用のアクセスポリシー付き擬似乱数関数（CPRF for inner-product）を融合することで、初めての適応的安全な内積述語暗号（IPE）の構成を与える。格子に基づく選択的安全なIPEは、Agrawal et al. (AC’2011)に提案されたが、IPEの適応的安全な構成を提案することは、それ以来の未解決問題であった。

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

著者：
Ward Beullens, Shuichi Katsumata, Federico Pintore

採録先：
ASIACRYPT 2020

本研究では、効率の良い（リンク可能）リング署名を格子と同種写像を基に提案する。我々の主結果は、任意の群作用（Group Action）に対するlogサイズのOR Sigmaプロトコルの作成で、格子と同種写像はそのinstantiationの一つである。我々のOR Sigmaプロトコルはチャレンジ空間が{0, 1}なので、一見すると非常に効率が悪そうに見えるが、従来よりもマークル木の使い方が効率化されているため、比較的少ないユーザー数Nでも、十分効率的なリング署名の構成になっている。

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

著者：
Shuichi Katsumata, Kris Kwiatkowski, Federico Pintore, Thomas Prest.

採録先：
ASIACRYPT 2020

多受信者KEM（multi-recipient KEM）は、ユーザー数が多いグループに向けて同じデータを発信したい場合においては、標準的なKEMと比べて、通信コストや暗号文の計算コストが少なくすむ。しかし、今のところ多受信者KEMの構成はDiffie-Hellman typeの仮定に限られており、多受信者KEMにはいくつかの暗号学的道具からのジェネリック構成が知られているが、それら道具はいずれも耐量子安全な方式での構成が知られていない。
本研究では、多受信者KEMのより簡単、かつ、幅広い安全性仮定からinstantiate可能なジェネリック構成を与える。具体的に、現在NISTに応募されている8つの耐量子KEMとCSIDHの構成を少しだけ変えることで、多受信者KEMにできる。例えば、通信コストは多受信者KEMを使うことで2~35倍程度改善される。さらに、Secure Group MessagingのIETFの根幹を成すTreeKEMと呼ばれるプロトコルを、我々の多受信者KEMを使うことで、効率改善できることも示す。

35. Circular Security Is Complete for KDM Security

著者：
Fuyuki Kitagawa, Takahiro Matsuda

採録先：
ASIACRYPT 2020

秘密鍵skに依存した平文M = f(sk)を暗号化しても暗号文から平文の情報が漏れないことを保証する安全性は、鍵依存平文安全性(Key-Dependent Message (KDM)安全性)と呼ばれる。KDM安全性は、秘密鍵から平文を計算する関数fの表現力や複雑性により強さが異なる。本研究では、慣例的に”Circular Security”と呼ばれる非常に基礎的な関数のクラスについてのKDM安全性を、任意の(多項式サイズの回路で計算可能な)関数クラスについてのKDM安全性へと一般的に強化する手法を示した。より詳細には、提案手法は、Circular-“CPA”安全な暗号方式を構成要素として、回路についてのKDM-“CCA”安全性を満たす暗号方式を得ることができる。Applebaum (EUROCRYPT’10)や、Kitagawa-Matsuda (TCC’19)でも、同種の”KDM安全性の強化手法”が示されたが、本論文の手法は、既存手法と比べ出発点に必要な仮定が弱いため、仮定の弱さの意味で真の改善となっている。また、Kitagawa-Matsuda-Tanaka (CRYPTO’19)や、Kitagawa-Matsuda (TCC’19)の結果と組み合わせて、IND-CCA安全な暗号方式や、再利用可能検証者指定型ゼロ知識主張システムなどが、Circular-CPA安全な暗号方式のみから構成可能、という系が得られる。

36. Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

著者：
Nuttapong Attrapadung, Junichi Tomida

採録先：
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

本論文は、匿名IDベース暗号およびその応用である検索可能暗号の適切な安全性定義を与えるにあたっての見過ごされていた論点を指摘する。具体的には、これまで広く利用されてきた識別不可能性に基づく匿名性の定義は（受信者のIDが漏洩しないという直観をより適切に捉えている）シミュレーションに基づく定義を含意するものであるかどうか、これまで議論されてきていなかったことを指摘する。これを受けて本論文では、シミュレーションに基づくIDベース暗号の匿名性の定義を与え（これ自体は、先行研究で与えられているより一般の概念である属性ベース暗号の匿名性の特殊化である）、これが識別不可能性に基づく定義と同値であることを証明する。この同値性自体は驚くべき結果では必ずしもないが、同値性の証明は全く自明という訳ではではない。実際、平文の秘匿性に関する識別不可能性に基づく定義とシミュレーションに基づく定義との同値性を証明するための手法は我々の文脈には直接は適用できない。これは、平文とIDとの暗号化における役割の違い、特に鍵生成オラクルの存在に由来するものである。

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

著者：
Junichiro HAYATA, Fuyuki KITAGAWA, Yusuke SAKAI, Goichiro HANAOKA, Kanta MATSUURA

採録先：
IEICE Trans. Fundamentals

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

採録先：
P rovsec 2020

既存の集約署名のほとんどはペアリングに依存しており、その高い計算コストは実用化にあたっての障害となっていた。Zhaoはペアリングを用いない初の集約署名を提案した（AsiaCCS 2019）。しかし、Zhaoの方式の安全性は同論文で初めて導入された非標準的な計算困難問題に基づいている。近年指摘されたDrijversら（IEEE S&P 2019）のペアリングを用いない2ラウンド多重署名の離散対数仮定からの証明不可能性は、離散対数仮定のような標準的な仮定からのペアリングを用いない集約署名を構成することは非常に困難であることを示唆するものである。
本論文では、この未解決問題についての新しい解を与える。我々は、集約署名についての新しいモデルである事前通信を持つ集約署名を提案する。事前通信ステージでは、各署名者が集約者と通信を行いある乱数を共有する。ここで、この事前通信は署名対象の文書を決定する前に行うことが可能である。また加えて、Drijversらの証明不可能性は署名生成時の乱数を攻撃者が完全にコントロールできる場合に適用可能となることを見出した。この新しいモデルと証明不可能性に関する観察に基づき、我々は、ペアリングを用いな集約署名を同モデルの下で提案する。この方式は各署名者が独立に乱数を生成し署名に含めるものであり、これによりDrijversらの証明不可能性を回避している。この方式は標準的な仮定である離散対数仮定の下で安全性が証明できる。トレードオフとして、鍵のセットアップのモデルとして、Zhaoの方式が用いていたようなplain public-keyモデルではなくより制限の強いknowledge-of-secret-keyモデルを安全性の証明のために必要とする。

40. NIZK from SNARG

著者：
Fuyuki Kitagawa, Takahiro Matsuda, Takashi Yamakawa

採録先：
TCC 2020

本研究では、証明長が”短い”非対話型証明(Succinct Non-interactive ARGument, 以下SNARG)から、非対話型ゼロ知識証明(Non-interactive Zero-Knowledge argument, 以下NIZK)を構成する手法を示した。構成要素となるSNARGの要件は、|π| = poly(λ)(|x| + |w|)^c (c < 1/2)を満たすことである。(ただし、λはセキュリティパラメータ、|x|は証明したいステートメント長、|w|は証拠情報の長さを指す。)検証に要する計算時間についての要件は不要であるため、SNARGとしての要件は弱いものであると言える。さらに本研究では、SNARGに加えてCPA安全な公開鍵暗号方式を追加の要素技術として用いることで、SNARGからゼロ知識性を満たすSNARGへの一般的な変換を示した。この一般的変換では、基とするSNARGの検証に要する計算時間がpoly(λ)(|x| + |w|)^{o(1)}であることが必要である。また本研究では、上記の成果を得る過程において、NIZKの非適応的ゼロ知識性を適応的ゼロ知識性へと一般的に強化する手法も与えた。

41. “CP-ABE for Circuits (and more) in the Symmetric Key Setting”

著者：
Shweta Agrawal; Shota Yamada

採録先：
TCC 2020

属性ベース暗号は、暗号文と秘密鍵に属性が紐づけられており、両者がある条件を満たすときに復号が可能となるような高機能暗号技術である。属性ベース暗号の中でも、暗号文側が回路/ポリシーと紐づけられており、秘密鍵側が対応する入力と紐づけられているようなものを暗号文ポリシー属性ベース暗号と呼ぶ。
格子に基づく暗号文ポリシー属性ベース暗号は未解決問題であったが、本研究ではこの問題に関して以下の進展を得た。まず、秘密鍵設定で格子に基づく暗号文ポリシー属性ベース暗号を提案した。また、公開鍵設定においても、回路サイズに限界はあるものの、今までよりも良い効率性の方式を提案した。また、秘密鍵設定で、秘密鍵に対応する属性のプライバシーを考えた場合の安全性定義を与え、対応する方式を与えた。また、より強い安全性を満たす方式が得られた場合には識別不可性難読化器を得ることができることを示した。

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

著者：
Shweta Agrawal; Daniel Wichs; Shota Yamada

採録先：
TCC 2020

放送型暗号は、システム内の多数のユーザにメッセージを暗号化して送ることを可能にする技術である。放送型暗号で、公開鍵、暗号文、秘密鍵のサイズが全てシステム内のユーザ数によらない方式は最適な効率性を持つ放送型暗号と呼ぶ。最適な効率性を持つ放送型暗号として、近年、格子と双線形写像に基づく方式が提案されたが、当該方式は安全性がgeneric group modelでしか証明されていないという欠点があった。本研究では、generic group modelを取り除き、KOALA仮定（Knowledge of OrthogonALity Assumption）の変種及びLWE仮定を仮定して標準モデルでの安全性証明を与えた。

43. A Note on Subgroup Security in Discrete Logarithm-Based Cryptography

著者：
Tadanori Teruya

採録先：
IEICE Trans. Fundamentals

群所属判定は，離散対数問題に基づく暗号方式を安全に実装するための重要な処理である．この処理は，スカラー倍またはべき乗という重い演算を必要とするため，様々な高速化手法が研究されている．離散対数問題に基づく暗号方式の一種であるペアリング暗号においては，Barretoら(LATINCRYPT 2015)がsubgroup-secureな楕円曲線というパラメータの選択方法を提案している．これによれば，楕円曲線がsubgroup-secureならば，ある暗号方式において，双線形群の群所属判定におけるスカラー倍やべき乗が省略でき，元の暗号方式よりも高速な方式が得られる．但し，省略ができない方式の存在が示唆されている．しかし，どのような状況で省略によって安全性が失われてしまうかが明確には示されていない．本稿では，開発者がsubgroup securityの性質をより良く理解できるように，subgroup securityの設定において安全性が失われる具体例を示す．この具体例に対する考察より，我々は，開発者に対して，汎用的かつ容易に暗号方式を安全に実装することができる，本来の群所属判定を使用することを推奨する．性能向上の必要性からsubgroup-secureな楕円曲線を使用し，重い処理を省略したい場合は，この省略により正当性と安全性が失われないかを，再度，注意深く解析しなければならない．

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

著者：
Le Trieu Phong, Tran Thi Phuong

採録先：
IEEE Access

分散型のSGDの通信量を改善するとともに、通信の攻撃に対して比較的robustなアルゴリズムを提案・評価した。

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

著者：
Fuki Yamamoto, Lihua Wang, and Seiichi Ozawa

採録先：
ICONIP2020

本研究では, アンサンブル決定木モデルであるXGBoostに協調学習スキームを導入した, プライバシー保護XGBoostを提案する. Yangらは損失関数の勾配情報を集約することによって, Zhao らは複数のデータ所有者がモデルを順番に更新することによって, 協調学習をXGBoost に適用した. これに対し,複数組織が中央サーバと共有するデータの安全性とAIモデルの性能を両立する改良手法を提案する．提案手法が実際に情報を秘匿したままデータを利活用できているかを検証するため, 安全性の分析とモデルの性能評価を行った.

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

著者：
Kaoru Takemure, Yusuke Sakai, Bagus Santoso, Goichiro Hanaoka, Kazuo Ohta

採録先：
IEICE Trans. Fundamentals

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

著者：
Shuichi Katsumata, Shota Yamada, Takashi Yamakawa.

採録先：
Journal of Cryptology(JoC)

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仮定による構成しか知られていない。
本論文では、X3DHプロトコルに着目し、KEMと電子署名に基づく一般的構成を与える。この系として、初の耐量子X3DHが実現した。

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安全性が担保できるか？等の根源的な問いに対する答えはない。
本研究では、ファジー署名の社会応用を目的とし、片手4本の指から取れる指静脈を利用した際に、効率的かつ安全なファジー署名が構成可能であることを示した。本研究の最大の貢献は、生体情報のエントロピーを計算する新しい確率解析手法を確立したことである。

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

採録先：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

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

採録先：
BMC Bioinformatics

(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

著者：
Shuichi Katsumata,Shota Yamada

採録先：
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$$

著者：
Nuttapong Attrapadung,Takahiro Matsuda,Ryo Nishimaki,Shota Yamada,Takashi Yamakawa

採録先：
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

著者：
Shuichi Katsumata,Ryo Nishimaki,Shota Yamada,Takashi Yamakawa

採録先：
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

著者：
Shuichi Katsumata,Shota Yamada

採録先：
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

採録先：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

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

採録先：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

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

採録先：
Theoretical Computer Science

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

採録先：
IEICE Transactions on Information and Systems

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

採録先：
Theoretical Computer Science

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

採録先：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

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

採録先：
I NDOCRYPT 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

採録先：
International Journal of Computational Intelligence Systems

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

近年、格子を基にする効率的な非対話型ゼロ知識証明（NIZK）が数多く提案されている。格子を基にしているため、これらNIZKは耐量子安全性であるように思われるが、実際これらNIZKは全て「古典」ランダムオラクルモデルのみでしか証明が付いておらず、真に耐量子安全性を示すためには「量子」ランダムオラクルモデル（QROM）で証明を付ける必要がある。しかし、未だQROMの扱いは難しく、上記のような格子に基づくNIZKのQROM安全性はあまり多くがわかっていない。
本研究では、新しく「extractable linear homomorphic commitment」プロトコルを導入し、既存の数多くの格子に基づくNIZKをsemi-genericにQROM安全にする手法を提案する。

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

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

採録先：
CRYPTO 2021

関数型暗号は、メッセージｘを暗号化し、秘密鍵には関数Ｍが対応しており、復号結果としてＭ（ｘ）が得られるような高機能暗号方式である。Mとしてチューリングマシンが扱えるものをチューリングマシンに対する関数型暗号と呼ぶ。本研究では、チューリングマシンに対する関数型暗号を初めて格子仮定のみに基づき設計した。ほかにも、ＮＬという計算クラスに対しても同様の方式を設計した。両方式は、システムセットアップの時に鍵の発行回数に制限がある従来の安全性モデルよりも強い、暗号化時に鍵の発行回数の制限を決めることができるより強い安全性モデルを満たす。提案２方式のうち、後者は前者よりも計算クラスが狭い一方、より強い安全性（適応安全性）を満たす。

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

非対話型秘密計算（NIMPC）とは，入力を持つn人のプレイヤが通信を介さずに関数を計算できる暗号技術である．これまで対称関数や指示関数に対してNIMPCプロトコルの効率化がなされてきた．本研究の成果は三つの部分からなる．まず，対称関数の一般化であるアーベルプログラム(abelian program)に対するプロトコルを提案する．入力がアーベル群G全体に値をとる場合通信量O(|G|(log|G|)^2)を達成し，Beimelら(Crypto 2014)の通信量O(|G|^2n^2)を改善する．さらに入力がサイズd以下の部分集合に値をとる場合には，結託数tに対して通信量(max{n,d})^{(1+o(1))t}|G|(log|G|)^2である．これは，Beimelら(Crypto 2014)の通信量(nd)^{(1+o(1))t}|G|^3を改善し，t=o(log n)かつ|G|=n^{Θ(1)}の場合にはBenhamoudaら(Crypto 2017)の通信量n|G|^{log n+O(1)}も改善する．続いて，線形分類器を表現する関数のクラスを定式化し，このクラスに対して一般的構成より効率の良いプロトコルを初めて提案する．最後に，Benhamoudaら(Crypto 2017)のPSM (Private Simultaneous Messages)プロトコルからNIMPCプロトコルへの変換手法に関して，その要素技術であるメッセージ出力関数に対するプロトコルがNIMPCの安全性を満たさず，攻撃方法が存在することを示す．また，その欠陥を修正するプロトコルも提案する．その系として，指示関数に対して入力のビット長に関して漸近的に最適な通信量を達成するプロトコルを得る．

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

採録先：
IEICE Transactions on Fundamentals of Electronics

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

採録先：
IEICE Transactions on Fundamentals of Electronics

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 Efficient
Building 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

採録先：
Advances in Information and Computer Security, IWSEC 2021, Lecture Notes in Computer Science

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

採録先：
Proceedings of 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

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 Protocols
Based 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

採録先：
EEE Wireless Communications Letters,

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

採録先：
Designs, Codes and Cryptography

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

採録先：
The 8th International Workshop on Information and Communication Security, WICS 2021

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

採録先：
15th International Conference on Provable and Practical Security, ProvSec 2021

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

採録先：
Theoretical Computer Science

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).