标签：导线技术乱码电路求值 oplus left

半门技术

执行乱码电路协议的主要开销是传输乱码门所需的网络带宽开销以及乱码电路生成和求值过程中的计算开销，针对网络带宽开销主要是减少通信量--乱码行缩减技术，针对计算开销主要是对乱码门生成和求值计算开销的优化--FreeXor技术和半门技术。乱码行缩减技术通过设置合理的输出导线标签达到传输3个乱码表项的目的，而在原始GC协议中乱码表项的数目为4。FreeXor针对XOR门进行了优化可以使XOR门不用传输乱码表即可重建输出导线标签，半门技术采用将AND门表示成两个半门XOR的结果，再结合乱码行缩减技术和FreeXor技术可以使AND的乱码表项降低为2个。

1. 乱码行缩减技术(Garbled Row Reduction,GRR)

乱码行缩减技术是一种可以降低每个门密文数量的方法，其关键思想为乱码表中的每个密文不一定非要是导线标签的加密结果，实际上可以考虑将乱码表中的一个密文设置为固定值，这样就不用传输这个密文，最简单的方式就是将其设置为$0^k$。例如针对以下乱码表（AND门)，a和b是两个输入导线，c是输出导线，$a^0,a^1$分别表示导线a的明文值0和1对应的导线标签，同理$b^0,b^1,c^0,c^1$。H是加密函数。

\[\begin{array}{|l|} \hline H\left(a^{1} \| b^{0}\right) \oplus c^{0} \\ \hline H\left(a^{0} \| b^{0}\right) \oplus c^{0} \\ \hline H\left(a^{1} \| b^{1}\right) \oplus c^{1} \\ \hline H\left(a^{0} \| b^{1}\right) \oplus c^{0} \\ \hline \end{array} \]

在生成导线标签时，$c^0,c^1$本身就为任意值，而$H\left(a^{1} \| b^{0}\right)$也为任意值，因此可以让$c^0=H\left(a^{1} \| b^{0}\right)$这样乱码表中的一个密文就总是一个全零的比特串，就不用发送这个密文了。这种方式称作$GRR3$,因为只用为每个门传输3个密文。GRR3看起来很简单，但仍需有几个细节需要注意：1.设置输出导线标签$c^r$是在按照标识比特排序乱码表项之后，也就是说事先计算好$H\left(a^{p_a} \| b^{p_b}\right)$并且将其放在乱码表中正确的位置上之后再计算$c^r$,计算$c^r$之后再计算完整的乱码表。2. 输入导线标签的两个标识比特一共可以标识四个位置，在原始GC中，求值方根据两个标识比特可以很精确的定位到乱码表中的某一项，例如导线a的激活标签的标识比特为0，导线b的激活标签的标识比特为0，那么求值方根据$00$可以定位到乱码表中的第0项；但是现在乱码表中只有3项，如若将第一项设置为全零，那么不用发送第0项后，现在的第0项其实是原本乱码表的第1项，当求值方再根据标识比特解密乱码表时就会出现错误。因此，双方需要约定乱码表中的第几项为全0,更简单的做法是默认第一项为全0，这样当根据标识比特得到乱码表中的位置k后，若$k=00$则直接计算输出导线标签，否则$k=k-1$解密乱码表即可得到输出导线标签。

2. FreeXor技术 (FreeXOR)

FreeXOR技术来自于GESS方案(GESS的介绍：https://www.cnblogs.com/hsa0x7f/p/16477310.html)，GESS方案中为XOR门生成秘密份额的方式很简单。令$S_0,S_1$表示输出导线的秘密明文值，R$\in D_s$, 电路生成方将两个导线的秘密份额设置为$sh10=R,sh11=S_0 \oplus S_1 \oplus R,sh20=S_0 \oplus R,sh21=S_1 \oplus R$。当输入为$sh1i,sh2i$时，直接输出$sh1i\oplus sh2i$.例如$sh11\oplus sh21=(s_0\oplus s_1 \oplus R)\oplus(s_1\oplus R)=s_0.$在GESS方案中最典型的特征是每一条导线对应的两个标签都具有相同的偏移量：令$s_0\oplus s_1=\Delta$,那么有$sh10\oplus sh11=sh20 \oplus sh21=s0\oplus s1=\Delta$这也决定了无法经XOR门的构造方法直接插入到姚氏乱码电路中，因为GC协议要求每个导线标签都是独立随机选取的，如果直接运用会破坏GC的正确性和安全性。破坏正确性是因为GESS方案中XOR门的输出导线秘密值(即输出导线标签)是在秘密分享过程中(可以视为秘密分享完成后)才产生的，而GC协议要求先生成输出导线秘密值(即输出导线标签)然后计算乱码表，换言之，GESS方案XOR不需要生成乱码表，而GC要求生成乱码表。破坏安全性是指GESS方案XOR门生成的秘密值具有相关性，而GC中需要将导线秘密值作为加密密钥使用不能具有相关性，从安全性角度来看，最大的问题是密钥与加密消息之间的相关性。

但是由于GESS方案XOR的优越性：不需要乱码表，秘密份额数量不会增加。如果能将其用于GC无疑会使GC中XOR门的效率提高，由此引出FreeXOR技术。

FressXOR技术通过调整乱码电路导线标签的生成过程解决正确性问题,增强生成乱码表时所使用的加密方案的安全性假设解决安全性问题。FreeXOR要求在生成乱码电路所有导线标签时都使用同一个随机选取的偏移量$\Delta$,也就是说针对一条导线a,令$W_a^0$表示其输入明文值为0的导线标签，$W_a^1=W_a^0\oplus \Delta$为输入明文值1对应的导线标签.前面提到过，导线标签之间的关联性会破坏GC协议的安全性，因此FreeXOR不能使用PRG作为加密方案，而是采用随机预言机加密门的输出导线标签。FreeXOR乱码电路协议与GC几乎完全相同，唯一的区别是针对XOR门求值方不需要对XOR门进行任何的加解密：对于门$f$的两个输入导线标签$W_a=(k_a,p_a),W_b=(k_b,p_b)$直接计算$W_c=W_a\oplus W_b=(k_a\oplus k_b,p_a \oplus p_b)$即可得到输出导线标签。FreeXOR乱码电路协议如下：

参数:

实现功能函数$\mathcal{F}$的布尔电路 C ,

安全参数 $\kappa$ .

令 $H:{0,1}^{*} \mapsto{0,1}^{\kappa+1} $ 表示一个可以看作随机预言机的hash函数.

协议：

随机选择偏移量 $\Delta \in_{R}{0,1}^{\kappa} $.

对于C的每一根输入导线$w_{i}$,随机选择0所对应的导线标签,$w_{i}^{0}=\left(k_{i}^{0}, p_{i}^{0}\right) \in_{R}\{0,1\}^{\kappa+1}$.将另一个对应的导线标签设置为 $w_{i}^{1}=\left(k_{i}^{1}, p_{i}^{1}\right)=\left(k_{i}^{0} \oplus \Delta, p_{i}^{0} \oplus 1\right)$.

对于C的每一个输入门$G_{i}$ (按照拓扑顺序)
(a) 如果 $G_{i}$ 是一个异或门 $w_{c}=\operatorname{XOR}\left(w_{a}, w_{b}\right)$ 输入导线标签依次为$w_{a}^{0}=\left(k_{a}^{0}, p_{a}^{0}\right), w_{b}^{0}=\left(k_{b}^{0}, p_{b}^{0}\right), w_{a}^{1}=\left(k_{a}^{1}, p_{a}^{1}\right), w_{b}^{1}=\left(k_{b}^{1}, p_{b}^{1}\right)$:
i. 将0所对应的输出导线标签设置为 $w_{c}^{0}=\left(k_{a}^{0} \oplus k_{b}^{0}, p_{a}^{0} \oplus p_{b}^{0}\right)$
ii. 将1所对应的输出导线标签设置为 $w_{c}^{1}=\left(k_{a}^{0} \oplus k_{b}^{0} \oplus \Delta, p_{a}^{0} \oplus p_{b}^{0} \oplus 1\right)$.
(b) 如果 $G_{i}$是一个两输入门 $w_{c}=g_{i}\left(w_{a}, w_{b}\right)$ 其输入导线标签为 $w_{a}^{0}=\left(k_{a}^{0}, p_{a}^{0}\right), w_{b}^{0}=\left(k_{b}^{0}, p_{b}^{0}\right), w_{a}^{1}=\left(k_{a}^{1}, p_{a}^{1}\right), w_{b}^{1}=\left(k_{b}^{1}, p_{b}^{1}\right)$:
i. 随机选择0对应的输入导线标签 $w_{c}^{0}=\left(k_{c}^{0}, p_{c}^{0}\right) \in_{R}\{0,1\}^{\kappa+1}$
ii. 设置1所对应的输入导线标签 $w_{c}^{1}=\left(k_{c}^{1}, p_{c}^{1}\right)=\left(k_{c}^{0} \oplus \Delta, p_{c}^{0} \oplus 1\right)$.
iii. 建立 $G_{i}$ 的乱码表. $G_{i}$ 的输入值 $v_{a}, v_{b} \in\{0,1\}$ 共有4种可能性, 对于每一种可能的输入组合设置$e_{v_{a}, v_{b}}=H\left(k_{a}^{v_{a}}\left\|k_{b}^{v_{b}}\right\| i\right) \oplus w_{c}^{g_{i}\left(v_{a}, v_{b}\right)}$.按照输入标识对条目e排序，将条目 $e_{v_{a}, v_{b}}$ 放置在位置$\left\langle p_{a}^{v_{a}}, p_{b}^{v_{b}}\right\rangle$.

计算输出乱码表

3. 半门技术（Half Gates）

半门技术是一种高效的乱码电路构造技术，可以让每个AND门只包含两个密文，且与FreeXor完全兼容。半门技术的关键在于将一个AND门表示成两个半门异或的结果，每一个半门都是一个AND门。每个半门只包含两个密文，然后采用乱码行缩减技术，可以将半门的密文数量降低为一个，这样组合起来一个AND门只包含两个密文。半门技术需要构造两个AND门称为电路生成方半门和电路求值方半门，其中电路生成方已经知晓电路生成方半门的一个输入，电路求值方已知晓电路求值方半门的一个输入。需要注意的是，这两个半门都是电路生成方构造的。接下来详细描述两个半门的构造方法，以及如何将这两个半门合并成一个AND门。

3.1 电路生成方半门 (Generator)

电路生成方半门是一个AND门，其输入导线分别为a和b，其输出导线为c.令$v_a,v_b,v_c$分别表示a,b,c三个导线的明文值，电路生成方半门需要计算的是$v_c=v_a \and v_b$,需要指出的是这里的$v_a,v_b,v_c$并不是原始AND门导线的明文值值，其中电路生成方已知$v_a$。如果$v_a=0$,那么$v_c=0$;如果$v_a=1$,那么$v_c=v_b$.因此电路生成方在不知晓另一个输入的前提下，无法得知电路生成方半门的输出。令$a^0,b^0,c^0$分别表示导线$a,b,c$中0所对应的导线标签。应用FreeXor技术可以知道$b^1=b^0\oplus \Delta$,电路生成方可以计算得到两个密文：

\[\begin{array}{l} H\left(b^{0}\right) \oplus c^{0} \\ H\left(b^{1}\right) \oplus c^{0} \oplus v_{a} \cdot \Delta \end{array} \]

为了能够计算$v_a\and v_b$,电路求值方计算导线b的激活标签的hash值，解密对应的密文。具体来说，如果电路求值方拥有$b^0$则计算$H(b^0)$并与第一个密文异或得到$c^0$(导线值0对应的正确导线标签)；如果$b=b^1$则计算$H(b^1)$并与第二个密文求异或，得到$c^0\oplus v_a\cdot \Delta$,若$v_a=1$则导线求值方得到$c^0\oplus \Delta=c^1$；若$v_a=0$,则导线求值方得到$c^0$。由于导线求值方不知道关于$v_a$的任何信息且电路求值方只能拥有$b^0$或者$b^1$，因此电路生成方半门输出导线的激活标签对于电路求值方来说是完全随机的，也就是说电路求值方也无法得知除了自己应该得到的任何额外信息，符合安全性定义。运用乱码行缩减技术，设置$c^0=H(b^0)$可以让第一个密文全为零，电路生成方只用发送不为0的那个密文给电路求值方。

3.2 电路求值方半门（Evaluator）

电路求值方半门也是电路生成方构造的。其目标也是计算$v_c=v_a \and v_b$,电路求值方已经知晓此电路的一个输入$v_a$,电路生成方不知晓此半门的任何一个输入。电路生成方需要为此电路求值方半门构造两个密文：

\[\begin{array}{l} H\left(a^{0}\right) \oplus c^{0} \\ H\left(a^{1}\right) \oplus c^{0} \oplus b^{0} \end{array} \]

电路求值方已知$v_a$,如果$v_a$=0,那么电路求值方知道自己拥有的导线标签是$a^0$,此时电路求值方计算$H(a^0)$与第一个密文求异或，可以得到输出导线标签$c^0$;如果$v_a=1$,那么电路求值方知道自己拥有的是$a_1$，此时电路求值方计算$H(a^1)$并与第二个密文求异或，得到$c^0\oplus b^0$,如果电路生成方拥有的是$b^0$那么电路求值方可以得到导线标签$c^0=c^0\oplus b^0\oplus b^0$如果电路生成方拥有的是$b^1$,那么电路求值方可以得到$c^1=c^0\oplus b^0\oplus b^1=c^0\oplus \Delta$.而这两种情况对于电路求值方来说是随机的，因此针对电路求值方半门，电路求值方无法得到任何额外信息。由于电路生成方无法得知$a^0$或者$a^1$因此电路生成方依然无法得知最终导线输出标签。同样的利用乱码行缩减技术，电路生成方只需令$c^0=H(a^0)$让第一个密文为全0，然后向电路求值方发送第二个密文。

3.3 两个半门的合并

要想将两个半门合并，首先需要将一个AND门表示成两个AND门异或的形式，考虑这样一个AND门：$v_c=v_a\oplus v_b$,其中$v_c,v_a,v_b$分别表示导线的真值。拆分的技巧是：电路生成方生成一个完全随机的比特r，运用r将一个原始AND门拆分成两个AND门。拆分的方式为：

\[v_{c}=\left(v_{a} \wedge r\right) \oplus\left(v_{a} \wedge\left(r \oplus v_{b}\right)\right) \]

整理一下$v_{c}=\left(v_{a} \wedge r\right) \oplus\left(v_{a} \wedge\left(r \oplus v_{b}\right)\right)=v_a\and \left(r\oplus r\oplus v_b \right)=v_a\and v_b$($\and$表示逻辑与)

可以利用电路生成方半门构造出第一个半门$v_a\and r$。利用电路求值方半门构造出第二个半门，但是电路生成方需要将$r\oplus v_b$的值提供给电路求值方，并且电路生成方不能知晓$r\oplus v_b$的值，需要注意的是电路求值方不能知晓r的值。这个问题可以简单的抽象为电路生成方拥有r,电路求值方拥有$v_b$,双方执行运算的结果是$r\oplus v_b$(这个结果只能由电路求值方获得),且不泄露两方的输入，很明显这个问题可以通过OPRF或者PRF就能解决。但是有一个简单的方法可以在不引入任何额外开销的前提下将$r\oplus v_b$的值传递给电路求值方：电路生成方将r设置为导线b（这里指原始AND门的导线b）中0所对应的导线标签的标识比特$p_b^0$。由于标识比特$p_b^0$本身就是随机选取的，因此电路求值方可以直接从导线b的激活标签上的标识比特$p_b^{v_b}$获取$r\oplus v_b$。具体来说，当$v_b=0$时，电路求值方获得的激活标签为$w_b^0=(k_b^0,p_b^0)$,$p_b^0=r=r\oplus 0=r\oplus v_b$,故$r\oplus v_b=p_b^0$；当$v_b=1$时，电路求值方获得的激活标签为$w_b^1=(k_b^1,p_b^1)$，$p_b^1=p_b^0\oplus 1=r\oplus v_b$,故$p_b^1=r\oplus v_b$。

3.4 整体梳理

在半门技术中电路生成方半门要完成$v_c=v_a\and v_b$的功能，其中$v_a=r$,$v_b=v_a$(指原始AND门的$v_a$),即$v_c=v_a\and r$，电路生成方已知r;电路求值方半门要完成$v_c=v_a\and v_b$的功能,其中$v_a=r\oplus v_b$(指原始AND门的$v_b$),$v_b=v_a$(指原始AND门的$v_a$)即$v_c=v_a\and (r\oplus v_b)$,电路求值方已知$r\oplus v_b$.整个算法的伪代码为：

GbAnd完成的功能就是乱码表的生成，$T_G,T_E$就是最终要发送的密文。Gb完成的功能为乱码电路的生成，包括生成导线标签，生成乱码表($\hat{F}$)，生成解码表($\hat{d}$)。En完成的功能是给出一个导线明文值$x$计算明文值对应的导线标签$X_i$。De完成的功能是根据解码表($\hat{d}$)和最终计算得到的输出导线标签($\hat{Y}$)计算输出导线标签对应的明文值($\hat{y}$)。Ev完成的功能是根据电路生成方发送的激活标签($W_a$)和通过自己选择比特经过OT协议获得的激活标签($W_b$)，结合乱码表，计算输出导线标签($W_i$)。
半门技术的核心在于半门的构造，下面的伪代码比上面讲的更清楚一些：

由于FreeXOR不需要为任何XOR门生成或者发送任何乱码表，因此只需要两个密文，调用两次H,执行两次免费XOR操作即可完成对AND门的求值。在包含低延时局域网的在内的任何场景下，网络带宽引入的开销远远大于加密引入的性能开销，在任何线性类乱码电路方案中，任何由2-输入布尔门组成的电路，门所需的密文数量都不可能少于两个，在线性假设下，半门技术是网络带宽最优方案。

4. 实现

半门技术只是降低了AND门所含密文的数量在实现通用GC协议时仍需按照协议的执行过程来，因此上述算法不能直接实现,需要加以改变将其融入到GC协议中。

我只是简单的实现了运用半门技术的GC协议(只有一个AND门)，双方通信采用的是模拟多线程之间pipe的通信方式，2选1-OT协议也采用的是黑盒的方式：通信双方都将自己的输入上传黑盒中使求值方得到黑盒的输出，双方没有交互，OT协议的半诚实安全协议以及实现在我的博客(https://www.cnblogs.com/hsa0x7f/p/16477310.html)中有介绍。hash函数使用的是sha1。

实现结果：

Alice: 1 Bob:1 求值结果为1