混淆电路简介(GC)

混淆电路简介

混淆电路的定义

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

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

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

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

混淆电路的过程

场景引入：假设有 Alice 和 Bob两个人，两个人进行炫富比较，在某个较为私密的场合，他们想比较下谁更加富有，但是又不想让对方知道彼此具体的财富值。我们设定Alice的财富值是

    X
   
  
  
   X
  
 
X，Bob的财富值是

 
  
   
    Y
   
  
  
   Y
  
 
Y，下面通过混淆电路的方式解决 

 
  
   
    X
   
  
  
   X
  
 
X和 

 
  
   
    Y
   
  
  
   Y
  
 
Y 谁大的问题。

这里针对与门进行讲解，整体流程主要包含四大步骤。

第一步： Alice生成混淆电路

1. 首先，Alice生成电路的Truth Table，并且对于真值表按照与门进行计算标注（如下图所示）
2. 然后，Alice进行电路的Truth Table替换（替换值代替真实值，对真实值进行隐藏），例如输 X 0 X_0 X0​代表 X = 0 X=0 X=0，输入 X 1 X_1 X1​代表 X = 1 X=1 X=1，输入 Y 0 Y_0 Y0​代表 Y = 0 Y=0 Y=0，输入 Y 1 Y_1 Y1​代表 Y = 1 Y=1 Y=1，输出 Z 0 Z_0 Z0​代表 Z = 0 Z=0 Z=0，输入 Z 1 Z_1 Z1​代表 Z = 1 Z=1 Z=1（这些值，我们称之为替换值，随机生成，无规律；原始的输入称之为真实值）。
3. 然后，Alice针对替换后的Truth Table的输出进行两次对称加密，并且加密的秘钥分别是Truth Table的两个输入。比如Truth Table的某行两个输入分别是 X 0 X_0 X0​与 Y 0 Y_0 Y0​输出是 Z 0 Z_0 Z0​ ，那么替换后的真值表的某行就是 E n c X 0 , Y 0 ( Z 0 ) Enc_{X_0, Y_0}(Z_0) EncX0​,Y0​​(Z0​) ;
4. 然后，Alice将加密过后的 Truth Table 的行打乱得到 Garbled Table。所以 Garbled Table 的内容和行号就无关了。这就是混淆电路中的混淆二字的由来。

第二步： Alice 和 Bob 通信

1. 首先，Alice将自己的输入发送给 Bob。比如取输入 X = 0 X=0 X=0，Alice就会发送替换值 X 0 X_0 X0​给 Bob。注意：由于 Bob 只是收到 对应的替换值，也就无从知晓 Alice 的原始值了。
2. 然后，Bob通过不经意传输协议，从 Alice 那里获得他的输入对应的替换值，并且通过协议，可以让Alice不知道Bob具体使用的是那个原始值，这里假设Bob的输入是1，所以通过不经意传输最终获取 Y 1 Y_1 Y1​的替换值。具体流程：通过不经意传输协议保证了 Bob 在替换值 Y 0 , Y 1 Y_0, Y_1 Y0​,Y1​中获得一个，但是Alice并不知道Bob获得了哪一个。
3. 然后，Alice 将与门的 Garbled Table发给 Bob。

第三步：Bob evaluate混淆电路

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

第四步：Alice 和 Bob 共享结果

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

网页参考链接:

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