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