MPC 问题与 Yao 混淆电路

MPC 允许 n 个参与方各自持有私有输入 x_i，在不向彼此泄露输入的情况下共同计算 f(x_1,...,x_n)——就好像由一个受信任的第三方完成了计算。

姚氏 1982 年的百万富翁问题：Alice 和 Bob 想知道谁更富有，但不透露各自的财富。不需要受信任的第三方。MPC 可以通过密码学保证解决这个问题。

1. 隐私：参与方只能了解输出，以及能够从输出中推断出的信息。2. 正确性：即使部分参与方遭到攻破，输出仍然正确。3. 针对半诚实对手和恶意对手，存在不同的方案。

任何函数都可以表示为布尔电路（由 AND、XOR、NOT 门组成）。MPC 协议通常在电路层面运行，安全地计算每个门。

Alice（混淆方）为每条线路分配两个随机标签：一个代表 0，一个代表 1。她使用输入线路标签加密每个门的真值表。Bob（求值方）通过不经意传输（OT）只能获得其输入对应的标签。

Bob 会收到混淆表（每个 AND 门包含 4 个密文）。他使用自己的输入标签准确解密其中一行，得到输出标签，但无法知道该标签代表 0 还是 1。

为每个标签附加一个随机的“选择位”。Bob 使用选择位，以 O(1) 的时间找到正确的混淆行，而不必尝试全部四种解密方式。计算量降低了 4×。

Kolesnikov 与 Schneider（2008 年）提出：选择一个全局偏移量 Δ。这样，对于每条线路都有 label_1 = label_0 ⊕ Δ。XOR 门无需加密即可完成，从而节省约 30% 的带宽。

Zahur 等人（2015 年）证明：每个 AND 门只需要 2 个密文（从 4 个减少而来）。与免费 XOR 结合后，这会使标准混淆电路的带宽需求减半。

经典混淆电路适用于两方。多方扩展方案（例如 BMR 协议）会在所有参与方之间并行进行混淆，但需要 O(n²) 的通信量。对于较小的 n，这种方案具有实用性。

MPC 允许参与方在不泄露输入的情况下共同计算。混淆电路将布尔函数编码为加密的真值表。免费 XOR、半门、点与置换等优化使其具备实用性。OT 会私密地传递 Bob 的输入标签。