混淆电路 (Garbled Circuit)

1. 百万富翁问题

这个问题是姚期智先生提出的，就是说两个富翁比较谁的财富多，但同时又不想让另一方知道自己财富的具体数额。

这个问题后来就演变成安全两方计算问题(Secure Two-Party Computation)，也就是有 A 和 B 两方，他们分别掌握问题的输入，通过执行这个安全计算的协议，二人都可以获得一个输出，但是互相并不知道对方的输入值。

Garbled Circuit 就是用于实现这样一种协议的。

2. 概念

首先我们需要明确的是，任何的计算机操作都可以使用逻辑门的形式来表示，逻辑门的基本单元有“与”门，“或”门，“非”门，任何其他的复杂逻辑电路都可以由这几个基本单元进行构造。

我们以一个 “与”门为例，

A	B	A 与 B
0	0	0
0	1	0
1	0	0
1	1	1

在这里，A 与 B 的输入为 0 或 1，下面我们介绍如何使用 Garbled Circuit 来实现这样一个过程的：

Alice 分别用 $Z_0$ 和 $Z_1$ 来表示 真值表 中的 0 和 1，然后 Alice 随机选取4个密钥，分别记为 $k_{0a},\ k_{1a},\ k_{0b},\ k_{1b}$ ，并使用这四个密钥来加密 $Z_0$ 和 $Z_1$ ，

$C_{00} = E_{k_{0a}}(E_{k_{0b}(Z_0)}) \\ C_{01} = E_{k_{0a}}(E_{k_{1b}(Z_0)}) \\ C_{10} = E_{k_{1a}}(E_{k_{0b}(Z_0)}) \\ C_{11} = E_{k_{1a}}(E_{k_{1b}(Z_1)})$

加密

$Z_0$ 还是

$Z_1$ ？

加密哪个值，取决于使用的 key，以及在真值表对应的关系。根据真值表中 $0\wedge 0=0$ ，所以使用 $k_{0a}$ 和 $k_{0b}$ 加密的是 $Z_0$

Alice 将这四个密文 顺序打乱 并发送给 Bob，并将自己 输入对应的 密钥也发送给 Bob。假设这里 Alice 的输入为 0，那么 Bob 就得到了 $(C_{00},C_{01},C_{10},C_{11},k_{0a})$ 。

B 的角度

因为对于 Bob 来说， $k_{0a}$ 只是一个随机字符串，因此仅仅凭着这个 key 不能知道 Alice 的输入是 0 还是 1

Bob 使用 OT 协议从 Alice 获取自己输入对应的密钥，假设 Bob 的输入为 0，那么 Bob 获取的密钥就为 $k_{0b}$ ，因为使用了 OT， Alice 并不能确定 Bob 获取的是哪一个密钥。
Bob 使用 $k_{0a}$ 和 $k_{0b}$ 分别对四个密文 $C_{00}, C_{01}, C_{10}, C_{11}$ 进行解密，如果能获取到正确的 $Z$ ，就能得知输出的结果为多少。这里 Bob 得到的结果为 $Z_{0}$ ，另外，Bob 需要把 $Z_{0}$ 的值告诉 Alice，Alice知道了这个值以后自然能得到对应的输出结果。

半诚实

这里的假设是 Alice 与 Bob 都是能正确执行这个协议的，也就是 Semi-Honest (半诚实) 的。半诚实 有时也称作 诚实但好奇的 (Honest but Curious)，意思是他们互相遵循协议，但不破坏协议

3. 举个栗子

我们来举个简单一点的实例，比如² Alice 有 $3$ 块钱， Bob 有 $1$ 块钱，他们希望能通过构造 Garbled Circuit 来比较大小。

首先把他们的金额转化成二进制，即 Alice 金额为 $11$ ，Bob 的金额为 $01$ ，

也就是说，他们的金额都可以用两个 bit 来表示，为了方便说明，记 Alice 的两个bit为 $xy$ ，Bob 的金额为 $x'y'$ ，那么 $xy > x'y'$ 就可以表示为：

$(x\ \wedge\ (\ \neg\ x'\ ))\ \vee\ (\ \neg\ (\ x\ \vee\ x'\ ))\ \wedge\ \ (y\ \wedge\ (\neg\ y' ))$

用真值表表示的话就是：

table

Alice 首先对表中的 0/1用 $Z$ 进行对应标记，然后使用 4 个 a 密钥 $k_{00a},k_{01a},k_{10a},k_{11a}$ 以及 4 个 b 密钥 $k_{00b},k_{01b},k_{10b},k_{11b}$ 进行加密，如：

$... \\ E_{k_{11a}}E_{k_{01b}}(Z_{1}) \\ ...$

类似的，Alice 把自己的密钥 $k_{11a}$ 以及 16 个加密后的真值发送给 Bob，Bob 利用 OT 协议从 Alice 处获取 $k_{01b}$ ，此时双方都不知道对方的输入。

通过解密，Bob 可以得到 $Z_{1}$ ，Bob 把 $Z_{1}$ 发送给 Alice，那么 Alice 就可以知道输出的结果为 1，也就是说自己手中的金额比Bob的大。

Bob 是怎么知道输出的结果呢？

参考一些 Wiki¹ 的说法， "Alice can share her information to Bob or Bob can reveal the output to Alice such that one or both of them learn the output"，也就是说：

Alice 可以事先告诉 Bob $Z$ 的值与 0/1 的对应关系，然后 Bob 把输出的结果告诉 Alice；
或者 Alice 不告诉 Bob $Z$ 的对应关系，而是 Bob 把输出的结果 $Z$ 告诉 Alice，Alice 得到对应的输出后，再把结果告诉 Bob。

如果 Alice 得到的输出为 0 ?

因为 Alice 输入为 11，如果她获得的输出为 0，那么意味着她能够反推出 Bob 的输入为 11，这是不是意味着不安全？

不是的，在定义安全之前，我们先假设有这么一个理想的世界 (Ideal World)，在这个理想的世界里，有一个 “神” 一样的角色，Alice 与 Bob 只需要把他们的输入交给 “神”，“神” 就可以返回给他们对应的输出。

在这个理想的世界里，比如 Alice 输入的是 11，然后得到了 1，那么 Alice 也会知道 Bob 的输入为 11。因此我们对安全的定义为：

如果通过构造现实中的协议，我们能提供与理想世界中同等的功能，那么它就是安全的。正因为在理想世界中，也无法避免出现 “反推出别人的输入” 这种情况，所以在现实世界中，就不能因为这一点来说明系统的不安全，这点是由问题本身带来的。

详细讨论可参看 Boaz 的密码学课件第17.1 节 Ideal vs. Real Model Security³

4. 总结

笼统地说，按照 Yao's garbled circuit 的思路解决百万富翁问题：

所有的这类问题（比较大小，做加减法运算）都可以写成 逻辑门/逻辑电路 的形式；
以 “与门” 为例，对于 A 和 B 的输入，我们可以构建一个真值表，然后 A 可以使用 $Z_0$ 和 $Z_1$ 分别代表真值表中的 0 和 1；
A 选取 2 组密钥，分别代表 A 和 B，每组密钥中有两把密钥，分别对应 0 和 1，A 分别在每组中各取一把，对 $Z$ 进行加密；
A 把加密后的 4 个密文以及自己输入对应的密钥发送给 B，B 从 A 处使用 OT 的方式获取到与自己输入对应的密钥；
B 使用这一对密钥进行解密，因此只能解出一个 $Z$ ，这样的话，根据 $Z$ 与 0/1 的对应关系，就能判断输出的结果。