Yao's Garbled Circuits
概要
2PCプロトコルとして一般的なスキームであり、お互いがプロトコルに協力的でない限りどちらも秘密計算の結果を得ることはできない。
プロトコル
この2PCの参加者はそれぞれGarbler、Evaluatorと呼ばれる。役割は異なるが、お互いPrivate InputをCircuitに入力する。
Garblerは後述するGarblerd Circuitを作成する。
Evaluatorは実際に計算を行う
この記事ではAliceがGarblerで、BobがEvaluatorとする。
この例では2in-1outのgateを例にする。ふたつのinputとoutputはそれぞれ1bitとする。
https://scrapbox.io/files/66faac8ed2396c001ce96b9d.png
このAND gateはx1とx2のinput wireから一つのoutput wireを出力する例
大まかな流れは以下のようになる
1.AliceはGarbled Circuitを作成し、ラベルをランダムに生成する。
2.Oblivious Transferを使って、Bobが自分の入力に対応するラベルを取得する。
3.BobはGarbled Circuitを評価し、出力ラベルを計算して最終結果を得る。
ユースケースによるが、必ずしもAliceが結果を知りたいとは限らない
これにより、BobはAliceの入力を知らず、またAliceもBobの入力や中間結果を知ることなく、安全に計算を行うことができます
1. Aliceが回路をガーベル化
まずAlice(Garbler)は回路の各ゲートをガーベル化して暗号化された形式に変換しBobに送る準備をします。
1.1 ワイヤのラベル生成
Aliceは回路内の各ワイヤに対して、2つのランダムなラベルを生成します。
$ \lambda_{W, 0}:ワイヤが0のときに対応するラベル
$ \lambda_{W, 1} :ワイヤが1のときに対応するラベル
このラベルは、入力ビットが0か1かに対応するGarbled Inptとなります。
Aliceがランダムに生成し、それに基づいてGarbled Circuitを作成します。
前提として回路がどのような処理を行うのかという点はお互い認識している
1.2 Gaebled gateの生成
Aliceは各ゲート(例えばANDゲート)の真理値表に従って、対応する出力ラベルを暗号化します。このとき、ゲートの入力ラベル(2つのワイヤのラベル)に基づいて出力ラベルを選択し、その出力ラベルを暗号化します。
AliceはゲートごとにGarbled Tableと呼ばれるテーブルを作成し、真理値表の各行に対して出力ラベルを暗号化します。
例えば、ANDゲートの場合、以下のような形式になります
https://scrapbox.io/files/66fabdf8a95157001ce24209.png
table:garbled_table
(x1, x2) 暗号化された出力ラベル
(0, 0) Enc( \lambda_{out, 0} )
(0, 1) Enc( \lambda_{out, 0} )
(1, 0) Enc( \lambda_{out, 0} )
(1, 1) Enc( \lambda_{out, 1} )
AliceはこのガーベルテーブルをBobに送りますが、どの行がどの入力に対応しているかはBobには分かりません。
1.3 ガーベルド回路と入力ラベルの送信
AliceはGarbled TableとBobに必要なラベルをBobに送ります。ここで、Bobが必要とするのは、自分の入力ビットに対応するラベルです。
Aliceは後述するOblivious TransfGer(OT)を使って、Bobが自分の入力ビットに対応するラベルだけを取得できるようにします。OTを使うことで、自分のビットに対応するラベルを相手に知られることなく選択できます
2. Bobがガーベルド回路を評価
次にBobは、Aliceから受け取ったGarbled Circuitを使って評価を行います
2.1 自分の入力に対応するラベルを取得
Bobは、Oblivious Transfer(OT)を通じて、自分の入力ビットに対応するラベルをAliceから取得します。たとえば、Bobの入力が x_1 = 1 、 x_2 = 0 だとした場合、それに対応するラベル \lambda_{x1, 1} と \lambda_{x2, 0} を取得します。
2.2 ガーベルテーブルの評価
Bobは、Aliceが送ったガーベルテーブルと自分の取得した入力ラベルを使って、ゲートを1つずつ評価していきます。
ガーベルテーブルの中から、自分の入力ラベルに対応する行を選び、暗号化された出力ラベルを復号します。たとえば、ANDゲートの場合、自分の入力 (x_1 = 1, x_2 = 0) に対応する行を選び、その行の暗号化された出力ラベルを復号して出力ラベル \lambda_{out} を取得します。
この評価は、Bobがワイヤの状態(0または1)を知ることなく進行します。
2.3 出力ラベルの再構成
Bobは、全てのゲートを評価して最終的な出力ラベルを得ます。
Bobはこの出力ラベルをAliceに送ることなく、Aliceから送られた対応表に基づいて、出力ラベルが0に対応するのか、1に対応するのかを確認します。
3. 出力を共有する
AliceとBobは、このプロトコルを通じて、最終的な計算結果(例えばAND演算の結果)を得ることができます。
Bobが出力を自分で知りたい場合は、最終的な出力ラベルを自分で評価して結果を知りますが、Aliceと結果を共有することもできます。
Oblivious Transfer(OT)
2人の当事者間でデータを転送する際に使用される
送信者が複数のメッセージを持ち、受信者がそのうちの1つ(または一部)を選択して受け取るプロトコル。
送信者は受信者が何を選んだかわからず、受信者は選んだ以外のメッセージの内容を知ることができない。
https://scrapbox.io/files/66faa8e2fcb164001da51b63.png
一度OTすれば、以降のgateは連鎖的に秘密計算されていくので、Layerが変わるごとにOTする必要はない。
もしInput Layerに複数のgateが存在するのであればそのgateの数だけOTが必要になる。
Yao's millionaire problem
BMR
Multiplication Beaver Triple
各Partyがlabel作成とCircuit作成を担う。OTが不要でコンスタントラウンドのPreprocessingを実現できる。
Point and Permute
標準的なYao's Garbeld CircuitはGarbled Tableを構成する4つのinput pair全てを用意する必要があった。
参考文献