混淆电路简介(GC)

  混淆电路是一种密码学协议，由姚期智教授在80年代针对安全计算所提出的概念。其效果就是：当几个通信方需要一起输入某些数据，然后通过同一个函数计算出一个结果。但是通信的各方都不希望其他人知道自己的输入是什么，此时利用混淆电路协议即可完成目的。

  在这里关键词是电路，实际上所有可计算问题都可以转换为各个不同的电路，例如加法电路，比较电路，乘法电路等。而电路是由一个个门（gate）组成，例如与门，非门，或门，与非门等。

  混淆电路里的多方的共同计算是通过电路的方式来实现，例如下图所示，Alice和Bob要进行多方计算，他们首先需要构建一个由与门，或门，非门，与非门组成的布尔逻辑电路，每个门都包括输入线，输出线。

  混淆电路则通过加密和扰乱这些电路的值来掩盖信息，而这些加密和扰乱是以门为单位，每个门都有一张真值表。

混淆电路的过程：针对与门进行讲解，整体流程主要包含四大步骤

第一步： Alice生成混淆电路

1. 首先，Alice生成电路的Truth Table，并且对于真值表按照与门进行计算标注（如下图所示）
   

2. 然后，Alice进行电路的Truth Table替换（替换值代替真实值，对真实值进行隐藏），例如输$X_0$代表$X=0$，输入$X_1$代表$X=1$，输入$Y_0$代表$Y=0$，输入$Y_1$代表$Y=1$，输出$Z_0$代表$Z=0$，输入$Z_1$代表$Z=1$（这些值，我们称之为替换值，随机生成，无规律；原始的输入称之为真实值）。
   

3. 然后，Alice针对替换后的Truth Table的输出进行两次对称加密，并且加密的秘钥分别是Truth Table的两个输入。比如Truth Table的某行两个输入分别是$X_0$与$Y_0$输出是$Z_0$ ，那么替换后的真值表的某行就是$En{c}_{X_0,Y_0}(Z_0)$ ;
   

4. 然后，Alice将加密过后的 Truth Table 的行打乱得到 Garbled Table。所以 Garbled Table 的内容和行号就无关了。这就是混淆电路中的混淆二字的由来。
   

第二步： Alice 和 Bob 通信

1. 首先，Alice将自己的输入发送给 Bob。比如取输入$X=0$，Alice就会发送替换值$X_0$给 Bob。注意：由于 Bob 只是收到 对应的替换值，也就无从知晓 Alice 的原始值了。

2. 然后，Bob通过不经意传输协议，从 Alice 那里获得他的输入对应的替换值，并且通过协议，可以让Alice不知道Bob具体使用的是那个原始值，这里假设Bob的输入是1，所以通过不经意传输最终获取$Y_1$的替换值。具体流程：通过不经意传输协议保证了 Bob 在替换值$Y_0,Y_1$中获得一个，但是Alice并不知道Bob获得了哪一个。

3. 然后，Alice 将与门的 Garbled Table发给 Bob。
   

第三步：Bob evaluate混淆电路

1. 首先，Alice和Bob通信完成之后，Bob尝试进行电路解密，目前Bob已知的信息有输入$X_0$ 和$Y_1$ ，所以使用这两个值，对于Garbled Table的四行进行解密，可以看到，这里只有第三行是可以解密成功的。
2. 然后，Bob虽然解密成功，但是由于解密出的$Z_0$仍然是替换值（非原始值0），所以无法获得其他信息。

第四步：Alice 和 Bob 共享结果

• 最后 Alice 和 Bob 共享结果。Bob分享解密后结果$Z_0$给Alice，Alice知道替换值与原始值的替换关系，进行替换，并且可以将最终结果分享给Bob。

网页参考链接:

1. 【隐私计算笔谈】MPC系列专题（三）：不经意传输与混淆电路
2. 安全多方计算之百万富翁问题
3. 隐私计算基础组件系列-混淆电路
4. MPC系列–信息论安全的混淆电路
5. Garbled Circuits介绍 - 1 引言