Garbled circuitを理解する

Yao's Millionaires' Problem（ヤオの富豪問題）

https://en.wikipedia.org/wiki/Yao's_Millionaires'_problem

2人の富豪がいて、お互いの財産額を開示することなく、どちらの財産がより多いかを知るにはどうすればよいか？

1982年に提唱された有名な秘密計算の問題です。

この問題への解決策の1つがGarbled circuitです。

Garbled circuitとは

これはMPC（Multi-Party Computation）の特殊なケースである2-Party Computationでのプロトコルです。

このプロトコルは大小問題に限らず論理回路$f(x,y)$について、互いに入力値を知ることなく結果を得ることができます。

ヤオの富豪問題は、この論理回路が$f(x, y) = x > y$のケースとなります。

Oblivious Transferとは

Garbled circuitを理解するうえで非常に重要なのがOblivious Transfer（OT）プロトコルです。

本記事ではOTの原理については触れず、Garbled circuitの理解に必要な性質の紹介のみにとどめますが、OTを用いることで、

• 送信者が2つの値を用意したとき、受信者はそのうち片方のみを取得できる
• 送信者は、受信者がどちらを選んだかを知ることができない

という状態を満たすことができます（1-out of-2 OTと呼ばれます）。

この「2つの値のどちらかを選ぶ」という部分、01で表現されるビットと非常に相性がよいです。

つまり、お互いの入力値をビット列に分解することで、各ビットについてOTを応用したやり取りができそうです。

大小比較の論理回路

まずは入力値の秘匿を抜きにして、数値をビットに分解して大小比較をする手順を考えていきましょう。

2つの数値の大小は、最上位のビットから順に見ていって、最初にビットの異なるものを見つければ判定できます。

たとえば5と7であれば、2ビット目が異なるため、より大きい数値は7であることが分かります。

5 -> 0101
7 -> 0111
       ^

そこで、以下のような変数を考えます。

• $E_i$：上位$i$ビットがすべて等しい（Equal）
• $G_i$：$x>y$ である（Greater）

これらの変数を用いて、$x>y$であるかどうかを漸化式の形で表現できそうです。

初期条件

ビット表現に変換していきます。

• $x = y$は、$\lnot(x \oplus y)$
• $x > y$は、$x \land \lnot y$

と表現できます。

つまり、最上位ビットを$i=n$として、以下が成り立ちます。

• $E_3 = \lnot(x_3 \oplus y_3)$
• $G_3 = x_3 \land \lnot y_3$

今回は4ビットなので0-indexedで$i=3$です。
これは最上位ビットにおける単純な比較に対応しています。

漸化式

ビット$i$に対して以下が成り立ちます。

• $E_i = E_{i+1} \land \lnot(x_i \oplus y_i)$
• $G_i = G_{i+1} \lor (E_{i+1} \land (x_i \land \lnot y_i))$

つまり上位のbitから見ていって、$x>y$であればその時点で確定、そうでなければ次のbitで同じように比較するということですね。

論理ゲートの構築

具体的にすべての01のパターンについて列挙してみましょう。

最上位ビット

$x_3$	$y_3$	$E_3$	$G_3$
0	0	1	0
0	1	0	0
1	0	0	1
1	1	1	0

$(E_3, G_3) = (1,0), (0,0),(0,1)$の3パターンのみです。

数値が同じなのにどちらかが大きくなることはありえないため、$(E_3, G_3) = (1,1)$のパターンは存在しません。

以降のビット

さて、それ以降のビットは$E_{i+1}=1$の場合だけ$(x_i, y_i)$の比較がさらに必要になります。

$E_{i+1}$	$G_{i+1}$	$x_i$	$y_i$	$E_i$	$G_i$
1	0	0	0	1	0
1	0	0	1	0	0
1	0	1	0	0	1
1	0	1	1	1	0

$E_{i+1}=0$の場合は、$(x_i, y_i)$によらず出力が定まるため省略して記載します。

$E_{i+1}$	$G_{i+1}$	$x_i$	$y_i$	$E_i$	$G_i$
0	0	*	*	0	0
0	1	*	*	0	1

結果の判定

最終的に得られた$(E_0, G_0)$の値が、$x>y$であるかどうかを表します。

$E_0$	$G_0$	結果
1	0	x = y
0	0	x < y
0	1	x > y

入力値マスクの必要性

以上のように、$n$ビットの整数の大小比較は、$n$個の論理ゲートを順次評価することで可能だと分かりました。

また、上で列挙した通り、論理ゲートの入出力パターンは限られているため、$n$個の論理ゲートの入出力は事前に列挙可能です。

しかし、このままでは結果の判定のためにお互いの入力を知る必要があります。

お互いに入力値を知らずに結果を得るために、Aliceは論理ゲートにガーブル化と呼ばれる暗号化を施します。

論理ゲートの生成

まず、論理ゲートのどちらが0でどちらが1であるかを判別できなくするために、Aliceはラベルを生成します。

入力値$x = (0, 1)$に対して、ラベルを$(K^0_x, K^1_x)$と定義します。

同様に、下記のようにラベルを定義します。

• $y\rightarrow(K^0_y, K^1_y)$
• $E\rightarrow(K^0_E, K^1_E)$
• $G\rightarrow(K^0_G, K^1_G)$

このように01の代わりにラベルを用いることで、0と1のどちらが0でどちらが1であるかを判別できないようにします。

次に、入力に対する出力値の対応がわかってしまうと値が判別できてしまうため、論理テーブルの入力$K_x$と$K_y$を用いて出力$K_E$と$K_G$を暗号化します。

$$C_E = Encrypt_{K_x, K_y}(K_E)$$

$$C_G = Encrypt_{K_x, K_y}(K_G)$$

（ここでのEncryptは、$K_x$と$K_y$を組み合わせた鍵で$K_E$を暗号化する擬似的な表記としています）

これを、論理ゲートの表に当てはめると以下のようになります。

$x_i$	$y_i$	$E_i$	$G_i$
$K^0_x$	$K^0_y$	$C_{K^1_E}$	$C_{K^0_G}$
$K^0_x$	$K^1_y$	$C_{K^0_E}$	$C_{K^0_G}$
$K^1_x$	$K^0_y$	$C_{K^0_E}$	$C_{K^1_G}$
$K^1_x$	$K^1_y$	$C_{K^0_E}$	$C_{K^0_G}$

（ここで、$K^0_x$は$x_i = 0$に対応するラベル、$K^1_x$は$x_i = 1$に対応するラベルです）

これで、論理ゲートを見ても01のどちらが0でどちらが1であるかを判別できないようになりました。

しかし、この表を生成したAliceは値の対応関係を知ってしまっています。
そのため、AliceがBobの入力値を知らずに次のゲートに進めるようにOTを利用します。

OTによる入力値のやり取り

Aliceは、$K^0_y$と$K^1_y$を用意し、Bobが自分の入力ビットに対応する一方のみを選んで受け取れるように、OTプロトコルを通じて送信します。

OTでは、Bobは$K^0_y$と$K^1_y$のうち片方のみを得ることができ、また、AliceはBobがどちらを選択したかを知ることができません。

すると、BobはAliceが選択したビットに対応する$K_x$（0と1どちらに対応するかはBobには判別不能）と、自身のビットに対応する$K_y$を得ることができます。

これらを用いて、論理ゲートの出力を復号します。

$$Dec_{K_x, K_y}(C_{K_E}) = K_E$$

$$Dec_{K_x, K_y}(C_{K_G}) = K_G$$

Bobが持っているのは、Aliceの入力値に対応する$K_x$と、自身の入力値に対応する$K_y$のみです。
したがって、論理ゲートのうち1行のみが復号できます。

この一連の工程をビットごとに行います。

いま、Bobの手元には前回の論理ゲートの出力があり、Aliceはどれが出力されたかを知りません。逆に、Bobは得た出力がどのビットに対応するかを知りません。

これを繰り返すことで、お互いの入力値を知らないまま、Bobは$K_{E_0}$と$K_{G_0}$を得ることができます。

結果の復号

最後に、Aliceは最終結果の対応表だけをBobに送信します。

$K_{E_0}$	$K_{G_0}$	結果
$K^0_{E_0}$	$K^0_{G_0}$	x = y
$K^0_{E_0}$	$K^1_{G_0}$	x < y
$K^1_{E_0}$	$K^0_{G_0}$	x > y

Bobは、自身の手元にある$K_{E_0}$と$K_{G_0}$を用いて、$x$と$y$の大小関係を知ることができます。

まとめ

以上のようにしてヤオの富豪問題を解くことができました。

Garbled circuitは非常に強力な手法ですが、実用化にあたっては計算・通信コストの高さが課題とされてきました。特に、ビットごとにゲートを暗号化・評価する必要があり、計算規模が大きくなるほど負荷が増大します。

このような課題に対し、近年ではさまざまな最適化技術が提案されています。中でも、OT extensionは、少数のベースOTから多数のOTを効率的に拡張する手法で、計算・通信コストの削減に大きく寄与しています。

このOT extensionを効果的に活用しているプロトコルの代表例がMASCOTです。
実はこの記事もMASCOTを調べている過程でOTやGarbled circuitが出てきたことがキッカケでした。

OTについては、こちらの記事でも紹介しているので、ご興味のある方はそちらもぜひご覧ください。

https://zenn.dev/synschismo_inc/articles/db5fcdba0f5bee