Yao's Garbled Circuits
概要
二人の参加者が関数$ f(x,y)を実行する時に、x,yの情報を知られることなく、結果だけを得ることができる
x,yはそれぞれの参加者が提供した秘密データ
関数$ f(x,y)はGarbled Boolean Circuit(GC)$ C(x,y)で表現される
GCはGarbled Boolean Gateで構成されている
蛇足
garbledはごちゃ混ぜになった、という意味
詳細
Garbled Boolean Gate
以下の論理ゲート用いて、x,y の入力を知られずに計算結果のz を返すことを目指す
https://gyazo.com/e050abd0cf19385fa2db24fbdd7159b8
x,y:入力ワイヤ
z :出力ワイヤ
$ k_x^0, k_x^1, k_y^0, k_y^1, k_z^0, k_z^1は暗号鍵
Garbled Computation Table(GCT)
以下のような表を用いてサーキットの処理を表現する
イメージは、鍵の組み合わせで計算結果を表現しつつ、その鍵が対応している入力値は秘密にすることで実現
https://gyazo.com/79ed4e1e7f3f6bfb7dbaa2b1d3c72bde
x,y の暗号鍵をもつ場合にのみ、計算結果z の鍵が正しく復号できる
例
$ k_x^0,k_y^1を受け取った場合は$ k_z^0が得られる
Aliceは暗号鍵6つ($ k_x^0, k_x^1, k_y^0, k_y^1, k_z^0, k_z^1)を生成してGCTを作成する
BobにGCTと自分の鍵$ k_x^{a}を送る
$ aはAliceの秘密情報
AliceはBobがどちらの鍵を受け取ったのかわからない
Bobの秘密情報$ bがバレない
受け取った鍵は$ k_y^bとなる
Bobは受け取らなかった方の鍵についての情報はわからない
Bobは$ k_x^a,k_y^bとGCTを入手した
それぞれの鍵を用いてGCTを復号すると、$ k_z^{g(a,b)}を得る
BobはAliceに$ k_z^{g(a,b)}を送信する
例えば、$ a=0,b=0 ならば $ k_z^0
以上で、AliceとBobの入力を秘匿にしたまま、計算結果の鍵$ k_z^{g(a,b)}を得ることができた
参考文献
公式
論文
スライド
Yao’s Garbled Circuit
Konstantinos Gkikas, アムステルダム大学
Web