EAGLYSアドベントカレンダー５日目の記事です。PSIという秘密計算技術のひとつについてざっくり解説したいと思います。
#秘匿共通集合演算（Private Set Intersection）とは
秘匿共通集合演算（長いので以降PSIとします）は秘密を漏らさず共通集合演算の結果だけを得られる秘密計算手法です。例えば、アリスが集合$X=\{x_1,x_2,\dots,x_n\}$とボブが集合$Y=\{y_1,y_2,\dots,y_m\}$を持っていて、$X\cap Y$を計算したいとします。この時、$X\cap Y$以外の情報は漏らしたくありません。
さて、この問題へのソリューションとして、Freedman,Nissim,PinkasはEEfficient Private Matching and Set IntersectionでPSIを提案しました。PSIとは
-
アリスの持つ集合$X$とボブの持つ集合$Y$について$X\cap Y$を計算する。
-
$X\cap Y$をアリスが得る。
-
ボブは何の情報も得られない。
というプロトコルです。医療や顧客データなどの個人情報を開示せずに計算に利用できます。データベース上の計算において集合演算は幅広く活用されているので、
#PSIプロトコル
PSIが実際にどう実現されているのか見てみます。この方式では加算準同型性を持つ暗号を使います。加法準同型暗号としてはPaillier暗号が有名です。暗号化したまま、暗号状態での加算と定数での乗算が出来ます。例えば、平文を$m_1,m_2$で定数を$C$とし、その準同型暗号化を$Enc(m_1),Enc(m_2)$とします。この時、次の性質を持っています。
$$
Enc(m_1+m_2)=Enc(m_1)+Enc(m_2)
$$
$$
C\cdot Enc(m_1) = Enc(C\cdot m_1)
$$
この性質を使い、次数kの多項式Pの係数がk個あり、平文yの知識があればP(y)が計算できるというように利用します。
以下にFreedmanらのPSIプロトコルの構成方法をあげます！
- アリスは次のような多項式$P(y)$を生成し、その$n+1$個の係数$\alpha_0,\dots,\alpha_{n}$を暗号化してボブに送る
$$
P(y) = (x _ 1 - y)(x _ 2 - y)\dots (x _ n - y) = \Sigma _ {i=0} ^ {n} \alpha _ i y ^ i
$$
- ボブは$y_j \in Y$について以下の計算を行い、多項式$P$を暗号化された$Enc(P(y))$のまま評価する。
$$
(Enc(\alpha _ n) \cdot y_j ^ {n} ) +(Enc(\alpha _ {n-1}) \cdot y ^ {n-1} _ j )+ \dots+(Enc(\alpha _ 1)\cdot y _ j)+Enc(\alpha _ 0)=Enc(P(y _ j))
$$
-
ボブは$y_j \in Y$について、$rEnc(P(y_j))+Enc(y_j)=Enc(rP(y_j)+y_j)$を計算して、ランダムに並び替えてアリスに送る。
-
アリスは受け取った暗号文を復号し、$m=Dec(Enc(r*P(y_j)+y_j))$とする。$m\in X$である$m$を全て出力する。
上の式が秘密を漏らさずに共通集合を計算できる仕組みを説明します。まず、ボブの入力$X$とアリスの入力$Y$に共通したものがあれば、
$$
P(y_j) = (x _ 1 - y_j)(x _ 2 - y_j)\dots (x _ k - y_j) = \Sigma _ {i=0} ^ k \alpha _ i y_j ^ i
$$
の因数のうちどれかが$0$になっているはずです。例えば、$x_1=y_j$なら
$$
(x _ 1 - y)(x _ 2 - y)\dots (x _ n - y)=0(x _ 2 - y)\dots (x _ n - y)=0
$$
です。つまり$r \cdot P(y _ j)$は0になるので、等しいものがあったときに限り、
$$
Enc(r \cdot P(y _ j) + y _ j )=Enc(y _ j)
$$
です。乱数$r$をかけているので、$r \cdot P(y _ j)$は$0$にならない限り乱数なので、$r \cdot P(y _ i)+y_i$も乱数となり秘密を漏らしません。
ボブが自分の入力すべてに対して、計算をした後に結果をアリスに全て送り返す。アリスは秘密鍵を使って、復号してみると自分の入力と等しい値がいくつか出てくるはずです。その等しい値が交点となります。
PSIのバリエーション
PSIは2004年からさかんに研究されており、ただ共通集合を演算するだけではない応用手法が登場しています。以下はそれについていくつか例をあげています。
Private Set Intersection Cardinaliry(PSI-CA)
PSI－CAとは共通集合や部分集合の要素集合ではなく、その大きさ（つまり濃度）を得るプロトコルです。PSIのように、要素そのものの値は分かりません。Honest-Verifier Private Disjointness Testing without Random Oraclesなどで提案された手法です。つまり、アリスの持つ情報の集合$X$、ボブが持つ情報の集合$Y$を入力したとき、
$$
|X \cap Y|
$$
だけを出力します。
MPSI
ここまでの手法でアリスとボブの二者間が基本でした。MPSIは集合演算を三者以上で行える方式です。Privacy Preserving Set Operationsの論文で提案された手法です。和集合、共通集合などに対するマルチパーティ計算プロトコルを提案しました。
Private intersection-sum with cardinality
Private intersection-sum with cardinalityとはPSI-CAの機能に加え、共通集合に属する要素に関連づけられた値の和を算出するプロトコルです。例えば、アリスの持つ情報の集合$X$、ボブが持つ情報の集合$Y$とします。各要素$x_i \in X$には$v_{x_i}$という統計情報が関連付けられているとしましょう。次の計算結果を出力します。
$$
|X \cap Y|,\Sigma_{x_i \in X \cap Y} v_{x_i}
$$
例えば、ECサイトAの利用者リストを$X$とし、統計データ$V$とします。アリスの家族$X=\{x_1,x_2,x_3,x_4\}$として共通集合を計算します。すると、アリスの家族が全員利用していればその計算結果は$\{v_{x_1},v_{x_2},v_{x_3},v_{x_4}\}=\{100,1000,200,300\}$だったら
$$
|X \cap Y|=\{x_1,x_2,x_3,x_4\},\Sigma_{x_i \in X \cap Y} v_{x_i}=1600
$$
となる。このように特定のグループに関する統計情報が得たい場合などに利用できます。
まとめ
今回は秘密計算手法のひとつであるPSIについて解説しました。ただ共通集合を演算するだけのプロトコルですが、その応用の幅広さから研究がさかんです。現在は非常に高速な方式としてFaster Private Set Intersection Based on OT ExtensionやPhasing: Private Set Intersection using Permutation-based Hashingも提案されており、実用も近いのではないかと思います！
#参考
Efficient Private Matching and Set Intersection
Privacy Preserving Set Operations
Fast and Private Computation of Cardinality of Set Intersection and Union
Honest-Verifier Private Disjointness Testing without Random Oracles
Faster Private Set Intersection Based on OT Extension
Practical Private Set Intersection Protocols with Linear Complexity
[3 暗号理論の応用 3-1 高速秘匿共通集合計算プロトコルの設計方法について]
(https://www.jstage.jst.go.jp/article/nictkenkyuhoukoku/54/2.3/54_9/_pdf)