Garbled Circuit
Table of Contents
1. Garbled Circuit 简介
混淆电路（Garbled Circuit）由 姚期智 发明，是一个基于半诚实模型（Semi-Honest）的两方安全计算（Two Party Security Computation）协议。
1.1. Garbled Circuit 步骤
使用混淆电路进行安全计算的过程分为下面 6 个步骤：
- The underlying function (e.g., in the millionaires' problem, comparison function) is described as a Boolean circuit with 2-input gates. The circuit is known to both parties. This step can be done beforehand by a third-party.
- Alice garbles (encrypts) the circuit. We call Alice the garbler.
- Alice sends the garbled circuit to Bob along with her encrypted input.
- In order to calculate the circuit, Bob needs to garble his own input as well. To this end, he needs Alice to help him, because only the garbler knows how to encrypt. Finally, Bob can encrypt his input through oblivious transfer. In terms of the definition from above, Bob is the receiver and Alice the sender at this oblivious transfer.
- Bob evaluates (decrypts) the circuit and obtains the encrypted outputs. We call Bob the evaluator.
- Alice and Bob communicate to learn the output.
2. Garbled Circuit 演示实例
假设 Alice 和 Bob 要共同完成“两个比特位的加法器”，但彼此都不想泄露自己的输入，下面将演示一下采用混淆电路实现这个功能。需要说明的是协议完成得到结果后，Alice 可以由结果减去自己的输入推出 Bob 的输入，类似地 Bob 也可以推出 Alice 的输入，我们仅是用这个例子来演示混淆电路的用法。不过，如果它们共同完成的运算是不可逆的运算（如哈希等），那就无法由结果反推出对方的输入了。
第一步、把问题转换为布尔电路，如图 1 所示。
Figure 1: “两个比特位的加法器”对应的布尔电路。 a[\times 1], a[\times 10] 分别表示 Alice 的输入二进数 a 的“个位”和“十位”
第二步，Alice 对电路进行加密。对电路中每个 Gate 的输入进行编码，比如第 1 个 XOR 的输入 0/1 分别被编码为 6816/8677；对每个 Gate 的真值表进行加密，如表 1 所示。
| Input1 | Input2 | Output | Encoding of output |
|---|---|---|---|
| 0 | 0 | 0 | 0 + hash(1, 6816, 6529) |
| 0 | 1 | 1 | 1 + hash(1, 6816, 4872) |
| 1 | 0 | 1 | 1 + hash(1, 8677, 6529) |
| 1 | 1 | 0 | 0 + hash(1, 8677, 4872) |
所有 Gate 进行编码后，得到如图 2 所示的加密电路。
Figure 2: Alice 加密电路
第三步，Alice 把加密后的电路和它自己的输入发送给 Bob。比如 Alice 想输入 [0,1] （由于图中 Alice 的输入 a[\times 1], a[\times 10] 分别表示 a 的“个位”和“十位”，所以，实际上输入的是二进制 10 ），则发送 [6816,3621] 给 Bob。
第四步，假设 Bob 想输入 [1,1] ，但由于电路加密了，他无法直接提交它的输入。 Bob 通过两次 Oblivious Transfer 协议问 Alice [1,1] 分别对应的标签，即 [4872,5851] 。 由于是通过 Oblivious Transfer 协议，所以 Alice 并不知道 Bob 的输入。
第五步， 加密电路的 4 个加密输入 Bob 都知道了，Bob 执行整个加密电路 ，即可得到输出 101 。由于最后一层 Gate 没有加密，所以 Bob 可以得到明文的结果；如果最后一层 Gate 加密了，则 Bob 得到一个加密后的结果，再要 Alice 解决也可以得到最终输出。
第六步，Bob 分享结果给 Alice。
3. 扩展到多方（BMR 协议）
姚期智提出的混淆电路只适应于“两方”安全计算。1990 年，D. Beaver, S. Micali and P. Rogaway 在论文 The round complexity of secure protocols 中把姚期智的混淆电路扩展为了支持“多方”安全计算的协议，这个协议可简称为 BMR 协议。本文不详细介绍它。