混淆电路协议最早由姚期智院士 ^[45] 提出，因此也称为姚氏混淆电路（Yao's Garbled Circuit，GC）。混淆电路协议是最著名的MPC协议，很多MPC协议都是在混淆电路协议的基础上设计、构造产生的。尽管混淆电路协议的通信复杂度较高，但其执行轮数是常数，受通信延迟的影响较小，因此一般认为，混淆电路协议在安全两方计算协议中具备最佳的执行效率。

混淆电路协议是一个安全两方计算框架，参与者有生成者（Generator或Garbler，也译作混淆者、电路生成方）和计算者（Evaluator，也译作电路求值方）。协议的主要思想是将函数表示成布尔电路的形式，再由生成者将布尔电路转化为混淆电路形式并发送给计算者，对于计算者，混淆电路与随机数不能区分，因此无法获取生成者的秘密信息。

我们先考虑仅由一个与门 构成的简单布尔电路，其中 是生成者的输入， 是计算者的输入。为了对这个简单电路生成对应的混淆电路，生成者首先为每根线路生成随机的线路标签，包括0标签和1标签，分别用于表示线路值为0和线路值为1的情况，这些标签实际上是一定长度的字符串。随后，生成者计算出逻辑门的真值表，对于这个与门，其真值表的各行内容为 ， ， ， ，为了加快计算速度，不同种类的逻辑门的真值表可以预先计算并储存在内存中，使用时再进行检索。然后，生成者以真值表的每一行中输入线路对应的标签计算出密钥 ，并使用该密钥，对真值表的每一行中输出线路对应的标签进行加密，得到， ， ， ， ，将这4个密文打乱即可得到混淆表。这里的 H 可以是一个哈希函数（Hash Function，也译作散列函数、杂凑函数），而Enc是一个对称加密函数，Enc( x , y )即以 x 作为密钥加密 y 。最后，生成者将混淆电路（在这个例子中为单个门的混淆表）发送给计算者。整个生成流程如图3.5所示。

为了计算这个混淆电路，计算者首先需要获取双方输入值对应的线路标签。生成者可以直接将自己的输入对应的标签 发送给计算者，而对于计算者的标签，则需要使用3.2节介绍的OT协议进行传输。在得到 和 后，计算者生成密钥 并对混淆表进行解密，从而得到正确的门输出线路标签 或 。最后，生成者和计算者进行一定的交互，即可确定计算结果。

而在实际应用中，布尔电路往往由大量的逻辑门组成。为了对复杂的布尔电路生成其混淆电路形式，生成者需要对电路中的所有线路生成0标签和1标签，并为每个逻辑门按上述流程生成对应的混淆表，最后将生成的混淆表和自己的输入对应的线路标签发送给计算者。计算者需要利用OT协议获取自己的输入对应的线路标签，并按上述流程对各个混淆表进行解密。需要注意的是，计算者需要按照拓扑顺序对混淆表逐个进行解密，否则将出现门输入标签未知的情况，因为部分逻辑门的输入线路是某些逻辑门的输出线路。在完成计算后，生成者和计算者通过一定的交互流程（通常是由生成者将电路输出线路的0标签和1标签的哈希值都发送给计算者），确定最终的明文计算结果。

这里给出的只是一个粗略的混淆电路协议实现方案，图3.6给出了大致的执行流程。事实上，这一方案存在着一些细节上的问题和极大的优化空间。例如，当计算者对混淆表进行解密时，他如何确定自己已经得到了正确的解密结果呢？一种可行的做法是在线路标签中添加特殊的标志模式，比如将线路标签的前40位都设置为0，那么当计算者解密得到一个前40位都为0的字符串时，他有较大概率得到了正确的计算结果，按照这一做法，计算者需要解密的平均密文数量由4下降到了2.5。但这一做法降低了协议的安全性，假设我们使用的是80位长度的线路标签，采用这一做法后，线路标签的随机性就从80位降低到了40位，取值范围大小由2 ⁸⁰ 减小到了2 ⁴⁰ ，为了达到与原先相同的安全性，就势必要增加线路标签的长度，但这又导致协议计算量的增加。又例如，密码哈希函数的开销远大于对称加解密操作，那么是否可以用Enc( W _a ,Enc( W _b , W _c ))代替Enc( H ( W _a , W _b ), W _c )？关于这些细节问题和优化问题，研究者们进行了深入的探讨、分析，下面我们就给出一些对于混淆电路协议的优化方案的简单介绍。

3.3.1　point-and-permute优化

point-and-permute优化由Beaver等人 ^[46] 提出，其思想是在线路标签中附加公开的选择比特信息，使得计算者在对逻辑门的混淆表进行解密时，可以预先知道自己需要对哪一个密文进行解密，从而将解密过程的计算量减少为基础方案的1/4。

以单个与门 构成的布尔电路为例，我们用 分别表示附加在线路 a 、 b 的0标签、1标签上的指针比特，在生成混淆表时，生成者不对混淆表的各行密文进行随机打乱，而是将密文 置于混淆表的第 行。显然， 和 、 和 都应是互不相同的，从而在位置上具备区分作用。而计算者在解密时，也只需要先从门输入线路标签的附加信息中得到选择比特，再确定需要解密的密文。

point-and-permute优化方案的优点还在于，它与其他的众多混淆电路优化方案都是适配的，可以同时使用，这也大大增加了该优化的可用性。

3.3.2　free-XOR优化

free-XOR是Kolesnikov和Schneider ^[47] 提出的混淆电路优化方案，正如它的名字所表示的，这一方案在计算异或门时开销极小，甚至可以认为是免费的。

free-XOR优化要求生成者在产生混淆电路的线路标签时，只产生输入线路的标签和非异或门的门输出线路的标签，并且对于这些标签，必须让0标签和1标签之间的距离具有相同的偏移量Δ，即 。在这样的约束下，异或门的门输出标签可以直接由其门输入标签异或而得，对异或门 ，即为 ，相较于原本的复杂密码学操作，简单的异或操作显然可以看作是免费的了。而这样的约束还有另一个作用，在3.2节，我们介绍了COT扩展协议，而符合free-XOR优化方案约束的线路标签也符合COT扩展协议的输入要求，实际上，COT扩展协议本就是为free-XOR优化方案设计的。因此，free-XOR优化相较于基础方案，不仅减少了计算量，在使用OT扩展协议进行线路标签的传输时，还能够减少通信量。

但free-XOR优化也有一些问题。一方面，由于线路标签之间存在一定的相关性，free-XOR优化需要有更强的假设来保证安全性，不能使用基于伪随机数生成器（Pseudo-Random Generator，PRG）的较弱加密方案，而需要使用随机预言机（Random Oracle，RO）对门输出标签进行加密。另一方面，它也与其他的一些混淆电路优化方案不兼容。

free-XOR优化技术还有两种推广，即FleXOR ^[48] 和Garbled Gadgets ^[49] 。在FleXOR优化中，可以使用0、1或2个密文构建异或门的混淆表，具体数量则是由布尔电路的构造和电路中各个门的组合关系决定的。Garbled Gadgets优化则是free-XOR优化在多输入逻辑门上的推广，Ball等人将普通的异或（⊕，这里记作 ）操作考虑为按位加法后按位模2，相应地， 即等价于按位加法后按位模 m 。对一个全部由3输入门构成的电路，Garbled Gadgets将线路标签设置为， ， 从而实现与free-XOR相同的效果。假设需要混淆的电路中存在操作 ，如果我们采用free-XOR优化并使用2输入异或门实现 m 输入异或门，那么就需要2 ^m 个相关的线路标签；而如果采用Garbled Gadgets并直接在电路中使用 m 输入异或门，就只需要 m +1个线路标签。

3.3.3　GRR优化

GRR是Garbled Row Reduction的简称，这类优化的主要思想是减小混淆表的大小。Naor、Pinkas和Sumner提出了第一个GRR方案 ^[50] ，这个方案能够将混淆表的大小由4条密文减小到3条密文，因此也称为GRR3。该方案的主要思想是，混淆表中的密文并不一定要是加密操作的结果，而可以被设置为固定值。常见的做法是将混淆表的第一行设置为全零，那么计算者不需要网络传输，就可以知道该行的内容，因此只需要将3条密文传输给计算者。

Pinkas等人 ^[51] 则给出了另一种形式的GRR优化方案，也称为GRR2。该方案通过多项式插值的方式，将混淆表的大小进一步缩减为2个密文。然而，这一方案不能与free-XOR同时使用，而只与FleXOR兼容。尽管GRR2和FleXOR同时使用能够支持2个密文的非异或门，但这一复合方案在可行性和性能上都不如下一节将要介绍的half-gates优化方案，因此在实际应用中较少被使用。

3.3.4　half-gates优化

half gates是Zahur等人 ^[52] 提出的一种高效的混淆电路构建方式，通过与其他优化技术结合，可以使得每个与门只需生成2个密文，而每个异或门则无须生成密文。其思想是将与门表示成2个半门的异或结果，每个半门都是与门，且参与方知道半门的1个输入。这两个半门分别称为生成者半门和计算者半门，这样命名的原因是我们假设生成者知道生成者半门的1个输入，计算者知道计算者半门的1个输入。

对生成者半门，我们将其表示为 ，并假设生成者在计算开始前就已知 （此时，生成者还不知道自己的输入是什么）。我们按照free-XOR优化的约束，生成2个密文 和 。在计算者对这2个密文进行解密时，根据不同的输入值，可以得到不同的计算结果：如果 ，那么计算者持有 ，可以计算得到 ；如果 ，那么同样计算得到 ；如果 ， ，那么计算者持有 ，并且可以计算得到 。应用point-and-permute技术，根据线路标签 的指针比特可以设定密文在混淆表中的位置，而进一步使用GRR可以减少1个密文。

对计算者半门，我们也表示为 ，并假设计算者在计算开始前已知 （此时，计算者还不知道自己的输入是什么）。生成者会生成密文 和 ，根据 ，计算者可以得到 或 。对于后一种情况，假如计算者知道的是 ，则可以获得 ；假如计算者知道的是 ，则可以得到 ，如果 ，那么计算者持有的线路标签是 ，可以计算得到 ，如果 ，那么计算者持有的线路标签是 ，可以计算得到 。同样地，使用GRR技术，令 ，可以将第一个密文设置为全零，从而让混淆表大小缩减为1个密文。

而为了让2个参与方在都不知道输入值的情况下对与门 进行计算，我们让生成者产生随机比特 r ，并将该与门表示为 。由于 r 是生成者产生的，他自然知道其内容，可以用于构造生成者半门。由于 r 是随机的，且计算方不知道其内容，生成者可以将 传递给计算方作为其已知内容。一种巧妙的做法是将 r 设置为 的指针比特，计算者通过自己持有的 的指针比特，就可以得到 。

总之，通过结合一系列优化方案，half-gates优化方案可以做到以2个密文表示与门、0个密文表示异或门，在求值时，对与门调用2次 H 、对异或门进行1次异或操作即可完成计算。Zahur等人 ^[52] 还证明，这一方案是线性混淆方案中的规模最优方案。 To1WEBebNy4m5ytwU4rZIorCU21kBduQ4x7gJgymCxb/jbSGBwmo7l32UkFv+wnz