3.3　混淆电路

混淆电路协议最早由姚期智院士[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.5　混淆表的生成

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

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

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

图3.6　基础混淆电路协议流程