安全多方计算：从姚百万富翁到现代隐私计算的工程实践

概述

在数字化时代，数据价值日益凸显，但数据隐私保护的需求同样迫切。一个根本性的矛盾是：数据的价值来自联合分析，但联合分析往往意味着隐私泄露。

安全多方计算（Secure Multi-Party Computation, MPC）为解决这一矛盾提供了密码学级别的解决方案：

多个参与方在不泄露各自私有输入的前提下，联合计算某个函数，最终各方只获得计算结果，对其他方的输入一无所知。

两个百万富翁想知道谁更富有，但不想向对方透露自己的具体财富数字。

理解MPC，就是理解"数据可用不可见"的密码学边界。

起源：百万富翁问题与早期构造

姚氏百万富翁问题

问题描述：Alice 拥有财富 $x$，Bob 拥有财富 $y$。他们想知道 $x > y$ 是否成立，但不向对方透露 $x$ 或 $y$ 的具体值。

姚期智提出的解法基于混淆电路（Garbled Circuit）和不经意传输（Oblivious Transfer）两个核心原语。这个方案虽然在当时的计算和通信开销非常大，但它证明了：

任何可计算函数都可以在不泄露输入的前提下被安全计算。

形式化定义

一个 MPC 协议涉及 $n$ 个参与方 $P_1, P_2, \ldots, P_n$，每个参与方 $P_i$ 持有私有输入 $x_i$。协议的目标是安全计算函数 $f(x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_n)$，其中 $y_i$ 是 $P_i$ 收到的输出。

正确性：诚实参与方收到的输出符合函数定义。

隐私性：任何参与方的视图（View）可以被其输入和输出唯一确定，即除了自己的输入和输出外，不获得任何其他方的输入信息。

形式化表述（基于模拟范式）：对于任何敌手的集合 $S \subset \{P_1, \ldots, P_n\}$，存在一个模拟器 $\text{Sim}_S$ 可以仅使用 $\{x_i\}_{i \in S}$ 和 $\{y_i\}_{i \in S}$ 生成一个与真实协议执行中 $S$ 的视图不可区分的模拟视图。

核心原语

1. 不经意传输（Oblivious Transfer, OT）

不经意传输是MPC的基础构件。最常见的是 1-out-of-2 OT（$\text{OT}_1^2$）：

• 发送方 input: 两个消息 $m_0, m_1$
• 接收方 input: 选择比特 $b \in \{0, 1\}$
• 结果: 接收方获得 $m_b$，但不知道 $m_{1-b}$；发送方不知道 $b$ 的值

发送方 (S)                                    接收方 (R)
  消息 m₀, m₁                               选择比特 b
    |                                           |
    +────────────  OT 协议 ────────────────→+ 
                                          获得 mₘ

关键性质：

• 接收方隐私：发送方无法知道 $b$ 的值
• 发送方隐私：接收方无法知道 $m_{1-b}$

构造方案：

• RSA-based OT（Bellare & Micali, 1989）：基于公钥密码学
• Efficient OT（Impabo & R.O.，2005-2008）：基于离散对数的扩展协议
• ALSZ OT Extension（Asharov et al., 2013）：用少量 base OT 实现任意数量的扩展 OT，每个仅需常数时间

2. 混淆电路（Garbled Circuit）

混淆电路由姚期智在1986年提出，解决两方计算问题：

基本思想：

• 将函数 $f(x,y)$ 表示为布尔电路（AND/OR/XOR门的组合）
• 发送方（Garbler）对电路进行"混淆"——为每条线分配两个随机密钥，对每个门的真值表进行置换加密
• 接收方（Evaluator）通过OT获取对应自己输入的密钥，逐门解密获取输出密钥
• 发送方提供输出线的最终映射（将密钥翻译为明文比特）

电路示例：AND 门
输入线 w₁, w₂    输出线 w₃

真值表：           混淆后：
w₁ w₂ | w₃        K₁  K₂ | E(...)
─────────────    ────────────────
0  0  |  0        K₁₀ K₂₀ | Enc(K₁₀, K₂₀; K₃₀)
0  1  |  0        K₁₀ K₂₁ | Enc(K₁₀, K₂₁; K₃₀)  
1  0  |  0        K₁₁ K₂₀ | Enc(K₁₁, K₂₀; K₃₀)
1  1  |  1        K₁₁ K₂₁ | Enc(K₁₁, K₂₁; K₃₁)

其中 $K_i^b$ 表示线 $i$ 取值 $b$ 对应的随机密钥。

Free XOR 优化（Kolesnikov & Schneider, 2008）：通过为全局设置偏移量 $\Delta$，使得 XOR 门无需加密计算，通信和计算开销大幅降低。

Half-Gates 优化（Zahur, Rosulek & Evans, 2015）：将 AND 门的密文数量从 4 减少到 2，这是目前理论最优的混淆方案。

基础协议

两方场景

#### GMW 协议（Goldreich-Micali-Wigderson, 1987）

GMW 协议基于秘密共享和 OT，是最早实用的两方计算协议：

输入阶段：每个参与方将自己的输入拆分为两个秘密份额（加法秘密共享），自己持有一个，发送给对方。

计算阶段（按门计算）：

• XOR 门：本地计算，无需交互
• AND 门：通过 OT 完成（需要 4 次 OT）

通信复杂度：$O(|C| \cdot \kappa)$，其中 $|C|$ 是电路大小，$\kappa$ 是安全参数。

#### Yao 混淆电路

Yao 协议的通信模式与 GMW 不同：

• Garbler：$O(|C| \cdot \kappa)$（发送整个混淆电路）
• Evaluator：$O(|I| \cdot \kappa)$（通过 OT 获取输入密钥）

• Yao 恒定轮数（1 轮 + 1 OT），但通信量线性于电路大小
• GM 需要对电路中的每一层进行交互，轮数线性于电路深度
• Yao 更适合低延迟网络，GMW 更适合高带宽网络

多方场景（$>2$ 参与方）

#### BGW 协议（Ben-Or, Goldwasser, Wigderson, 1988）

BGW 协议是实现无条件安全的标志性成果：

前提假设：诚实多数（Honest Majority）——诚实方数量 $> n/2$。在线阶段无需加密原语。

核心思想：将基于 Shamir 秘密共享的算术电路（加法门和乘法门）模拟。

加法：本地计算份额之和（线性性质）。

乘法：各方份额相乘后，使用重共享（Resharing）恢复正确次数的多项式相乘结果。具体地，各方 $i$ 将自己的份额与其他方共享，收集至少 $t+1$ 个份额后插值得到乘法结果的 $t$-次共享。

安全条件：在被动安全模型下，敌手控制 $t < n/2$ 方时，BGW 是无条件安全的；在主动安全模型下（需要可靠性），需要 $t < n/3$ 的额外条件。

定理（BGW, 1988）：如果最多 $t$ 个参与方被敌手控制，且 $t < n/2$（被动安全）或 $t < n/3$（主动安全），则任何函数都可以安全计算。

#### GMW 多方扩展

多方 GMW 的诚实多数条件是：敌手最多只能破坏 $n-1$ 方中的 1 方。该协议通过通用 OT 实现 n 方安全计算，不受限于算术电路，可以计算任意函数。

现代协议

SPDZ 系列

SPDZ（Damgård et al., 2012-2013）是最有影响力的现代 MPC 协议之一，其核心创新在于预处理模型（Preprocessing Model）：

离线阶段：生成与函数无关的"乘法三元组"（Beaver Triplets）。这一阶段计算昂贵，但可以在执行具体计算前完成。

在线阶段：使用预处理的三元组快速执行乘法门，仅需少量通信。

关键特性：

• 需要承诺和 MAC 保证份额的正确性
• 通信复杂度从 $O(|C| \cdot n^2 \cdot \kappa)$ 降低到接近 $O(|C| \cdot n \cdot \kappa)$
• 适合恶意安全下的多方计算

其他重要协议

• 算术共享：模加/模乘高效
• 布尔共享：比较、移位操作高效
• YAO 共享：线性操作（如 XOR）高效

恶意安全增强

实际部署中，参与方可能恶意偏离协议。常见防护机制：

• 消息认证码（MAC）：每个份额附带基于预共享密钥的 MAC
• Cut-and-Choose：生成多个混淆电路，验证其中一部分
• 承诺方案：各方在协议早期 commit 到输入
• 可验证秘密共享（VSS）：验证共享的一致性

工程实践

性能挑战

MPC 的主要性能瓶颈：

• 单次 AES 加密（Yao）：~0.1-0.5ms（双方，本地网络）
• 一次乘法三元组（SPDZ）：现代硬件上每个 ~0.01ms
• 5 方 $n=5$ 的安全计算：接近明文计算的 10-100 倍

开源框架

应用场景

#### 1. 数字资产托管

MPC 在加密货币/数字资产托管中的价值：消除单点故障。

• Fireblocks：使用 MPC + HSM 管理超过 1 万亿美元资产（2025 年数据）
• Coinbase：MPC 钱包服务（2019 年推出）
• Qredo：基于 MPC 的去中心化托管网络

#### 2. 隐私保护机器学习（PPML）

MPC 与机器学习的结合带来了"数据可用不可见"的推理和训练：

• 隐私推理：模型持有方不泄露模型参数，用户不泄露输入数据
• 隐私训练：多家机构联合训练模型，数据不离开本地
• MPCMask（Xu et al., 2023）：MPC 生成的对抗性扰动保护图像隐私

联邦学习的梯度聚合面临梯度攻击（Gradient Inversion Attack）风险：

• 攻击者从梯度反推训练数据
• MPC 提供安全聚合（Secure Aggregation），使服务器只能获得聚合梯度，看不到各参与方的个体梯度

#### 4. 基因组学中的隐私计算

基因组数据具有不可更改的隐私性，MPC 允许多家医院联合进行基因组研究而不泄露患者基因信息。

安全性权衡

半诚实 vs 恶意

诚实多数 vs 不诚实多数

诚实多数假设（如 BGW）可以基于信息论安全实现无需公钥原语的协议，效率更高。

不诚实多数假设需要额外机制：

• 使用公钥原语（承诺、零知识证明）
• 性能损失 10-1000x 相比诚实多数方案

总结

从1982年姚期智的百万富翁问题出发，安全多方计算经历了从纯理论到实际可用的完整发展历程：

• 理论基础：混淆电路、GMW、BGW 证明了 MPC 的普适性
• 性能改进：预处理模型（SPDZ）、混合共享模型（ABY）使 MPC 接近实用
• 工程落地：数字资产托管、隐私计算、基因组学等场景已有大规模应用

理解 MPC，就是理解现代密码学如何从"保护数据传输"走向"保护数据计算"——从通信安全走向计算安全的关键跨越。

参考来源

• Yao, A.C. (1982). "Protocols for Secure Computations". *Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS)*, 160-164.
• Yao, A.C. (1986). "How to Generate and Exchange Secrets". *Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS)*, 162-167.
• Goldreich, O., Micali, S., & Wigderson, A. (1987). "How to Play ANY Mental Game — A Completeness Theorem for Protocols with Honest Majority". *Proceedings of the 19th ACM Symposium on Theory of Computing (STOC)*, 218-229.
• Ben-Or, M., Goldwasser, S., & Wigderson, A. (1988). "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computations". *Proceedings of the 20th ACM Symposium on Theory of Computing (STOC)*, 1-10.
• Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012). "Multiparty Computation from Somewhat Homomorphic Encryption". *Advances in Cryptology — CRYPTO 2012*, 643-662.
• Damgård, I., Keller, M., Larraia, E., Pastro, V., & Smart, N. (2013). "Practical Covertly Secure MPC for Dishonest Majority". *Computer Security — ESORICS 2013*, 350-366.
• Kolesnikov, V. & Schneider, T. (2008). "Improved Garbled Circuit: Free XOR Gates and Applications". *ICALP 2008*, 486-498.
• Zahur, S., Rosulek, M., & Evans, D. (2015). "Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits Using Half Gates". *EUROCRYPT 2015*, 220-250.
• Demmler, D., Schneider, T., & Zohner, M. (2015). "ABY — A Framework for Efficient Mixed-Protocol Secure Two-Party Computation". *NDSS 2015*.
• Evans, D., Kolesnikov, V., & Rosulek, M. (2018). "A Pragmatic Introduction to Secure Multi-Party Computation". *Foundations and Trends in Privacy and Security*, 2(2-3).
• Cramer, R., Damgård, I., & Nielsen, J.B. (2015). *Secure Multiparty Computation and Secret Sharing*. Cambridge University Press.
• Lindell, Y. (2020). "Secure Multiparty Computation". *Communications of the ACM*, 63(1), 76-85.
• Aly, A. & Smart, N. (2019). "Practical Secure Matrix Multiparty Computation". *Proceedings of the 17th International Conference on Privacy in Security & Trust*.