秘匿共通集合計算プロトコル（ひとくきょうつうしゅうごうけいさんプロトコル、Secure Set-Intersection Protocol）では、二人のユーザがそれぞれ秘密の集合を保持しており、お互いにその情報を漏らすことなく、それらの共通集合のみを得ることを可能とする。この方式は、Freedman, Nissim, Pinkasらにより、Eurocrypt 2004で発表され、国家間でのテロリストリストの共有などといった多種多様な応用範囲を持つ。二人の参加者サーバとクライアントがいるものとする。彼らは、それぞれ秘密の情報である集合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により提案されている。

出典:wikipedia