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

秘匿共通集合計算プロトコル（ひとくきょうつうしゅうごうけいさんプロトコル、Secure Set-Intersection Protocol）では、二人のユーザがそれぞれ秘密の集合を保持しており、お互いにその情報を漏らすことなく、それらの共通集合のみを得ることが可能である。
この方式は、Freedman、Nissim、Pinkasらにより、Eurocrypt2004で発表され、国家間でのテロリストリストの共有などといった多種多様な応用範囲を持つ。
基本的アイデア.
二人の参加者サーバとクライアントがいるものとする。彼らは、それぞれ秘密の情報である集合formula_1とformula_2を保持しており、お互いにそれらを漏らすことなく、formula_3のみを
計算したい。
この方式を実現するために有用となるのは、集合を多項式で表現すること、そして、準同型暗号を利用することである。
ここで利用する準同型暗号には、formula_4とformula_5を与えられたときに、
formula_6を計算できる性質を有することとする。また、この性質を利用すれば、formula_4とformula_8から、
formula_9を計算できることにも注意する。
方式の安全性.
この方式は、利用する準同型暗号がIND-CPAを満たしていれば semi-honestのサーバとクライアントに対して安全であることが示される。
一般化.
KisserとSongは, Crypto2005において、二人参加型ではなく多人数が参加できる秘匿共通集合計算プロトコルを提案した。また、上記方式は、共通集合しか計算できないが、任意の関数に対して上記のような方式を実現するフレームワーク(Garbled Circuit)が、Andrew Yaoにより提案されている。