參考文獻：

Bellare M, Hoang V T, Rogaway P. Foundations of garbled circuits[C]//Proceedings of the 2012 ACM conference on Computer and communications security. 2012: 784-796.

Zahur S, Rosulek M, Evans D. Two halves make a whole[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2015: 220-250.

Bi?er O. Efficiency Optimizations on Yao’s Garbled Circuits and Their Practical Applications[J]. arXiv preprint arXiv:1703.03473, 2017.

文章目錄

• Garbling Schemes Abstraction
• Secret Shares
• AND Gate
• • Generator Half Gate
  • Evaluator half-gate
  • Two halves make a whole
• Arbitrary gates
• The complete scheme

Garbling Schemes Abstraction

2012年，Bellare, Hoang, Rogaway 給出了混淆電路協(xié)議的抽象。

一個 Garbling Scheme 是算法四元組 $(Gb,En,Ev,De)$，

• $Gb(1^k,f)\to (F,e,d)$：安全參數(shù)$k$，將布爾電路$f$轉(zhuǎn)化為混淆電路$F$，$e$是編碼信息（encoding information），$d$是解碼信息（decoding information）
• $En(e,x)\to X$：$x$是明文輸入，根據(jù)$e$編碼為混淆值$X$
• $Ev(F,X)\to Y$：將$X$輸入混淆電路$F$，運算后結(jié)果為$Y$
• $De(d,Y)\to y$：$Y$是混淆輸出，根據(jù)$d$解碼為明文$y$

安全屬性：

Privacy：$(F,X,d)$不會泄露比$f(x)$更多的關(guān)于$x$的信息

Obliviousness：$(F,X)$不會泄露$x$的任何信息

Authenticity：只給定$(F,X)$，任何敵手都無法計算一個$Y^{\prime }\ne Ev(F,X)$使得$De(d,Y^{\prime })\ne \perp$，除了可忽略的概率

Secret Shares

混淆電路的任意一條線$w$，我們將線標簽$k_w^0,k_w^1$和置換比特（permute bit）$p_w$寫在一起：
$$\begin{array}{rl}{W}_w^0& =k_w^0\Vert p_w\\ W_w^1& =k_w^1\Vert (p_w\oplus 1)\end{array}$$

值$v_w=0$的選擇比特（select bit）為$s_w=p_w$，而值$v_w=1$的選擇比特為$s_w=p_w\oplus 1$。易知，$v_w=s_w\oplus p_w$，秘密共享為：
$$[v_w]=(p_w,p_w\oplus v_w)$$

使用 Free XOR 技術(shù)，隨機選擇$k_w^0$，那么$k_w^1=k_w^0\oplus R$?；蛘哒f，隨機選擇$W_w^0$（包含了$p_w$），然后設(shè)置$lsb(R)=1$，那么$W_w^1=W_w^0\oplus R$

此時的秘密共享為：
$$[v_w]=(W_w^0,W_w^0\oplus v_w?R)$$

可以提取$lsb(?)$重新得到$(p_w,p_w\oplus v_w)$

AND Gate

令 Alice 是混淆電路的生成者，令 Bob 是混淆電路的計算者。

一個 AND Gate，它的輸入線為$a,b$，輸出線為$c$

簡記：$a=0$的混淆值為$A$，$b=0$的混淆值為$B$，$c=0$的混淆值為$C$，Free XOR 技術(shù)的全局偏移為$R$

Generator Half Gate

這個所謂的 Generator Half Gate 是指：Alice 知道其中一條輸入線（不失一般性的，$a$）的明文值，只知道另一條線（對應(yīng)的，$b$）的混淆值。

為了計算 $c=a\wedge b$，因為 Alice 知道$a$的值，因此它是關(guān)于$b$的一元門（unary gate），

如果$a=0$，那么這個一元門就是$c=0$

如果$a=1$，那么這個一元門就是$c=b$

Alice 構(gòu)造這個一元門的混淆表：
$$\begin{array}{r}H(B)\oplus C\\ H(B\oplus R)\oplus C\oplus aR\end{array}$$

Bob 持有$b$上的混淆值，但無法區(qū)分$b=0/1$，

如果 Bob 持有$B$，那么可以得到$C$，對應(yīng)$c=a\wedge 0=0$

如果 Bob 持有$B\oplus R$，那么可以得到$C\oplus aR$，對應(yīng)$c=a\wedge 1=a$

利用 P&P 技術(shù)和 GRR3 技術(shù)，Alice 根據(jù)$b$的置換比特$p_b:=lsb(B)$，將選擇比特$s_b^{v_b}=0$所對應(yīng)的$v_b=p_b$的條目的密文置為零，即：
$$C=\{\begin{array}{rlr}H(B),& & p_b=0\\ H(B\oplus R)\oplus aR,& & p_b=1\end{array}$$

當$p_b=0$時，
$$\begin{array}{rl}H(B)\oplus C& =0\\ T_G:=H(B\oplus R)\oplus C\oplus aR& =H(B)\oplus H(B\oplus R)\oplus aR\end{array}$$

當$p_b=1$時，
$$\begin{array}{rl}H(B\oplus R)\oplus C\oplus aR& =0\\ T_G:=H(B)\oplus C& =H(B)\oplus H(B\oplus R)\oplus aR\end{array}$$

所以，我們只需發(fā)送一個密文$T_G$即可。

Evaluator half-gate

這個所謂的 Evaluator half-gate 是指：Bob 知道其中一條輸入線（不失一般性的，$a$）的明文值，只知道另一條線（對應(yīng)的，$b$）的混淆值。

為了計算 $c=a\wedge b$，因為 Bob 知道$a$的值，因此它是關(guān)于$b$的一元門（unary gate）

Alice 構(gòu)造這個如下的密文（這并非真值表對應(yīng)的混淆表）：
$$\begin{array}{r}H(A)\oplus C\\ H(A\oplus R)\oplus C\oplus B\end{array}$$

如果 Bob 知道$a=0$，此時它持有$A$，那么可以得到$C$，對應(yīng)$c=0\wedge b=0$

如果 Bob 知道$a=1$，此時它持有$A\oplus R$，那么可以得到$C\oplus B$，然后還需要再與$b$上的混淆值（Bob 無法區(qū)分$b=0/1$）異或，

如果 Bob 持有$B$，計算出$C\oplus B\oplus B=C$

如果 Bob 持有$B\oplus R$，計算出$C\oplus B\oplus B\oplus R=C\oplus R$

對應(yīng)$c=1\wedge b=b$

由于 Bob 知道$a$的明文值，因此知道自己持有的是$A$還是$A\oplus R$，所以根本不必利用隨機置換來隱藏這個信息。

利用 GRR3 技術(shù)，我們簡單地設(shè)置$C=H(A)$，那么有：
$$\begin{array}{rl}H(A)\oplus C& =0\\ T_E:=H(A\oplus R)\oplus C\oplus B& =H(A)\oplus H(A\oplus R)\oplus B\end{array}$$

所以，我們只需發(fā)送一個密文$T_E$即可。

Two halves make a whole

容易發(fā)現(xiàn)：
$$\begin{array}{rl}c& =a\wedge b\\ & =(a\wedge r)\oplus (a\wedge (b\oplus r))\end{array}$$

Alice 和 Bob 都不知道$a,b$的明文值，只有混淆值$W_a^{v_a},W_b^{v_b}$

將置換比特和線標簽視為秘密共享。對于$b$上的值的 shares，Alice 持有置換比特$p_b:=r$的明文（根據(jù)$lsb(W_b^0)$），Bob 持有選擇比特$s_b:=b\oplus r$的明文（根據(jù)$lsb(W_b^{v_b})$）

因此，我們將 AND Gate 轉(zhuǎn)化為：

• $1$個 Generator Half Gate：$c_1=a\wedge r$，其中 Alice 知道$r$，但是不知道$a$（同時也不知道$b$）
• $1$個 Evaluator half-gate：$c_2=a\wedge (b\oplus r)$，其中 Bob 知道$b\oplus r$，但是不知道$a,b$
• $1$個 XOR Gate：$c=c_1\oplus c_2$，這可以利用 Free XOR 技術(shù)

Alice 構(gòu)造 Generator Half Gate，根據(jù)$p_a:=lsb(W_a^0)$設(shè)置恰當?shù)?span id="ze8trgl8bvbq" class="katex--inline">$W_{c_1}^0$，發(fā)送一個密文，
$$T_G:=H(W_a^0)\oplus H(W_a^0\oplus R)\oplus p_{b}R$$

構(gòu)造 Evaluator half-gate，設(shè)置$W_{c_2}^0=H(W_b^{p_b})$（使得$b\oplus r=0$時$v_b=p_b$），發(fā)送另一個密文，
$$T_E:=H(W_b^0)\oplus H(W_b^0\oplus R)\oplus W_a^0$$

共計發(fā)送$2$個密文。

Bob 接收到兩個 Half Gate 后，

根據(jù)$a$線上的混淆值$W_a^{v_a}$，計算出$c_1$線的混淆值$W_{c_1}^{v_{c_1}}$

根據(jù)$b$線上的$s_b:=lsb(W_b^{v_b})$，解密得到$W_{c_2}^0\oplus W_a^0$，再與$a$線上的$W_a^{v_a}$異或，得到$W_{c_2}^{v_{c_2}}$

計算$W_{c_1}^{v_{c_1}}\oplus W_{c_2}^{v_{c_2}}$，得到$c$線上的混淆值$W_c^{v_c}$

Arbitrary gates

任意的 even gate（非凡的只有 XOR, NXOR），應(yīng)用 Free XOR 技術(shù)，都是 free 的。

任意的 odd gate（例如 AND, NAND, OR, NOR）都可以寫作：
$$f(v_a,v_b)=({\alpha }_a\oplus v_a)\wedge ({\alpha }_b\oplus v_b)\oplus {\alpha }_c$$

其中${\alpha }_c$控制$1$的個數(shù)是：

• ${\alpha }_c=0$時，有一個$1$，三個$0$
• ${\alpha }_c=1$時，有三個$1$，一個$0$

而${\alpha }_a,{\alpha }_b$控制那一個不同的數(shù)的位置：

• 對于$v_a=1?{\alpha }_a,v_b=1?{\alpha }_b$，這一個條目的真值只有一個
• 而其他的三個條目，它們的真值相等

三元組$({\alpha }_a,{\alpha }_b,{\alpha }_c)\in \{0,1{\}}^3$的取值范圍大小是$2^3=8$，分別對應(yīng)$8$種 odd gate：

設(shè)置${\alpha }_a={\alpha }_b={\alpha }_c=0$，那么就是 AND Gate

設(shè)置${\alpha }_a={\alpha }_b={\alpha }_c=1$，那么就是 OR Gate

如果把$f(v_a,v_b)$寫成：
$$\begin{array}{rl}{f}_G(v_a,p_b)& :=({\alpha }_a\oplus v_a)\wedge ({\alpha }_b\oplus p_b)\oplus {\alpha }_c\\ f_E(v_a,p_b\oplus v_b)& :=({\alpha }_a\oplus v_a)\wedge (p_b\oplus v_b)\\ f(v_a,v_b)& =f_G(v_a,p_b)\oplus f_E(v_a,p_b\oplus v_b)\end{array}$$

因為 Alice 知道$p_b$，而 Bob 知道$p_b\oplus v_b$，那么就可以利用 Half Gate 技術(shù)，將這個 odd gate 的通信量降低到$2$個密文。

The complete scheme

將電路$f$的各個邏輯門拓撲排序，對電線依次標號$\{1,2,?\}$，輸出線為$i$的邏輯門記為$G_i$，它的輸入線為$a,b<i$

利用 P&P 技術(shù)、Half Gate 技術(shù)、Free XOR 技術(shù)、GRR3 技術(shù)，完整的 GC 協(xié)議為：

易知 Free XOR 技術(shù)使得 even gate 的所需的密文數(shù)量為零?？梢宰C明，實現(xiàn) odd gate 至少需要兩個密文。而 Half Gate 技術(shù)使用兩個密文就完成了 odd gate 的構(gòu)造。因此，上述的協(xié)議達到了最優(yōu)的通信復雜度。

總結(jié)

以上是生活随笔為你收集整理的Yao‘s GC 的通信最优解：Half Gate的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。