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输入异或门，那么就需要2m个相关的线路标签；而如果采用Garbled Gadgets并直接在电路中使用m输入异或门，就只需要m+1个线路标签。