MPCの応用：Private Set Intersectionと機械学習

MPCは理論を実用に変えます。Private Set Intersection（PSI）とプライバシー保護MLは、現在、業界で最も広く導入されているMPCアプリケーションの2つです。

PSIでは、Aliceが集合Aを、Bobが集合Bを持ちます。A\BやB\Aに含まれる要素を互いに知られることなく、A∩Bを計算します。GoogleやAppleの接触追跡、広告詐欺の検出、脅威インテリジェンスの共有などに使用されています。

両方の集合をハッシュ化して比較する方法は、集合が小さい場合には安全ではありません。攻撃者がすべての要素を試せるためです。安全なPSIでは、共通部分のサイズさえも隠すか、共通部分だけを公開する必要があります。

Oblivious PRF（OPRF）では、BobはAliceの要素を知らずに、その要素に対してPRFを評価します。Aliceは各x∈AについてPRF(k, x)を取得し、BobがBの各y∈Bについて事前計算したPRF(k, y)と比較します。

Circuit PSIはMPC回路内で共通部分を計算するため、どの項目が共通しているかを明らかにせずに、共通部分の要素に対する追加の計算（購入金額の合計など）を実行できます。

PPMLでは、複数の当事者のデータを使って学習または推論を実行します。Federated learningではデータをローカルに保持しますが、MPCではさらに、モデルや集約された勾配さえも秘密分散します。

Googleが2017年に発表したセキュア集約プロトコルでは、各クライアントが勾配更新を秘密分散します。サーバーが復元するのは合計値だけです。個々の更新値がサーバーを含む誰かに公開されることはありません。

CrypTen（Facebook/Meta）とMOTIONは、秘密分散された入力に対してPyTorch形式のニューラルネットワークを実行できます。線形層は低コストですが、非線形関数（ReLU）にはブール表現から算術表現への変換が必要です。

ReLU(x) = max(0,x)では、xと0を比較する必要があります。これは非線形かつ非算術的な演算であり、garbled circuitまたはビット分解によって実行されます。PPMLにおける最大のコスト要因です。

AppleのPrivate RelayはPSIを使用しています。Metaはプライベート広告計測にMPCを使用しています。IETFのPRIOプロトコル（Firefox Telemetryで使用）は、秘密分散された集計統計を使用しています。

PSIを使うと、当事者間でOPRFを介して集合の共通部分を非公開で計算できます。Circuit PSIでは、共通部分のデータに対して追加の計算を実行できます。PPMLでは、Federated learningの集約や暗号化された入力に対するモデル推論にMPCを使用します。ReLUは、PPMLにおける主なコストボトルネックです。