Yao's Garbled Circuit

やり方

Binary なサーキットがあるとする。このサーキットを 2-Party, P1 と P2 で評価する。

   Circuit:
             0|
            (2:Or)
          1/      2\
       (0:And)    (1:Or)
       3/   4\   5/    6\
Input: 0      1  2       3

サーキットの構造は P1 と P2 が共有する。
P1, P2 の入力は、お互い公開せずにサーキットを評価する。
サーキットのどの入力を、どちらが提供するのかは事前に決めておく。

Step 1: P1 がサーキットを作る

サーキットの各ワイヤー (上の図の | の部分) について、P1 が True と False に対応するワイヤーラベルを作る。

ワイヤーラベルには、ランダムな鍵とランダムなパリティービットを割りあてる。パリティービットは、True と False のラベルで異なるようにする。

WireLabel {
  key: Vec<u8>,
  parity: bool,  
}

Wire {
  true_label: WireLabel,
  false_label: WireLabel,
}

Garbled Tableの作成

サーキットの各ゲート (上の図の (n: And/Or) の部分) について、Garbled Table を作る。

Garbled Table は、ゲートの入力の全パターンに対応する値を持っている。
また、各値がどの入力パターンに対応するものなのかが分からないように、ランダムに割り当てられたパリティー値から作られるインデックスに格納される。

各値は、以下の様に作る。

lhs = Hash(wire_label_left.key || wire_label_key.right || gate_id)
rhs = wire_label_out
lhs XOR rhs  // 値

例えば、OR のゲートで、入力が、左が false, 右が true の場合は、結果が true になるので、wire_label_leftには、左のワイヤーの false のワイヤーラベル、wire_label_rightには、右のワイヤーの true のワイヤーラベル、wire_label_out には、true のワイヤーラベルを使う。

格納するインデックスは、

index = wire_label_left.p << 1 | wire_label_right.p

Output Decoding Table の作成

また、評価結果を鍵からデコードするために、Output Decoding Table を作る。

lhs = Hash(wire_label_out.key || "out" || gate_id) % 2 as bool
rhs = value  // true または false
lhs XOR rhs

rhs は 1 ビットなので、lhs は最後のビットだけ残す。

Step 2: P1 が P2 に、Garbled Table と Output Decoding Table を送る。

P1 が、各ノードの Garbled Table と、Output Decoding Table を P2 に送る。

Step 3: P1 が P2 に自分の入力に対応するワイヤーラベルを送る

P1 は全てのワイヤーラベルを持っているので、自分の入力に対応するワイヤーラベルを P2 に送る。

Step 4: P2 が Oblivious Transfer を使い、P1 から、自分の入力に対応するワイヤーラベルを取得する

Oblivious Transfer (OT)

一番簡単な、Semi Honest な OT で、P2 が P1 からワイヤーラベルを取得する方法は、以下の通り：

1. 鍵ペアを 2 つ作って、片方の秘密鍵を捨てる
2. 自分が必要な方の入力に、秘密鍵が存在する公開鍵を、自分が必要でない方の入力に、秘密鍵が存在しない公開鍵を割り当てて、P1 に送る
3. P1は、true と false のワイヤーラベルを、受け取ったそれぞれに対応する公開鍵で暗号化して、P2 に送る
4. P2 は、必要な方のワイヤーラベルを秘密鍵で復号化する

Step 5: P2 が Garbled Table を使い、サーキットを評価する

この時点で、P2 は全ての入力に対応するワイヤーラベルを持っているので、入力が接続されているゲートからルートのゲートに向かって、サーキットを評価する。

ゲートの評価

ゲートの入力に対応するワイヤーラベルのパリティービットから、Garbled Table のインデックスを計算して、値を取得する。

index = wire_label_left.p << 1 | wire_label_right.p

次に、ゲートの入力に対応するワイヤーラベルから lhs を求める。

lhs = Hash(wire_label_left.key || wire_label_key.right || gate_id)

値は、lhs XOR 出力のワイヤーラベル なので、値に lhs を XOR することで lhs を打ち消して 出力のワイヤーラベル を取得する。

Step 6: P2 が、ルートゲートの出力ワイヤーラベルをデコードする

Output Decoding Table の値は、lhs XOR サーキットの評価結果 なので、
Output Decoding Table の、出力ワイヤーラベルのパリティービットのインデックスから値を取得して、以下の様に lhs を計算して、値に XOR することで、サーキットの評価結果を取得できる。

lhs = Hash(出力ワイヤーラベル.key || "out" || gate_id) % 2 as bool

実装

参考文献

• Pragmatic MPC