秘匿共通集合

2023年3月10日 #MPC #PSI #OPRF

概要

秘匿共通集合 (private set intersection, PSI) は 2 つパーティがそれぞれで保持しているデータ集合の情報を相手に明かすことなく共通集合 (交差) を見つけることのできる暗号技術。交差に含まれない要素は秘匿されたままであることから二者間のデータプライバシー保護が重要なケースにおいて有用である。

PSI の応用範囲は広く、例えば Apple や Google, Microsoft ではユーザの入力したパスワードが漏洩パスワードリストに含まれているかどうかを (ユーザ入力や漏洩リストを明かすことなく) 確認するために PSI を使用している。また共通するヒトゲノム、ボットネットアクセスの検出、病院間で共通する患者の特定といった取り扱いに慎重を要するデータ検索の分野にも応用することができる。

PSI には多様なプロトコルがある。最近では暗号論的マルチパーティ計算の分野の一つとして活発に研究されている。また Microsoft Edge の漏洩パスワード検出は準同形暗号を使用した SPI である。一方で Signal の開発者は SPI では遅すぎると判断して Intel SGX を使用した trusted third-party を構築する方法を選んでいる。

概要
ナイーブハッシング
紛失疑似乱数関数を使う方法
参考文献

ナイーブハッシング

もっとも単純な PSI はデータ集合の要素をハッシュ化して交換する方法である。Alice と Bob がそれぞれデータ集合 \(A=\{a_1,\ldots,a_n\}\), \(B=\{b_1,\ldots,b_m\}\) を持っているとき、共通のハッシュ関数 \(h\) を用いて \(h:a_i \mapsto \alpha_i\), \(h:b_j \mapsto \beta_j\) のように変換し、\(\alpha_i=\beta_j\) となる要素を見つける。ここで Alice は \(\alpha_i\) に対する \(a_i\) を知っているため、共通要素が何であったかを知ることができるが、それ以外の要素についての情報を得ることはできない。Bob についても同様である。

ナイーブハッシングは簡単だが、双方がハッシュ関数 \(h\) をいつでも利用できるためオフラインでのブルートフォース攻撃に対して安全ではない。また大きなデータ集合に対しては計算量と転送データ量がかなり大きくなる可能性がある。

紛失疑似乱数関数を使う方法

文献 [1] では紛失疑似乱数関数 (oblivious pseudorandom function; OPRF) を使って PSI の仕組みを説明している。この方法は一方のパーティでのみ暗号化 (ハッシュ化) を行うためオフラインでブルートフォース攻撃を行うことはできない。

OPRF は秘匿化 (ブラインド) された入力から秘匿化された乱数を生成する決定論的な疑似乱数関数である。ここで入力の秘匿化に使用したブラインドファクターを使わなければ乱数の値を解読できないという特徴がある。

Fig 1 は Alice が入力 \(x\) を明かすことなく Bob の OPRF を使って乱数 \(y\) を得る操作を表している。

Alice は入力 \(x\) とブラインドファクター \(z\) を使って秘匿化した \(x'\) を算出し Bob に送信する。
Bob は鍵 \(S\) を使って \(x'\) から秘匿化された疑似乱数 \(y'\) を算出し Alice に送信する。
Alice は \(x\) に対する疑似乱数 \(y\) をブラインドファクター \(z\) を使って \(y'\) から算出する。

ここで \(y = {\rm OPRF}(x,S) = {\rm unblind}({\rm OPRF}({\rm blind}(x, z), S), z)\) となることに注意。

この手順では Bob は Alice の入力値 \(x\) や乱数 \(y\) を知ることはできず、また Alice には Bob が使用した鍵 \(S\) を知ることもできない。文献 [1] の説明では \({\rm OPRF}()\) に HMAC に似た疑似乱数関数を想定している。

Oblivious Pseudo-Random Function — Fig 1. Alice が \(x\) を明かすことなく Bob の紛失疑似乱数関数を使って乱数 \(y\) を得る。

OPRF のスキームを使うと次のように互いのデータ集合を明かすことなく Alice が共通のデータを得ることができる。Fig 2 はこの一連の手順を表している。

Alice はブラインドファクター \(z\) を使って自身のデータ集合 \(A=\{a_1,\ldots,a_n\}\) を秘匿化した \(A'=\{a'_1,\ldots,a'_n\}\) を算出し Bob に送信する。
Bob は鍵 \(S\) を使って秘匿化されたデータ集合 \(A'\) から疑似乱数集合 \(\mathcal{A}'=\{\alpha'_1,\ldots,\alpha'_n\}\) を算出し Alice に送信する。
Alice はブラインドファクター \(z\) を使って \(\mathcal{A}'\) から疑似乱数集合 \(\mathcal{A}=\{\alpha_1,\ldots,\alpha_n\}\) を算出する。
Bob は鍵 \(S\) を使って自身のデータ集合 \(B=\{b_1,\ldots,b_m\}\) に対する疑似乱数集合 \(\mathcal{B}=\{\beta_1,\ldots,\beta_m\}\) を算出し Alice に送信する。
Alice は \(A\) と \(B\) の共通要素を \(\mathcal{A} \cap \mathcal{B}\) によって知ることができる。

この手順では Alice のみがデータ集合の共通要素を知ることができる。ただし文献 [1] では秘匿化や OPRF のための具体的なアルゴリズムはなくスキームの説明のみである。