はじめに
こちらの記事では、MPCの基礎となるプロトコルであるOblivious TransferとGarbled Circuitsを解説していきます。
MPC Overviewページ <- ここにMPC各記事へのリンクがあります。
Oblivious Transfer (OT)
登場人物
-
Alice（送信者）：2つのメッセージ
m0,m1を持っている -
Bob（受信者）：どちらか1つだけ欲しい（例：
m1）
基本アイデア
Bob は「どっちが欲しいか」を Alice に知られずに伝えるために、
公開鍵暗号をうまく使って“鍵”を渡す。
Alice はその鍵を使ってメッセージを暗号化。
Bob だけが、選んだ1つだけを復号できるようになる。
プロトコルの流れ
① Bob が鍵を準備
- Bob は「選択」を隠したまま公開鍵を2つ作る。
- そのうち、1つは自分が秘密鍵を持っている鍵。
- もう1つはダミー。
- Alice からは、どっちが本物か分からないようになっている。
👉 Bob はこの2つの公開鍵を Alice に送る。
② Alice がメッセージを暗号化
- Alice はそれぞれの公開鍵で
m0とm1を暗号化。 - どっちの鍵で暗号化されたかは Bob しかわからない。
👉 Alice は2つの暗号文を Bob に送る。
③ Bob が選んだ1つだけ復号
- Bob は自分が秘密鍵を持っている方の暗号文だけを復号。
- もう一方は鍵を知らないので開けられない。
👉 Bob は m_b（選んだ1つ）だけを受け取れる。
ここでのポイント
Alice: Bob は1つしか復号できないので1つしか値がバレない
Bob: Alice に「どちらを選んだか」がバレない
※ 両方知ってる公開鍵を渡せば両方復号できますが、以下のようにすることで片方の秘密鍵しか知らないことを保証します。
- $g^a$ は Aliceが選んだ公開値（これをBobに送る）
- Bobは選択ビット $b \in {0,1}$ に対して以下を送る
- $PK_b = g^k$（秘密鍵 $k$ を 知っている）
- $PK_{1-b} = g^{a-k}$（離散対数問題より受け取った$g^a$からaが計算できないので、秘密鍵に対応する$a-k$は分からない）
Yao’s Garbled Circuits (GC)
YaoのGCは2者MPCの代表的プロトコルです。ある2者が互いの入力を知らずに回路の出力を得ることができます。
定数ラウンドで動作するため、レイテンシが高い環境でも高速に実行可能です。garbleは音声とかメッセージを歪めるという意味の動詞で、文字化けとかいう意味もあるそうです。なので入出力を外から見た時にわからなくするような回路ということですね。
以下プロトコルの流れです。
前提：登場人物
- Alice（ガーブラー）: 回路を「ガーブル化」して送る側。自分の入力も持つ。
- Bob（評価者）: ガーブル化された回路を受け取り、評価する側。自分の入力も持つ。
ステップ1〜2はAliceが単独で行う事前処理です。
ステップ1: 鍵の割当（Aliceが行う）
Aliceは、回路の各ワイヤー $w$ に対して2つのランダムな鍵を生成する。
$$K_w^0, \quad K_w^1$$
$K_w^0$ はワイヤーの値が $0$ のとき、$K_w^1$ は $1$ のときに対応する。
つまり、例えばワイヤーがANDゲートの入力で、実際の値が 0 だった場合、そのワイヤーには$K_w^0$が割り当てられます。
これをBobが受け取ってもそれが0に対応する鍵なのか、1に対応する鍵なのかはわかりません。
ステップ2: ガーブル化（Aliceが行う）
Aliceは、各ゲート $g: {0,1}^2 \to {0,1}$ に対し、ガーブルドテーブルを作成する：
$$
C_{a,b} = \text{Enc}_{K_x^a, K_y^b}\left( K_z^{g(a,b)} \right),
\quad (a,b \in {0,1})
$$
- $x, y$：ゲートの入力ワイヤー、$z$：出力ワイヤー
- 4通りの $(a,b)$ の組み合わせに対して暗号文を作るため、テーブルは4行になる。
- 行の順序はシャッフルして送る（どの行が何の入力に対応するかをBobに隠すため）。
作成したガーブルドテーブルをAliceはBobに送る。
| 入力ペア (a, b) | 暗号文 |
|---|---|
| (0, 0) | $Enc_{K_x^0, K_y^0}( K_z^{g(0,0)} )$ |
| (0, 1) | $Enc_{K_x^0, K_y^1}( K_z^{g(0,1)} )$ |
| (1, 0) | $Enc_{K_x^1, K_y^0}( K_z^{g(1,0)} )$ |
| (1, 1) | $Enc_{K_x^1, K_y^1}( K_z^{g(1,1)} )$ |
※ 実際にBobに渡すときは行をシャッフルするため、どの行が (0,0) に対応するかはBobにはわからない。
ステップ3: 入力の共有
- Aliceの入力: Aliceは自分の入力ビットに対応する鍵を直接Bobに送る。
- Bobの入力: BobはOblivious Transfer（OT）を使い、自分の入力ビットに対応する鍵だけを取得する。このときAliceはBobの入力値を知ることができない。
ステップ4: 評価（Bobが行う）
Bobはゲートごとにステップ3で得た鍵のペアを使って復号を実行する：
$$
(K_x^a, K_y^b) \rightarrow K_z^{g(a,b)}
$$
4行のテーブルのうち、手持ちの鍵ペアで復号できるのは常に1行だけ（それ以外は復号失敗）。こうして出力ワイヤーの鍵を順に得ていく。
ステップ5: 出力解釈
Bobが最終的に得るのは出力ワイヤーの鍵 $K_\text{out}^v$。しかしBobはそれが $0$ に対応するのか $1$ に対応するのかを知らない。
AliceがBobに「$K_\text{out}^0$ が $0$、$K_\text{out}^1$ が $1$」という対応表を送ることで、Bobはじめて出力値 $v$ を解釈できる。
要点をまとめると：ステップ1・2はAliceが事前にすべて準備し、ステップ3でBobに渡すという流れです。
具体例：ANDゲート
鍵割当
- 入力 $A$: $K_A^0, K_A^1$
- 入力 $B$: $K_B^0, K_B^1$
- 出力 $C$: $K_C^0, K_C^1$
ガーブルドテーブル
- $C_{0,0} = \text{Enc}_{K_A^0, K_B^0}(K_C^0)$
- $C_{0,1} = \text{Enc}_{K_A^0, K_B^1}(K_C^0)$
- $C_{1,0} = \text{Enc}_{K_A^1, K_B^0}(K_C^0)$
- $C_{1,1} = \text{Enc}_{K_A^1, K_B^1}(K_C^1)$
（これをシャッフルしてBobへ渡す）
Bobの評価例
- 入力が $A=1, B=0$ のとき、Bobは鍵 $(K_A^1, K_B^0)$ を持っている。
- Aliceが選んだ鍵はそのままもらう（ここでBobはそれが0/1どちらに対応した鍵かは分からない）
- Bobは自分で0/1を選んでOTでどちらかに対応する鍵をもらう（この時AliceはBobが0/1どちらの鍵を手に入れてかは分からない）
- 復号できるのは $C_{1,0}$ だけ → 出力鍵 $K_C^0$ を得る。
- $(K_A^1, K_B^0)$が鍵になっているので、これでガーブルドテーブルで受け取った暗号をそれぞれ復号する
- 復号できるのは1つだけ（それ以外は復号処理がうまくいかない）
- Bobは$K_C^0$だけ受け取るが、この時点もまだそれが0/1なのかは分からない
- 最後に対応表から $K_C^0 \mapsto 0$ と判明。
ポイント
ポイントとしては、一般に使われるゲートは存在しないということです。例えがANDゲートと言われたらゲート自体は入力に対する結果を返してくれると思うのですが、ここではそんな物理ゲートは存在せずに、暗号テーブル（ガーブルドテーブル）から値を得るっていう流れです。
また、ゲートが1つだけだと最終的に対応表で0/1分かってしまったら相手の入力分かってしまうことあると思いますが、途中までは全て鍵だけで計算して最後だけ対応表を用いれば相手の入力を推定することはできません。
まとめ
OTやGarbled Circuitはよく出てくるので、この辺理解できてると良いと思います。