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と関連付けられ、復号は属性xがポリシー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

著者:
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と関連付けられ、復号は属性xがポリシー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

採録先:
TCS

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

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

採録先:
IEICE Trans. Fundamentals

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