混淆电路简介

 1. 什么是混淆电路？

混淆电路（Garbled Circuit）又称姚氏电路（Yao’s GC），是一种密码学协议，是姚期智院士在1986年提出的 “百万富翁” 问题的解决方案，它同时也被看作是对隐私计算中安全多方计算方向的一种较为简单的实现。所谓“百万富翁”问题，就是说有两个拥有百万资产的富翁，他们都想知道谁更富有，但他们同时都想保护好自己的隐私，都不愿意让对方或者任何第三方知道自己真正拥有多少财富，所以如何在保护好双方隐私的情况下计算出谁更有钱就是混淆电路主要解决的问题。

这里混淆电路解决问题的关键就是电路（Circuit），实际上我们知道任何可计算的问题都可以被转换成逻辑门电路，包括加法电路、乘法电路、比较电路等等。而电路又可以由一个个门（Gate）组成，例如与门（AND）、或门（OR）、非门（NOT）、异或（XOR）等。混淆电路正是利用了这一点，对每个门电路分别进行加密和混淆从而达到安全计算同一函数的效果。

2. 混淆电路的工作原理

混淆电路的核心思想是将双方待计算的函数表示为加密查找表。假设计算函数的输入域很小，那么就可以通过枚举所有输入情况，将每种情况对应的计算结果加密并插入到查找表的条目中，最终通过检索查找表条目，解密获得计算输出。此过程的核心在于：如何加密查找表，如何获得正确解密条目以及如何保证仅能解密一个条目。

在此架构体系下，通用的两方安全计算协议大致步骤为：

① 一方首先将电路加密混淆，然后将混淆的加密查找表给另一方。

② 双方使用不经意传输（OT）使得其中一方可以通过自己的输入选择混淆的查找表。

③ 最后一方可以通过混淆密钥计算出混淆电路标签，并且解密得到计算结果。

所以总的来说，混淆电路的工作原理是使用逻辑电路+OT协议。关于OT的相关知识已在之前的推文中进行了详细的介绍，此处不再详细展开。

假设有两个参与方P1和P2分别拥有数据X1和X2（0或1），他们想共同计算一个函数f(X1, X2)，在姚氏混淆电路协议下，P1和P2会执行如下的步骤（以与门为例，其他门类似）：

1) 生成混淆电路

首先，P1将目标函数f(X1, X2)转换为布尔电路，然后生成一张与门的真值表：

随机生成6个数A0，A1，B0，B1，C0和C1对真值表进行替换（A0代表替换X1=0的位置，其他同理）。于是便能得到进一步的真值表：

之后，P1对替换表中的f(X1, X2)值进行对称加密（加、解密密钥相同），并对加密后的查找表的行顺序进行打乱，防止P2通过真值表的顺序推测出各行的含义。其中的一个混淆加密查找表（Gabled Table）如下：

2) P1与P2进行通信

首先P1将自己的输入发送给P2，比如P1的输入X1=1，P1就会发送替换值A1给P2，这样P2就无法知道P1的原始值了。然后P2通过不经意传输1-out-of-2 OT协议从P1处获得他的输入对应的替换值，由于OT协议的特性，可以让P1不知道P2具体使用的是哪个原始值。最终，P1将与门的混淆加密查找表发给P2。

3) P2评估混淆电路

P2接收到P1发送过来的替换值以及混淆加密查找表后，尝试对电路进行解密。这里假设P1的真实输入值是X1=1，P2自己的真实输入是X1=0，那么目前P2已知的信息有A1，B0两个数据，使用对称加密的密钥对混淆加密查找表进行解密，可以看出只有上表的第四行能够得到结果C0。但这里的解密结果C0仍然是一个随机值，而只有P1知道其中转换的关系。

4) P1和P2共享结果

P2将解密后的结果C0分享给P1，因为P1知道替换值与原始值之间的转换关系，故P1通过转换关系得到最终结果，并分享给P2。

以上就是P1与P2双方通过逻辑电路与OT协议实现了共同安全计算一个函数的功能，整体流程（图1）可以总结如下：首先P1端会生成布尔电路对应的真值表、替换表、加密表以及混淆加密查找表，发送自己输入的替换值和混淆加密查找表给P2，然后P2通过OT协议得到自己的替换值，通过对称密钥对混淆表中的值进行解密，最后，将解密后的结果发送给P1得到最终的真值结果，双方共享真值结果。

图1 混淆电路协议的整体流程

3. 混淆电路的优化

相比于其他安全多方计算技术，例如秘密共享、不经意传输等，混淆电路是一种比较通用的解决方案，其安全性相对较高，但性能一般，尤其是通信量上，因为一个混淆电路会使电路C的大小至少扩大到安全参数倍的大小，故特别不适合带宽受限或WAN网络环境下使用。

针对混淆电路通信量较大问题，其优化思路一般考虑两个方面：一方面，对电路本身的优化，主要目的是减少编译后电路的大小，常用的技术有Point and Permute、Free-XOR、Garbled row reduction等；另一方面，是对电路执行阶段的优化，一是可以通过减少解密混淆真值表的次数，常用的方案有Fast table lookup技术，二是将原来电路的产生与执行两阶段转换成一个阶段，电路的产生和执行共同进行，这个方法较为常用的方案是Pipelined circuit execution。

综上所述，混淆电路作为安全多方计算中的核心技术，对保护数据隐私具有重要作用。尽管面临一些挑战，但随着技术的不断发展和完善，混淆电路将在保护隐私方面发挥越来越重要的作用，推动信息安全领域的进一步发展。