回路が破損しています

難読回路プロトコルでは、秘匿転送を利用します。秘匿転送では、文字列は送信者と受信者の間で次のように転送されます。送信者は 2 つの文字列を持っています。${\displaystyle S_{0}}$そして${\displaystyle S_{1}}$受信者が選択する${\displaystyle b\in \{0,1\}}$そして送信者は${\displaystyle S_{b}}$秘匿転送プロトコルにより、

1. 受信者は未送信の文字列に関する情報を一切得ない${\displaystyle S_{(1-b)}}$、
2. 価値${\displaystyle b}$送信者には公開されません。

受信者は知らないが、${\displaystyle S_{0},S_{1}}$値、実際には受信者は、${\displaystyle S_{b}}$受信者が盲目的に選択しないようにエンコードします${\displaystyle b}$つまり、もし${\displaystyle S_{0}}$偽の値をエンコードします。${\displaystyle S_{1}}$真の値をエンコードし、受信者がエンコードされた真の値を取得したい場合、受信者は${\displaystyle b=1}$。

秘匿転送は、RSA暗号システムのような非対称暗号技術を用いて構築することができる。

オペレーター${\displaystyle \parallel }$文字列連結演算子です。${\displaystyle \oplus }$はビット単位のXOR演算です。kはセキュリティパラメータであり、鍵の長さを表します。80より大きい値が必要で、通常は128に設定されます。

小さな関数のブール回路は、手作業で生成できます。 2 入力のXOR ゲートとANDゲートで回路を作成するのが一般的です。 生成された回路の AND ゲートの数が最小であることが重要です (フリー XOR 最適化を参照)。論理合成技術を使用して、AND ゲートの数に関して最適化された回路を生成する方法があります。^{[ 5 ]}ミリオネア問題の回路は、デジタル比較器回路 (減算器として動作し、キャリー フラグを出力する全加算器のチェーン) です。 全加算器回路は、 1 つのANDゲートといくつかのXORゲートのみを使用して実装できます。 これは、ミリオネア問題の回路の AND ゲートの総数が入力のビット幅に等しいことを意味します。

アリス（ガーブラー）はこのステップでブール回路を暗号化して、ガーブルされた回路を取得します。アリスは、回路内の各ワイヤにラベルと呼ばれるランダムに生成された2つの文字列を割り当てます。1つはブール意味0、もう1つは1です。（ラベルはkビット長で、kはセキュリティパラメータであり、通常は128に設定されます。）次に、回路内のすべてのゲートに移動し、真理値表の0と1を対応するラベルに置き換えます。下の表は、2つの入力を持つANDゲートの真理値表を示しています。${\displaystyle w^{a},w^{b}}$出力${\displaystyle w^{c}}$:

アリスは0と1を対応するラベルに置き換えた。

次に、真理値表の出力エントリを対応する2つの入力ラベルで暗号化します。暗号化された表は、難読化表と呼ばれます。これは、正しい2つの入力ラベルを持っている場合にのみ難読化表を復号できるようにするために行われます。以下の表では、${\displaystyle Enc_{\kappa }(X)}$は、二重鍵対称暗号化であり、${\displaystyle \kappa }$は秘密鍵であり、Xは暗号化される値です（固定鍵ブロック暗号を参照）。

その後、アリスは行から出力値が特定できないように、テーブルをランダムに並べ替えます。このランダムな並べ替えにちなんで、プロトコルの名前である「garbled（ガーブルド）」が付けられました。

アリスは回路内のすべてのゲートについて計算された難読化テーブルをボブに送信する。ボブは難読化テーブルを開くために入力ラベルを必要とする。そこでアリスは自分の入力に対応するラベルを選択する。${\displaystyle a}$そしてそれらをボブに送信します。たとえば、アリスの入力が${\displaystyle \mathbf {a} =a_{4}a_{3}a_{2}a_{1}a_{0}=01101}$そして彼女は送る${\displaystyle X_{0}^{a_{4}}}$、${\displaystyle X_{1}^{a_{3}}}$、${\displaystyle X_{1}^{a_{2}}}$、${\displaystyle X_{0}^{a_{1}}}$、 そして${\displaystyle X_{1}^{a_{0}}}$ボブへ。ボブはアリスの意見について何も知ることはないだろう。${\displaystyle \mathbf {a} }$なぜなら、ラベルはアリスによってランダムに生成され、ボブにはランダムな文字列のように見えるからです。

ボブは入力に対応するラベルも必要とします。彼は入力の各ビットに対して、非盲目的な転送によってラベルを受け取ります。たとえば、ボブの入力が${\displaystyle \mathbf {b} =b_{4}b_{3}b_{2}b_{1}b_{0}=10100}$ボブはまず${\displaystyle b_{0}=0}$アリスのラベルの間${\displaystyle X_{0}^{b_{0}}}$そして${\displaystyle X_{1}^{b_{0}}}$2回に1回の無知な転送を通じて、彼は受け取る${\displaystyle X_{0}^{b_{0}}}$などなど。無意識的な転送の後、アリスはボブの入力について何も知ることができず、ボブも他のラベルについて何も知ることができません。

データ転送後、ボブは判読不能なテーブルと入力ラベルを受け取ります。彼はすべてのゲートを一つずつ通過し、判読不能なテーブルの行を復号化しようと試みます。彼は各テーブルにつき1行を開き、対応する出力ラベルを取得することができました。${\displaystyle X^{c}=Dec_{X^{a},X^{b}}(garbled\_table[i])}$、 どこ${\displaystyle 0\leq i\leq 3}$彼は出力ラベルに到達するまで評価を続けます。

評価後、ボブは出力ラベルを取得します。${\displaystyle X^{c}}$アリスは両方のラベルを持っているため、それがブール値にどう対応するかを知っている。${\displaystyle X_{0}^{c}}$そして${\displaystyle X_{1}^{c}}$アリスがボブに情報を共有するか、ボブがアリスに結果を明らかにするかのどちらかによって、どちらか一方または両方が結果を知ることができる。

この最適化では、アリスはランダムなビットを生成し、${\displaystyle s}$各ワイヤの選択ビットと呼ばれる${\displaystyle w}$彼女はラベル0の最初のビットを設定します。${\displaystyle X_{0}^{a}}$に${\displaystyle s}$そしてラベル1の最初の部分、${\displaystyle X_{1}^{a}}$、 に${\displaystyle {\bar {s}}}$（​​${\displaystyle s}$彼女はワイヤーについても同じことをする。${\displaystyle w^{b}}$すると彼女は、ランダムに順列する代わりに、入力の選択ビットに従って難読化されたテーブルをソートします。こうすることで、ボブは正しい行を見つけるためにテーブルの4行すべてをテストする必要がなくなります。なぜなら、各ワイヤラベルとともにポインタビットを受け取り、1回の試行で正しい行を見つけて復号化できるからです。これにより、評価負荷が4分の1に軽減されます。また、選択ビットはランダムに生成されるため、出力値に関する情報も一切明らかにされません。^{[ 6 ]}

この最適化により、文字化けしたテーブルのサイズが 4 行から 3 行に縮小されます。ここでは、アリスはゲートの出力ワイヤのラベルをランダムに生成する代わりに、入力ラベルの関数を使用して生成します。アリスは、文字化けしたテーブルの最初のエントリがすべて 0 になり、送信する必要がなくなるように出力ラベルを生成します。^{[ 7 ]}

${\displaystyle {\begin{aligned}&Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})=0\\&X_{0}^{c}=Dec_{X_{0}^{a},X_{0}^{b}}(0).\end{aligned}}}$

この最適化では、アリスはグローバルな乱数 (k-1) ビット値を生成します。${\displaystyle R}$これは秘密にされている。入力ゲートの混乱中に${\displaystyle w^{a}}$そして${\displaystyle w^{b}}$彼女はラベルを生成するだけです${\displaystyle (X_{0}^{a},X_{0}^{b})}$そして他のラベルを次のように計算します。${\displaystyle X_{1}^{a}=X_{0}^{a}\oplus (R\parallel 1)}$そして${\displaystyle X_{1}^{b}=X_{0}^{b}\oplus (R\parallel 1)}$これらの値を使用して、XORゲートの出力ワイヤのラベルは${\displaystyle w^{c}}$入力線付き${\displaystyle w^{a}}$、${\displaystyle w^{b}}$設定されています${\displaystyle X^{c}=X^{a}\oplus X^{b}}$この最適化におけるランダムオラクルモデルのセキュリティ証明は、Free-XOR論文で示されています。^{[ 8 ]}

この方法により、SHA-2のような高コストな暗号学的ハッシュ関数ではなく、固定鍵AESを使用してANDゲートを効率的に難読化および評価できます。Free XORおよび行削減技術と互換性のあるこの難読化方式では、出力鍵は${\displaystyle X^{c}}$入力トークンで暗号化されています${\displaystyle X^{a}}$そして${\displaystyle X^{b}}$暗号化機能を使用する${\displaystyle Enc(X^{a},X^{b},T,X^{c})=\pi (K)\oplus K\oplus X^{c}}$、 どこ${\displaystyle K=2X^{a}\oplus 4X^{b}\oplus T}$、${\displaystyle \pi }$は固定鍵ブロック暗号（例えば、AESでインスタンス化される）であり、${\displaystyle T}$は、ゲートごとに一意な番号（ゲート識別子など）で、tweakと呼ばれます。^{[ 9 ]}

この最適化により、ANDゲートのガーブルテーブルのサイズが、行削減時の3行から2行に削減されます。これは、特定のクラスのガーブル技術の場合、ガーブルテーブルの行数の理論上の最小値であることが示されています。^{[ 10 ]}