参考文献:
- 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 给出了混淆电路协议的抽象。
一个 Garbling Scheme 是算法四元组 (Gb,En,Ev,De)(Gb,En,Ev,De)(Gb,En,Ev,De),
- Gb(1k,f)→(F,e,d)Gb(1^k,f) \to (F,e,d)Gb(1k,f)→(F,e,d):安全参数kkk,将布尔电路fff转化为混淆电路FFF,eee是编码信息(encoding information),ddd是解码信息(decoding information)
- En(e,x)→XEn(e,x) \to XEn(e,x)→X:xxx是明文输入,根据eee编码为混淆值XXX
- Ev(F,X)→YEv(F,X) \to YEv(F,X)→Y:将XXX输入混淆电路FFF,运算后结果为YYY
- De(d,Y)→yDe(d,Y) \to yDe(d,Y)→y:YYY是混淆输出,根据ddd解码为明文yyy
安全属性:
- Privacy:(F,X,d)(F,X,d)(F,X,d)不会泄露比f(x)f(x)f(x)更多的关于xxx的信息
- Obliviousness:(F,X)(F,X)(F,X)不会泄露xxx的任何信息
- Authenticity:只给定(F,X)(F,X)(F,X),任何敌手都无法计算一个Y′≠Ev(F,X)Y' \neq Ev(F,X)Y′=Ev(F,X)使得De(d,Y′)≠⊥De(d,Y') \neq \perpDe(d,Y′)=⊥,除了可忽略的概率
Secret Shares
混淆电路的任意一条线www,我们将线标签kw0,kw1k_w^0,k_w^1kw0,kw1和置换比特(permute bit)pwp_wpw写在一起:
Ww0=kw0∥pwWw1=kw1∥(pw⊕1)\begin{aligned} W_w^0 &= k_w^0 \| p_w\\ W_w^1 &= k_w^1 \| (p_w \oplus 1)\\ \end{aligned} Ww0Ww1=kw0∥pw=kw1∥(pw⊕1)
值vw=0v_w=0vw=0的选择比特(select bit)为sw=pws_w = p_wsw=pw,而值vw=1v_w=1vw=1的选择比特为sw=pw⊕1s_w = p_w \oplus 1sw=pw⊕1。易知,vw=sw⊕pwv_w = s_w \oplus p_wvw=sw⊕pw,秘密共享为:
[vw]=(pw,pw⊕vw)[v_w] = (p_w,\, p_w \oplus v_w) [vw]=(pw,pw⊕vw)
使用 Free XOR 技术,随机选择kw0k_w^0kw0,那么kw1=kw0⊕Rk_w^1 = k_w^0 \oplus Rkw1=kw0⊕R。或者说,随机选择Ww0W_w^0Ww0(包含了pwp_wpw),然后设置lsb(R)=1lsb(R)=1lsb(R)=1,那么Ww1=Ww0⊕RW_w^1 = W_w^0 \oplus RWw1=Ww0⊕R
此时的秘密共享为:
[vw]=(Ww0,Ww0⊕vw⋅R)[v_w] = (W_w^0,\, W_w^0 \oplus v_w \cdot R) [vw]=(Ww0,Ww0⊕vw⋅R)
可以提取lsb(⋅)lsb(\cdot)lsb(⋅)重新得到(pw,pw⊕vw)(p_w,\, p_w \oplus v_w)(pw,pw⊕vw)
AND Gate
令 Alice 是混淆电路的生成者,令 Bob 是混淆电路的计算者。
一个 AND Gate,它的输入线为a,ba,ba,b,输出线为ccc
简记:a=0a=0a=0的混淆值为AAA,b=0b=0b=0的混淆值为BBB,c=0c=0c=0的混淆值为CCC,Free XOR 技术的全局偏移为RRR
Generator Half Gate
这个所谓的 Generator Half Gate 是指:Alice 知道其中一条输入线(不失一般性的,aaa)的明文值,只知道另一条线(对应的,bbb)的混淆值。
为了计算 c=a∧bc = a \wedge bc=a∧b,因为 Alice 知道aaa的值,因此它是关于bbb的一元门(unary gate),
- 如果a=0a=0a=0,那么这个一元门就是c=0c=0c=0
- 如果a=1a=1a=1,那么这个一元门就是c=bc=bc=b
Alice 构造这个一元门的混淆表:
H(B)⊕CH(B⊕R)⊕C⊕aR\begin{aligned} H(B) \oplus C\\ H(B \oplus R) \oplus C \oplus aR\\ \end{aligned} H(B)⊕CH(B⊕R)⊕C⊕aR
Bob 持有bbb上的混淆值,但无法区分b=0/1b=0/1b=0/1,
-
如果 Bob 持有BBB,那么可以得到CCC,对应c=a∧0=0c=a \wedge 0 = 0c=a∧0=0
-
如果 Bob 持有B⊕RB \oplus RB⊕R,那么可以得到C⊕aRC \oplus aRC⊕aR,对应c=a∧1=ac=a \wedge 1 = ac=a∧1=a
利用 P&P 技术和 GRR3 技术,Alice 根据bbb的置换比特pb:=lsb(B)p_b := lsb(B)pb:=lsb(B),将选择比特sbvb=0s_b^{v_b}=0sbvb=0所对应的vb=pbv_b=p_bvb=pb的条目的密文置为零,即:
C={H(B),pb=0H(B⊕R)⊕aR,pb=1C = \left\{ \begin{aligned} H(B), && p_b = 0\\ H(B \oplus R) \oplus aR, && p_b = 1 \end{aligned} \right. C={H(B),H(B⊕R)⊕aR,pb=0pb=1
当pb=0p_b=0pb=0时,
H(B)⊕C=0TG:=H(B⊕R)⊕C⊕aR=H(B)⊕H(B⊕R)⊕aR\begin{aligned} 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{aligned} H(B)⊕CTG:=H(B⊕R)⊕C⊕aR=0=H(B)⊕H(B⊕R)⊕aR
当pb=1p_b=1pb=1时,
H(B⊕R)⊕C⊕aR=0TG:=H(B)⊕C=H(B)⊕H(B⊕R)⊕aR\begin{aligned} 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{aligned} H(B⊕R)⊕C⊕aRTG:=H(B)⊕C=0=H(B)⊕H(B⊕R)⊕aR
所以,我们只需发送一个密文TGT_GTG即可。
Evaluator half-gate
这个所谓的 Evaluator half-gate 是指:Bob 知道其中一条输入线(不失一般性的,aaa)的明文值,只知道另一条线(对应的,bbb)的混淆值。
为了计算 c=a∧bc = a \wedge bc=a∧b,因为 Bob 知道aaa的值,因此它是关于bbb的一元门(unary gate)
Alice 构造这个如下的密文(这并非真值表对应的混淆表):
H(A)⊕CH(A⊕R)⊕C⊕B\begin{aligned} H(A) \oplus C\\ H(A \oplus R) \oplus C \oplus B\\ \end{aligned} H(A)⊕CH(A⊕R)⊕C⊕B
如果 Bob 知道a=0a=0a=0,此时它持有AAA,那么可以得到CCC,对应c=0∧b=0c=0 \wedge b = 0c=0∧b=0
如果 Bob 知道a=1a=1a=1,此时它持有A⊕RA \oplus RA⊕R,那么可以得到C⊕BC \oplus BC⊕B,然后还需要再与bbb上的混淆值(Bob 无法区分b=0/1b=0/1b=0/1)异或,
- 如果 Bob 持有BBB,计算出C⊕B⊕B=CC \oplus B \oplus B = CC⊕B⊕B=C
- 如果 Bob 持有B⊕RB \oplus RB⊕R,计算出C⊕B⊕B⊕R=C⊕RC \oplus B \oplus B \oplus R = C \oplus RC⊕B⊕B⊕R=C⊕R
对应c=1∧b=bc=1 \wedge b = bc=1∧b=b
由于 Bob 知道aaa的明文值,因此知道自己持有的是AAA还是A⊕RA \oplus RA⊕R,所以根本不必利用随机置换来隐藏这个信息。
利用 GRR3 技术,我们简单地设置C=H(A)C = H(A)C=H(A),那么有:
H(A)⊕C=0TE:=H(A⊕R)⊕C⊕B=H(A)⊕H(A⊕R)⊕B\begin{aligned} 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{aligned} H(A)⊕CTE:=H(A⊕R)⊕C⊕B=0=H(A)⊕H(A⊕R)⊕B
所以,我们只需发送一个密文TET_ETE即可。
Two halves make a whole
容易发现:
c=a∧b=(a∧r)⊕(a∧(b⊕r))\begin{aligned} c &= a \wedge b\\ &= (a \wedge r) \oplus (a \wedge (b \oplus r))\\ \end{aligned} c=a∧b=(a∧r)⊕(a∧(b⊕r))
Alice 和 Bob 都不知道a,ba,ba,b的明文值,只有混淆值Wava,WbvbW_a^{v_a},W_b^{v_b}Wava,Wbvb
将置换比特和线标签视为秘密共享。对于bbb上的值的 shares,Alice 持有置换比特pb:=rp_b := rpb:=r的明文(根据lsb(Wb0)lsb(W_b^{0})lsb(Wb0)),Bob 持有选择比特sb:=b⊕rs_b := b \oplus rsb:=b⊕r的明文(根据lsb(Wbvb)lsb(W_b^{v_b})lsb(Wbvb))
因此,我们将 AND Gate 转化为:
- 111个 Generator Half Gate:c1=a∧rc_1 = a \wedge rc1=a∧r,其中 Alice 知道rrr,但是不知道aaa(同时也不知道bbb)
- 111个 Evaluator half-gate:c2=a∧(b⊕r)c_2 = a \wedge (b \oplus r)c2=a∧(b⊕r),其中 Bob 知道b⊕rb \oplus rb⊕r,但是不知道a,ba,ba,b
- 111个 XOR Gate:c=c1⊕c2c = c_1 \oplus c_2c=c1⊕c2,这可以利用 Free XOR 技术
Alice 构造 Generator Half Gate,根据pa:=lsb(Wa0)p_a:=lsb(W_a^0)pa:=lsb(Wa0)设置恰当的Wc10W_{c_1}^0Wc10,发送一个密文,
TG:=H(Wa0)⊕H(Wa0⊕R)⊕pbRT_{G} := H(W_a^0) \oplus H(W_a^0 \oplus R) \oplus p_bR TG:=H(Wa0)⊕H(Wa0⊕R)⊕pbR
构造 Evaluator half-gate,设置Wc20=H(Wbpb)W_{c_2}^0=H(W_b^{p_b})Wc20=H(Wbpb)(使得b⊕r=0b \oplus r = 0b⊕r=0时vb=pbv_b=p_bvb=pb),发送另一个密文,
TE:=H(Wb0)⊕H(Wb0⊕R)⊕Wa0T_{E} := H(W_b^0) \oplus H(W_b^0 \oplus R) \oplus W_a^0\\ TE:=H(Wb0)⊕H(Wb0⊕R)⊕Wa0
共计发送222个密文。
Bob 接收到两个 Half Gate 后,
- 根据aaa线上的混淆值WavaW_a^{v_a}Wava,计算出c1c_1c1线的混淆值Wc1vc1W_{c_1}^{v_{c_1}}Wc1vc1
- 根据bbb线上的sb:=lsb(Wbvb)s_b := lsb(W_b^{v_b})sb:=lsb(Wbvb),解密得到Wc20⊕Wa0W_{c_2}^{0} \oplus W_a^0Wc20⊕Wa0,再与aaa线上的WavaW_a^{v_a}Wava异或,得到Wc2vc2W_{c_2}^{v_{c_2}}Wc2vc2
- 计算Wc1vc1⊕Wc2vc2W_{c_1}^{v_{c_1}} \oplus W_{c_2}^{v_{c_2}}Wc1vc1⊕Wc2vc2,得到ccc线上的混淆值WcvcW_c^{v_c}Wcvc
Arbitrary gates
任意的 even gate(非凡的只有 XOR, NXOR),应用 Free XOR 技术,都是 free 的。
任意的 odd gate(例如 AND, NAND, OR, NOR)都可以写作:
f(va,vb)=(αa⊕va)∧(αb⊕vb)⊕αcf(v_a,v_b) = (\alpha_a \oplus v_a) \wedge (\alpha_b \oplus v_b) \oplus \alpha_c f(va,vb)=(αa⊕va)∧(αb⊕vb)⊕αc
其中αc\alpha_cαc控制111的个数是:
- αc=0\alpha_c=0αc=0时,有一个111,三个000
- αc=1\alpha_c=1αc=1时,有三个111,一个000
而αa,αb\alpha_a,\alpha_bαa,αb控制那一个不同的数的位置:
- 对于va=1−αa,vb=1−αbv_a=1-\alpha_a,v_b=1-\alpha_bva=1−αa,vb=1−αb,这一个条目的真值只有一个
- 而其他的三个条目,它们的真值相等
三元组(αa,αb,αc)∈{0,1}3(\alpha_a,\alpha_b,\alpha_c) \in \{0,1\}^3(αa,αb,αc)∈{0,1}3的取值范围大小是23=82^3=823=8,分别对应888种 odd gate:
- 设置αa=αb=αc=0\alpha_a=\alpha_b=\alpha_c=0αa=αb=αc=0,那么就是 AND Gate
- 设置αa=αb=αc=1\alpha_a=\alpha_b=\alpha_c=1αa=αb=αc=1,那么就是 OR Gate
如果把f(va,vb)f(v_a,v_b)f(va,vb)写成:
fG(va,pb):=(αa⊕va)∧(αb⊕pb)⊕αcfE(va,pb⊕vb):=(αa⊕va)∧(pb⊕vb)f(va,vb)=fG(va,pb)⊕fE(va,pb⊕vb)\begin{aligned} 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{aligned} fG(va,pb)fE(va,pb⊕vb)f(va,vb):=(αa⊕va)∧(αb⊕pb)⊕αc:=(αa⊕va)∧(pb⊕vb)=fG(va,pb)⊕fE(va,pb⊕vb)
因为 Alice 知道pbp_bpb,而 Bob 知道pb⊕vbp_b \oplus v_bpb⊕vb,那么就可以利用 Half Gate 技术,将这个 odd gate 的通信量降低到222个密文。
The complete scheme
将电路fff的各个逻辑门拓扑排序,对电线依次标号{1,2,⋯}\{1,2,\cdots\}{1,2,⋯},输出线为iii的逻辑门记为GiG_iGi,它的输入线为a,b<ia,b < ia,b<i
利用 P&P 技术、Half Gate 技术、Free XOR 技术、GRR3 技术,完整的 GC 协议为:
易知 Free XOR 技术使得 even gate 的所需的密文数量为零。可以证明,实现 odd gate 至少需要两个密文。而 Half Gate 技术使用两个密文就完成了 odd gate 的构造。因此,上述的协议达到了最优的通信复杂度。