GMWプロトコルとOblivious Transfer

Goldreich-Micali-Wigderson（GMW）プロトコルは、XOR秘密分散を使ってブール回路を評価します。各ワイヤーの値はすべての参加者に分散され、ゲートごとに対話しながら処理されます。

参加者iは、s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w（真のワイヤー値）となるシェアs_iを保持します。XORゲートは無料です。各参加者が自分のシェアをローカルでXORするだけで済みます。

ワイヤーa,bに対するANDゲートでは、(a_1⊕a_2)(b_1⊕b_2)を展開すると交差項が現れます。参加者i≠j間の交差項a_i·b_jを評価するには、Oblivious Transferが必要です。

1-out-of-2 OTでは、送信者がメッセージ（m_0, m_1）を持ち、受信者が選択ビットcを持ちます。受信者はm_cを取得し、送信者はcを知りません。受信者はm_{1-c}を知ることができません。

Diffie-Hellmanに基づく方式です。受信者は2つの公開鍵を生成し、そのうち1つについてだけ離散対数を知っている状態にします。送信者は各メッセージをいずれか一方の鍵で暗号化します。受信者は選択した暗号文だけを復号できます。

Ishaiら（2003）は、k個のベースOTから、対称鍵演算だけを使ってm >> k個のOTを生成する方式を提案しました。IKNP extensionでは、1回限りのセットアップ後、OT 1回あたり約3回のAES呼び出しまでコストを削減できます。

各ANDゲートには、参加者の各ペアにつき1回のOTが必要です。OTをオフラインフェーズですべて事前計算しておけば、オンラインフェーズではゲートごとに1回のXOR交換だけで済みます。

半正直なGMWは、ゼロ知識証明またはcut-and-choose OTを使って、悪意のある攻撃者に対して安全な方式にできます。コストは3～8倍に増加しますが、不正を行う参加者に対する安全性が保証されます。

MASCOT（Kellerら）は、OTを拡張して悪意のあるモデルで認証付きANDトリプルを生成し、SPDZプロトコルを可能にします。このプロトコルについては次のレッスンで扱います。

EMP-toolkitとMOTIONは、OT extensionを用いたGMWを実装しています。LAN経由で2者間に毎秒数百万個のANDゲートを処理でき、実際のアプリケーションを実現可能にしています。

GMWプロトコルで、XORゲートが参加者間の通信を必要としないのはなぜですか。

GMWは、ブール回路上でXOR秘密分散を使用します。XORゲートは無料ですが、ANDゲートにはOTが必要です。OT extensionによってOTのコストを下げられます。悪意のある攻撃者への安全性を加えるには、ZKPまたはcut-and-chooseを使用します。EMPなどのライブラリにより、実際のアプリケーションに必要な実用的なスループットを実現できます。