MPC問題とYaoの秘匿回路

MPCでは、各自が秘密の入力x_iを持つn者が、互いの入力を明かさずにf(x_1,...,x_n)を共同で計算できます。あたかも信頼できる第三者が計算したかのように実行できます。

Yaoが1982年に提案したMillionaires' Problemでは、AliceとBobが資産額を明かさずに、どちらが裕福かを知ろうとします。信頼できる第三者は存在しません。MPCは暗号学的な保証によってこの問題を解決します。

1. プライバシー：参加者が知るのは出力と、そこから推測できる情報だけです。2. 正しさ：一部の参加者が不正であっても、出力は正しくなります。3. 半正直な攻撃者を想定する場合と悪意のある攻撃者を想定する場合で、さまざまな方式があります。

任意の関数は、ブール回路（AND、XOR、NOTゲート）で表現できます。MPCプロトコルは回路レベルで動作し、各ゲートを安全に評価することがよくあります。

Alice（garbler）は各ワイヤーに、0用と1用の2つのランダムなラベルを割り当てます。各ゲートの真理値表を、入力ワイヤーのラベルで暗号化します。Bob（evaluator）はOblivious Transferを通じて、自分の入力に対応するラベルだけを取得します。

Bobはgarbled table（ANDゲートごとに4つの暗号文）を受け取ります。入力ラベルを使って正しい1行だけを復号し、出力ラベルを取得します。そのラベルが0を表すか1を表すかを知ることはありません。

各ラベルにランダムな「select bit」を付加します。Bobはselect bitを使って、4つすべての復号を試す代わりに、O(1)で正しいgarbled rowを見つけます。計算量を4分の1に削減できます。

KolesnikovとSchneider（2008）は、グローバルオフセットΔを選択する方式を提案しました。すべてのワイヤーについてlabel_1 = label_0 ⊕ Δとします。これによりXORゲートが暗号化不要で処理でき、帯域幅を約30%削減できます。

Zahurら（2015）により、各ANDゲートに必要な暗号文が4つから2つになりました。Free-XORと組み合わせることで、標準的なgarbled circuitの帯域幅を半分にできます。

古典的なgarbled circuitは2者向けです。マルチパーティ拡張（例：BMRプロトコル）では、すべての参加者が並列にgarblingを行いますが、O(n²)の通信が必要です。参加者数nが少ない場合に実用的です。

Yaoのgarbled circuitプロトコルでは、Bobは自分の秘密の入力ビットに対応するワイヤーラベルをどのように取得しますか。

MPCを使うと、参加者は入力を明かさずに共同で計算できます。Garbled circuitはブール関数を暗号化された真理値表として符号化します。Free-XOR、Half-Gates、Point-and-Permuteなどの最適化により、実用的な性能が得られます。OTによって、Bobの入力ラベルが秘密裏に届けられます。