混淆电路 - SAGIRI'S BLOG

来源

混淆电路（Garbled Circuit）是姚期智院士在提出“百万富翁”问题之后提出的解决方案，“百万富翁”问题是说有两个百万富翁，他们都想知道谁更富有，但他们都想保护好自己的隐私，都不愿意让对方或者任何第三方知道自己真正拥有多少财富，如何在保护好双方隐私的情况下计算出谁更有钱。

原理

所有可计算问题都可以转换为由逻辑门电路组成的电路，CPU就是由加法电路、比较电路和乘法电路等组合而成的。即使是复杂的计算过程如深度学习等也是可以转换成电路，而混淆电路正是利用了这一点，对每个门电路分别进行加密和混淆从而达到安全传输的效果。

工作原理

我们假设双方为 Alice 和 Bob，此处仅以与门为例，其他逻辑门操作与与门相同

Alice 首先对电路中的每根线随机生成两个标签来对应 0 和 1
如：对于下图线 $ a_{0} $ 来说，Alice 会生成 $ X_{a_{0}}^{0} $ 来代表这条线上的 0，$ X_{a_{0}}^{1} $ 来代表这条线上的 1
Alice 将与门真值表中的 0 和 1 替换为第一步生成的对应的标签，替换后的真值表如下所示（以上图中与门为例）

Input d	Input e	Output f
$ X_{d}^{0} $	$ X_{e}^{0} $	$ X_{f}^{0} $
$ X_{d}^{0} $	$ X_{e}^{1} $	$ X_{f}^{0} $
$ X_{d}^{1} $	$ X_{e}^{0} $	$ X_{f}^{0} $
$ X_{d}^{1} $	$ X_{e}^{1} $	$ X_{f}^{1} $

Alice 将输入线上的标签作为加密密钥，并按顺序对输出进行对称加密，加密过后的真值表如下所示

Output f
$ Enc_{X_{d}^{0}, X_{e}^{0}}(X_{f}^{0}) $
$ Enc_{X_{d}^{0}, X_{e}^{1}}(X_{f}^{0}) $
$ Enc_{X_{d}^{1}, X_{e}^{0}}(X_{f}^{0}) $
$ Enc_{X_{d}^{1}, X_{e}^{1}}(X_{f}^{1}) $

Alice 将第三步生成的真值表顺序打乱，这样可以防止 Bob 通过真值表的顺序推测出各标签的含义，其中一种打乱结果如下：

Output f
$ Enc_{X_{d}^{1}, X_{e}^{0}}(X_{f}^{0}) $
$ Enc_{X_{d}^{1}, X_{e}^{1}}(X_{f}^{1}) $
$ Enc_{X_{d}^{0}, X_{e}^{1}}(X_{f}^{0}) $
$ Enc_{X_{d}^{0}, X_{e}^{0}}(X_{f}^{0}) $

Alice 将所有打乱后的真值表发送给 Bob，并将每个门电路自己输入对应生成的标签发送给 Bob
Bob 通过不经意传输协议（OT），从 Alice 处获取到自己每项输入所对应的标签
现在 Bob 知晓了 Alice 所有的输入对应的标签，也知道自己所有输入对应的标签，就可以根据每个门的标签和真值表进行解密，每个门中有四项，只有一项可以解出一个有效的数据，但是 Bob 不知道这个数据对应的值，因为他收到的真值表的顺序是打乱过的
Bob 将第7步解密得到的所有数据发送给 Alice，Alice 根据自己生成的真值表即可得到对应的值，随后 Alice 将得到的数据发送给 Bob，至此参与计算的双方都得到了运算的结果，并且都不知道对方的输入是什么

标识置换

对于上方 Bob 进行解密时，Bob 如何知道解密出来的结果是对是错呢，有一种方法是 Alice 在每一行的输出标签后方添加 $ \sigma $ 个 0，这样解密后只有 $ \frac{1}{2^{\sigma}} $ 的概率后 $ \sigma $ 个数全为 0，如果不全是则这是个错误的解密结果，但是这种结果效率太低，由此 Beaver 等人提出了标识置换方法。

标识置换的思想就是将密钥的一部分（即第一个密钥的后 $ \lceil log|X| \rceil $ 比特和第二个密钥的后 $ \lceil log|Y| \rceil $ 比特）作为查找表的置换标识，标识密钥应该用于加密哪行密文，根据置换标识对加密好的查找表进行置换。为避免查找表各列分配过程中发生冲突，Alice 必须保证置换标识不会在 $ k_x $ 的密钥空间和 $ k_y $ 的密钥空间中出现冲突。严格来说密钥长度必须要达到相应的安全等级。因此参与方不会直接把密钥中的一部分作为置换标识，而是将置换标识附加在密钥之上，使密钥满足所需的长度要求

参考文献

深入浅出隐私计算：技术解析与应用实践/李伟荣著.北京：机械工业出版社，2022.1