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]还证明，这一方案是线性混淆方案中的规模最优方案。