秘匿共通集合計算プロトコル

秘匿共通集合計算プロトコル（ひとくきょうつうしゅうごうけいさんプロトコル、Secure Set-Intersection Protocol）では、二人のユーザがそれぞれ秘密の集合を保持しており、お互いにその情報を漏らすことなく、それらの共通集合のみを得ることが可能である。この方式は、Freedman、Nissim、Pinkasらにより、Eurocrypt2004で発表^[1]され、国家間でのテロリストリストの共有などといった多種多様な応用範囲を持つ。

基本的アイデア

二人の参加者サーバとクライアントがいるものとする。彼らは、それぞれ秘密の情報である集合 $S$ と $C$ を保持しており、お互いにそれらを漏らすことなく、 $C\cap S$ のみを計算したい。この方式を実現するために有用となるのは、集合を多項式で表現すること、そして、準同型暗号を利用することである。ここで利用する準同型暗号には、 ${\rm {Enc}}(m_{1})$ と ${\rm {Enc}}(m_{2})$ を与えられたときに、 ${\rm {Enc}}(m_{1}+m_{2})$ を計算できる性質を有することとする。また、この性質を利用すれば、 ${\rm {Enc}}(m_{1})$ と $k$ から、 ${\rm {Enc}}(km_{1})$ を計算できることにも注意する。

方式の構成

クライアントは、準同型暗号の公開鍵・秘密鍵対 $(pk,sk)$ を生成し、公開鍵のみを公開する。続けて、 $c_{i}\in C$ に対して、 $P(X)=(X-c_{1})(X-c_{2})\cdots (X-c_{|C|})=a_{|C|-1}X^{|C|-1}+\cdots +a_{0}$ を計算する。それら係数を暗号化して、サーバにおくる。
サーバは、準同型性を利用して、全ての $s\in S$ に対して、 $rP(s)+s$ の暗号文を計算する。ここで $r$ は乱数であり、各 $s$ に対して異なるものを選ぶ。
クライアントは全ての暗号文を復号し、復号したものが $C$ に含まれているならば、その値を出力する。

方式の安全性

この方式は、利用する準同型暗号がIND-CPAを満たしていれば semi-honestのサーバとクライアントに対して安全であることが示される。

一般化

KisserとSongは, Crypto2005において、二人参加型ではなく多人数が参加できる秘匿共通集合計算プロトコルを提案した。また、上記方式は、共通集合しか計算できないが、任意の関数に対して上記のような方式を実現するフレームワーク(Garbled Circuit)が、Andrew Yaoにより提案されている。

参考文献

^ Michael J. Freedman, Kobbi Nissim, Benny Pinkas: Efficient Private Matching and Set Intersection. EUROCRYPT 2004: 1-19

[1]