はじめに
こちらの記事では、ブール回路を逐次的に安全評価するプロトコルであるGMWプロトコルの解説です。
MPC Overviewページ <- ここにMPC各記事へのリンクがあります。
GMWプロトコル
Goldreich–Micali–Wigderson (GMW) プロトコルは、秘密分散に基づき任意人数で計算可能な汎用プロトコルです。Bool回路でも、算術回路でも計算可能です。
考え方はシンプルで、入力を秘密分散（secret sharing）し、その分散された値のまま回路計算を進める方式です。
以下おおまかな内容です。
- ワイヤ値をXOR分散または加法分散で共有：
$$
[x] = x_1 \oplus x_2 \oplus \dots \oplus x_n
$$
- $x_i$がそれぞれシェアになっていて単独ではxはわからない。
- XORゲートは通信不要でローカル計算可能。
- ANDゲートはOTを用いて評価。各ゲートで1ラウンド通信が必要。
通信ラウンド数は 回路深さ に比例するため、深い回路では遅延が支配的になります。
XORの例
1. 前提：入力のシェア
各パーティは、自分の入力をランダムなビットでマスクして相手とシェアします。
-
P1 の秘密にしたい入力を $x$、P1が決めたランダム値を $r$ とし、$r$をP2に渡します。それぞれをxに関するP1、P2のシェアと定義します。
- P1 のシェア： $s^x_1 = x \oplus r$
- P2 のシェア： $s^x_2 = r$
つまり、以下の計算で元に戻せます。
$$
x = s^x_1 \oplus s^x_2
$$ -
同様にP2 の入力を $y$、ランダム値を $r'$ とすると：
- P1 のシェア： $s^y_1 = r'$
- P2 のシェア： $s^y_2 = y \oplus r'$
2. XORゲートの評価
$$
z = x \oplus y
$$
を計算したいとします。
各パーティは 自分のシェア同士を XOR するだけ で計算が完了します。
-
P1:
$$
s^z_1 = s^x_1 \oplus s^y_1 = (x \oplus r) \oplus r'
$$ -
P2:
$$
s^z_2 = s^x_2 \oplus s^y_2 = r \oplus (y \oplus r')
$$
この時点ではまだ$x \oplus y$の値はわかりません。
3. 出力の復元
両者のシェアを XOR すると：
$$
s^z_1 \oplus s^z_2
= \bigl( (x \oplus r) \oplus r' \bigr) \oplus \bigl( r \oplus (y \oplus r') \bigr) \
= x \oplus y \oplus r \oplus r' \oplus r \oplus y \oplus r' \
= x \oplus y
$$
$r$ と $r'$ が打ち消し合い、正しい出力 $x \oplus y$ が得られます！
XORだけであればこの計算をしてしまうと相手の入力が分かってしまいますが、このようなゲートがたくさん連なることで相手の入力は分からない状態で出力だけを計算できます。
ANDの例
ANDの場合は、XORと違ってP1とP2で通信が必要です。
$$
z = x \land y
$$
つまり、
$$
z = (s^x_1 \oplus s^x_2) \land (s^y_1 \oplus s^y_2)
$$
これを展開すると、
$$
z =
(s^x_1 \land s^y_1)
\oplus (s^x_1 \land s^y_2)
\oplus (s^x_2 \land s^y_1)
\oplus (s^x_2 \land s^y_2)
$$
ここで各項を見ると👇
| 項 | 内容 | 誰が計算できるか |
|---|---|---|
| $s^x_1 \land s^y_1$ | P1の情報だけ | ✅ P1 が計算可能 |
| $s^x_2 \land s^y_2$ | P2の情報だけ | ✅ P2 が計算可能 |
| $s^x_1 \land s^y_2$ | P1のシェアとP2のシェア | ❌ どちらも単独では不可 |
| $s^x_2 \land s^y_1$ | P1のシェアとP2のシェア | ❌ どちらも単独では不可 |
つまり
- P1は $s^x_1$ は知っているが $s^y_2$ は知らない
- P2は $s^y_2$ は知っているが $s^x_1$ は知らない
そのためどうにかして相手の情報を知る必要があります。
P1の手順（送信側）
-
ランダムなビット $r''$ を生成
$$
t_1 = r'' \quad \text{(P1 の出力シェア)}
$$ -
P2 のシェア $(s^x_2, s^y_2) \in {(0,0),(0,1),(1,0),(1,1)}$ に対して
P2の入力ごとの結果をテーブル化：\begin{align} (0,0):& \space r'' \oplus (s^x_1 \land s^y_1) \\ (0,1):& \space r'' \oplus (s^x_1 \land \neg s^y_1) \\ (1,0):& \space r'' \oplus (\neg s^x_1 \land s^y_1) \\ (1,1):& \space r'' \oplus (\neg s^x_1 \land \neg s^y_1) \\ \end{align} -
この4行を OT の送信メッセージとして準備。
P2の手順（受信側））
- P2 は $(s^x_2, s^y_2)$ を知っている。
- そのペアに対応する 1 行だけを 1-out-of-4 OT で受信：
$$
t_2 = \text{table}[s^x_2, s^y_2]
$$
- P1 はどの行を選んだか知らない。
- P2 は他の行の情報を得られない。
出力のシェア
- P1 の出力シェア： $t_1 = r''$
- P2 の出力シェア： $t_2$（OTで取得）
$$
t_1 \oplus t_2 = x \land y
$$
これにより、ANDゲートの出力が$P_1$ と $P_2$ に分散された形で得られます。
以上がGMWプロトコルです。