混淆电路
在安全多方计算领域，一个经典问题是“百万富翁问题”：两位参与者希望比较彼此的财富数额，但均不愿透露具体的数值。这引出了一个根本性的密码学挑战——如何在仅知晓函数定义而不知晓各方输入的情况下，安全地计算该函数的结果。1982年，姚期智院士首次提出了针对该问题的解决方案，其核心思想后来发展为混淆电路（Garbled Circuit）技术。
MPC与百万富翁问题
安全多方计算（Secure Multi-Party Computation, MPC）允许一组参与方在不泄露各自私有输入的前提下，共同计算某个函数。百万富翁问题可形式化为：设有两方 Alice 与 Bob，分别持有私有输入 $ a $ 与 $ b $，目标为计算函数 $ f(a,b) $，且除输出结果外，不泄露任何关于 $ a $ 或 $ b $ 的信息。
混淆电路是解决此类问题的一种通用框架，其核心是将目标函数表示为布尔电路，并通过密码学方法对电路进行混淆处理，使得各方可在不解密对方输入的情况下协同完成计算。
简单来说，混淆电路是一种将计算过程“加密”的技术。它的核心思想是：
- 将想要计算的函数转化为布尔电路（由与门、或门、非门等基本逻辑门组成）
- 对电路中的每个逻辑门进行“混淆”处理
- 参与方在不知道对方输入的情况下，沿着电路逐门计算
- 最终得到正确结果，但整个过程不会泄露任何中间信息
可以看作不经意传输+逻辑电路
混淆电路的基本原理
混淆电路是一种基于布尔电路的密码学协议，其主要步骤包括：
- 电路表示：将待计算函数 $ f $ 转化为由逻辑门（如 AND、OR、XOR）构成的布尔电路。
- 电路混淆：为电路中每一条导线分配随机标签，并对每个逻辑门的真值表进行加密与重排，生成混淆表。
- 安全计算：各方通过不经意传输等协议获取其输入对应的标签，并利用混淆表逐门计算，最终得到输出标签。
- 结果解码：根据预定义的映射关系，将输出标签还原为函数输出值。
在整个过程中，各方仅接触到随机标签与加密后的混淆表，无法推断其他参与方的输入信息。
技术细节
以 AND 门为例的混淆过程
考虑一个两方参与的 AND 门计算：Alice 持有输入 $ x $，Bob 持有输入 $ y $，双方希望计算 $ z = x \land y $，且不泄露 $ x, y $ 的具体值。
1. 标签生成
设导线 $ x, y, z $ 分别对应两个可能的布尔值。为每个值生成随机标签：
- 导线 $ x $：标签 \(X_0\)（对应 0），\(X_1\)（对应 1）
- 导线 $ y $：标签 \(Y_0\)（对应 0），\(Y_1\)（对应 1）
- 导线 $ z $：标签 \(Z_0\)（对应 0），\(Z_1\)（对应 1）
2. 真值表替换
AND 门的标准真值表为：
| $ x $ | $ y $ | $ z = x \land y $ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
将真值表中的布尔值替换为对应标签：
| 输入标签 | 输出标签 |
|---|---|
| $ X_0, Y_0 $ | $ Z_0 $ |
| $ X_0, Y_1 $ | $ Z_0 $ |
| $ X_1, Y_0 $ | $ Z_0 $ |
| $ X_1, Y_1 $ | $ Z_1 $ |
3. 混淆表构造
对每一行使用双重加密：以两个输入标签为密钥，加密输出标签。例如，对第一行计算：
其中 \(\text{Enc}_K(\cdot)\) 表示以 $ K $ 为密钥的对称加密。对四行均进行加密后，随机打乱行序，得到混淆表。
4. 协议执行流程
- 电路生成方（Alice）：生成整个电路的混淆表，并将混淆表发送给 Bob。同时，Alice 将其输入 $ x $ 对应的标签 $ X_x $ 发送给 Bob。
- 标签获取（Bob）：Bob 通过不经意传输协议，从 Alice 处获取其输入 $ y $ 对应的标签 $ Y_y $，且 Alice 无法得知 Bob 的选择。
- 电路计算（Bob）：Bob 使用 $ X_x $ 与 $ Y_y $ 尝试解密混淆表的每一行。仅当两个输入标签均正确时，才能成功解密得到输出标签 $ Z_z $。
- 结果输出：Bob 将输出标签 $ Z_z $ 发回 Alice，双方根据标签映射还原输出值 $ z $。
安全性分析
混淆电路的安全性基于以下密码学假设与设计：
- 标签的伪随机性：所有标签均为随机生成，在计算多项式时间内不可区分于随机字符串。
- 加密算法的安全性：使用的对称加密算法满足 IND-CPA 等安全性质，确保仅持有正确密钥时可解密。
- 不经意传输的安全性：确保接收方能获得所需标签，而发送方无法得知接收方的选择。
- 混淆表的不可区分性：打乱行序后，混淆表不泄露任何关于输入-输出映射的信息。
在半诚实模型下，若上述组件均安全，则混淆电路协议可模拟理想计算过程，满足输入隐私与计算正确性。
实例：XOR 门的混淆表构造
XOR 门的混淆表构造过程如下：
真值表：
| $ x $ | $ y $ | $ z = x \oplus y $ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
标签替换后加密并重排，得到混淆表：
| 密文 |
|---|
| \(\text{Enc}_{X_0}\left( \text{Enc}_{Y_1}(Z_1) \right)\) |
| \(\text{Enc}_{X_1}\left( \text{Enc}_{Y_0}(Z_1) \right)\) |
| \(\text{Enc}_{X_0}\left( \text{Enc}_{Y_0}(Z_0) \right)\) |
| \(\text{Enc}_{X_1}\left( \text{Enc}_{Y_1}(Z_0) \right)\) |
优化技术与发展
原始混淆电路在通信与计算开销上较高，后续研究提出了多种优化方案：
- Free XOR：利用标签的代数结构，使 XOR 门无需混淆表，直接通过标签的异或计算输出标签。
- 点置换：为每个标签附加一个选择比特，使计算方可快速定位混淆表中对应行，避免全表解密尝试。
- 半门技术：将每个逻辑门拆分为两个半门，可将每个门的密文数量从 4 个减少至 2 个。
- 电路压缩与并行化：通过布尔电路优化、批处理与硬件加速提升整体效率。
这些改进使混淆电路能够支持大规模电路（如包含数亿逻辑门的机器学习模型）的安全计算。
应用领域
混淆电路作为 MPC 的核心技术之一，已在多个隐私敏感场景中得到应用：
- 隐私保护机器学习：多个机构可联合训练模型，无需集中原始数据。
- 金融风控：银行间可协作检测欺诈行为，而不共享客户交易明细。
- 安全数据库查询：用户可向数据库提交加密查询，数据库返回结果而不知查询内容。
- 安全电子投票：实现匿名投票与可验证计票。