3.1　混淆电路的原理

对计算机实现原理有所了解的人应该知道可计算问题都可以转换为一个个电路，CPU就是由加法电路、比较电路和乘法电路等组合而成的。即使是复杂的计算过程，如深度学习等，也是可以转换成电路的。一个电路由一个个逻辑门组成，比如与门、非门、或门、与非门等。每个逻辑门都有输入端和输出端。图3-1是几个常见的逻辑门。

在经典的混淆电路中，加密和扰乱是以门为单位的。每个门都有一张真值表。表3-1是与门的真值表。

不妨认为两个富翁Alice和Bob的财富是用二进制表示的一个整数。Alice方的财富值用a来表示，a=a4a3a2a1a0=01101；Bob方的财富值用b来表示，b=b4b3b2b1b0=10100。下面先以与门为例来说明混淆电路的工作原理，介绍如何使用混淆电路实现对a和b的与操作。

1）Alice方首先对与门的每根输入线（输入线a和输入线b）生成两个随机的标签来分别对应0和1。其中，标签的比特位长度是k，其取值是算法的安全参数，一般可以设为128。

2）Alice方将与门真值表中的0和1替换成对应的标签，如表3-2所示。

3）Alice方将真值表输入线上的标签作为加密密钥对真值表输出线标签，并使用对称加密算法进行加密，如表3-3所示。

4）Alice方将真值表上的行顺序打乱（见表3-4），这样其他人就无法根据标签值知晓其对应真值表上的哪一行。

5）假设a=a4a3a2a1a0=01101，Alice对5个比特位都生成混淆后的与门真值表，并将它们发送给Bob。表3-5展示了针对第0位比特生成的经混淆后的与门真值表。Bob方需要输入线上的标签值才能根据真值表计算，因此Alice方把值a每个比特位对应的标签发送给Bob，即Alice方发送给Bob。因为标签值是随机生成的，因此Bob方无法从中获取任何信息。

6）真值表计算除了需要输入线上a的值，还需要输入线上b的值。但是，输入线b对应的标签都是由Alice方产生的，为此Bob需要从Alice处获取。假设b=b4b3b2b1b0=10100，对于第0个比特位b0=0，Bob使用2.2节中描述的不经意传输协议，就可以从Alice处获取对应的标签。根据不经意传输协议，Bob是无法获知值的，Alice也无法知晓Bob究竟获取了哪个标签。Bob对每个比特位需使用不经意传输协议获取对应的标签值。

7）对于获取到的标签值，Bob通过遍历从Alice处获取的对应的混淆后的与门真值表（表3-4）的每一行来尝试解密。比如针对第0位，对真值表中的每一行，Bob尝试用去解密，直到解密成功。比如针对表3-5，在计算第二行时就可以成功解密出，而在计算第一行时因为密钥不符，解密就会失败。对每一个比特位解密后，Bob就可以获得。

8）Bob将解密获得的发送给Alice，Alice就可以根据自己生成标签时的对应关系恢复出计算结果00100，而这个结果正是a和b执行与操作的计算结果。

至此，Alice和Bob在保护好各自数据的前提下完成了与操作。同理，我们可以实现异或、或等逻辑门的操作。如果你对计算机逻辑电路有基本了解，应该已经知道两个数的比较操作可以通过多个异或门和与门来实现。如果你对逻辑电路不是很了解也没有关系，把它作为基本结论记下来就可以了。图3-3是将图3-2中单比特比较的逻辑电路组合而成来实现x>y比较操作的逻辑电路。由此可见，我们使用上面提到的混淆电路就可以解决“百万富翁”问题。

显然，上述混淆电路属于半诚实模型，电路本身还有很多优化空间，这里不进一步阐述了。读者可以思考一下优化方法。