LOADING

加载过慢请开启缓存 浏览器默认开启

MPC 基础：从安全计算问题到隐私计算协议

Cryptography 密码学 MPC 隐私计算 安全多方计算 阅读量 0

MPC 基础：从安全计算问题到隐私计算协议

MPC，全称是 Multi-Party Computation，中文通常叫安全多方计算。

一句话概括：

多个参与方各自持有私有输入，大家共同计算一个函数，只泄露约定好的输出，不泄露各自输入的额外信息。

我更愿意从真实协作场景理解 MPC。

假设几家机构想一起做一件事：

  1. 银行想联合识别欺诈风险，但不能把完整客户数据交出去。
  2. 医院想联合统计病例特征，但不能泄露患者隐私。
  3. 平台想做广告转化分析，但广告方和平台都不想暴露完整用户列表。
  4. 多个安全团队想聚合威胁情报，但不想公开自己的全部样本库。
  5. 几家公司想联合训练模型，但原始数据不能离开本机构。

这些场景的共同矛盾是：

数据分散在不同参与方手里
直接共享数据有合规和商业风险
完全不共享又无法完成联合计算

MPC 试图解决的就是这个矛盾。它不是只保护“传输中的数据”或“磁盘上的数据”，而是进一步保护“计算中的数据”。

1. 从明文协作到安全计算

先看一个普通明文协作流程。

Alice 有一份数据 x，Bob 有一份数据 y，他们想计算一个函数：

Alice 输入 x
Bob 输入 y
计算 f(x, y)

最直接的做法是：

  1. Alice 把 x 发给 Bob，Bob 本地计算。
  2. Bob 把 y 发给 Alice，Alice 本地计算。
  3. 双方把数据发给一个第三方，由第三方计算。

这三种做法都不理想。前两种会让一方直接拿到另一方的原始数据，第三种把信任压力转移给了中心节点。

MPC 的目标是把这个流程改成：

Alice 不交出 x
Bob 不交出 y
双方通过协议共同得到 f(x, y)
协议过程中不泄露超过输出本身的信息

也就是说，MPC 要模拟一个“可信计算员”，但现实里又不真正引入这个可信计算员。

这个思想可以覆盖很多函数：

函数类型 例子 输出
比较 f(x, y) = x > y 谁更大
求交 f(X, Y) = X ∩ Y 共同元素
聚合 f(x, y) = sum(x, y) 总和、均值、计数
联合建模 f(D1, D2) = model 模型参数或预测结果
风控规则 多方特征共同判断 命中结果或风险分

姚氏百万富翁问题就是第一类比较函数的经典例子：两个百万富翁想知道谁更有钱，但都不想暴露自己的具体财富。它适合作为 MPC 的历史入口，但真实工程里的 MPC 更常见于数据协作、统计分析和隐私计算系统。

PSI 也是这个框架下的一个函数：

Alice 输入集合 X
Bob 输入集合 Y
双方计算 f(X, Y) = X ∩ Y

所以 PSI 可以看成 MPC 的一个高频特化问题。MPC 是大框架，PSI 是其中非常实用的一类任务。

2. MPC 想模拟什么：理想世界和现实世界

学习 MPC 时，要先理解一个安全定义直觉：理想世界。

理想世界里有一个可信第三方：

  1. Alice 把 x 私下发给可信第三方。
  2. Bob 把 y 私下发给可信第三方。
  3. 可信第三方计算 f(x, y)。
  4. 可信第三方只把约定输出发给对应参与方。

如果真的有这样一个可信第三方，隐私问题就很简单。但现实里没有可信第三方，所以 MPC 协议的目标是：

不用可信第三方
只靠密码协议
让现实世界的协议执行效果
尽量等价于理想世界

这就是 MPC 安全证明里常见的 simulation 思路：如果攻击者在现实协议里看到的一切，都可以由理想世界中的输出模拟出来，那么现实协议没有泄露额外信息。

3. 威胁模型：半诚实、恶意、多数诚实

MPC 里最常见的安全模型有几类。

3.1 半诚实模型

半诚实参与方会按协议执行，但会试图从收到的消息中推断额外信息。

这个模型适合入门，因为协议更简单，效率更高。但真实业务里不能默认所有人都老实执行协议。

3.2 恶意模型

恶意参与方可以偏离协议：

  1. 构造异常输入。
  2. 发送错误消息。
  3. 中途退出。
  4. 尝试让输出错误。
  5. 利用协议细节套取对方隐私。

恶意安全协议通常需要更多证明、认证、承诺、零知识证明或一致性检查，代价也更高。

3.3 诚实多数和非诚实多数

如果有 n 个参与方，安全性经常取决于最多有多少人会串通。

honest majority：诚实参与方超过一半
dishonest majority：攻击者可能控制半数甚至更多参与方

诚实多数下可以做出效率更好的协议。两方计算里没有“多数诚实”可用，所以 2PC 往往需要更重的密码工具。

4. 核心工具一：混淆电路

混淆电路是 Yao 两方安全计算的代表性方案。

它的思路是：

  1. 把要计算的函数写成布尔电路。
  2. 每根导线上的 0/1 不直接用明文表示，而用随机标签表示。
  3. 每个门的真值表被加密打乱。
  4. 一方生成混淆电路，另一方拿到自己输入对应的标签。
  5. 电路执行时只能得到最终输出标签，不能知道中间明文值。

例如一个 AND 门：

a AND b = c

真实电路里输入是 0/1，混淆电路里输入变成标签：

a0_label, a1_label
b0_label, b1_label
c0_label, c1_label

计算方拿到 a 和 b 对应的标签，但不知道标签代表 0 还是 1。通过加密表，它只能一路算到输出。

混淆电路的优点：

  1. 适合两方计算。
  2. 安全直觉清楚。
  3. 任意函数只要能转成电路就能算。

缺点：

  1. 电路规模可能很大。
  2. 比较、加法、乘法、查表等操作都要考虑电路成本。
  3. 对大数据集合类任务，直接用通用混淆电路可能不如专门 PSI 协议高效。

5. 核心工具二：GMW 和按位秘密分享

GMW 协议也是经典 MPC 协议。它通常把每个比特秘密分享给参与方。

以两方 XOR 分享为例：

x = x_A XOR x_B

Alice 持有 x_A，Bob 持有 x_B。单独看任意一份 share，都不知道真实 x。

如果要计算 XOR 门：

z = x XOR y

双方本地就能算：

z_A = x_A XOR y_A
z_B = x_B XOR y_B

因为：

z_A XOR z_B
= x_A XOR y_A XOR x_B XOR y_B
= (x_A XOR x_B) XOR (y_A XOR y_B)
= x XOR y

AND 门就麻烦一些，需要交互或借助 OT。这个特点很重要：

  1. 线性操作通常便宜。
  2. 非线性操作通常贵。

这句话在很多 MPC 系统里都成立，只是底层域可能从比特变成有限域或整数环。

6. 核心工具三：算术秘密分享

很多数据分析和机器学习任务不是按比特电路写的，而是大量加法、乘法、矩阵运算。

这时经常使用算术秘密分享。

设秘密值是 x，在模 p 的有限域里：

x = x1 + x2 + x3 mod p

三个参与方分别持有一份：

P1 持有 x1
P2 持有 x2
P3 持有 x3

只看单独一份，无法知道 x。

加法很简单：

x = x1 + x2 + x3
y = y1 + y2 + y3
z = x + y

每方本地计算：

zi = xi + yi

乘法就不一样：

z = x * y

如果每方直接本地相乘：

zi = xi * yi

拼起来并不等于 x*y，因为缺少交叉项：

(x1 + x2 + x3)(y1 + y2 + y3)

所以乘法通常需要交互或预处理材料。

7. Beaver 三元组：把乘法拆成离线和在线

Beaver triple 是 MPC 里非常重要的预处理工具。

协议提前准备随机值：

a, b, c
c = a * b

这些值本身也以 secret sharing 的形式分给参与方。

当参与方想计算：

z = x * y

可以先打开两个差值：

d = x - a
e = y - b

因为 a 和 b 是随机的，公开 d、e 不会直接泄露 x、y。

然后计算：

xy = c + d*b + e*a + d*e

验证一下：

c + d*b + e*a + d*e
= ab + (x-a)b + (y-b)a + (x-a)(y-b)
= xy

这个技巧把昂贵的乘法相关工作放到离线阶段，在线阶段只需要较少交互。SPDZ、MASCOT、MP-SPDZ 等很多现代 MPC 系统都和这条线有关。

8. OT 和 OTE：MPC 的基础管道

OT 是 Oblivious Transfer，不经意传输。

1-out-of-2 OT 可以写成：

Sender 输入 m0, m1
Receiver 输入选择位 b
Receiver 得到 mb
Receiver 不知道 m(1-b)
Sender 不知道 b

OT 看起来只是一个小功能，但它是很多协议的基础管道：

  1. 混淆电路里，接收方需要拿到自己输入对应的标签，又不能暴露输入。
  2. GMW 的 AND 门计算可以基于 OT。
  3. 很多 PSI 协议依赖 OT 扩展来提高效率。

基础 OT 往往依赖公钥密码，数量一多就很慢。OTE 的目标就是：

少量基础 OT + 大量对称密码操作 = 大量 OT

所以 OTE 是从理论走向工程的关键桥梁之一。你在读 PSI 前沿协议时看到 KKRT、silent OT、VOLE、PCG，这些都和“如何高效生成大量相关随机材料”有关。

9. SPDZ 和现代 MPC 系统

SPDZ 是恶意安全 MPC 中非常有代表性的一条路线。

它的大致思想是：

  1. 用 secret sharing 表示秘密值。
  2. 为 share 加上消息认证码，防止恶意参与方篡改。
  3. 大量乘法三元组在离线阶段生成。
  4. 在线阶段用预处理材料快速完成真实计算。

MP-SPDZ 是一个常被用来学习和实验 MPC 的开源框架，它集成了很多协议族，适合对比不同威胁模型和网络环境下的成本。

从工程视角看，MPC 系统通常要面对：

  1. 协议选择：2PC、3PC、n 方协议，半诚实还是恶意安全。
  2. 数据表示：布尔电路、算术电路、固定点数、整数环、有限域。
  3. 计算结构：线性操作多还是非线性操作多。
  4. 网络成本：轮数、带宽、延迟。
  5. 预处理：离线材料能不能提前生成。
  6. 可验证性：参与方是否会偏离协议。

10. MPC 和 PSI 的关系

PSI 可以用通用 MPC 做：

输入 X, Y
把集合成员关系写成电路或算术表达式
在 MPC 中计算 X ∩ Y

但大多数时候，专门 PSI 协议会更高效，因为集合求交有特殊结构：

  1. 目标通常只是比较相等。
  2. 元素可以先哈希或分桶。
  3. 可以用 OPRF 把元素映射成隐私保护标签。
  4. 可以用 OT/OTE 批量生成比较所需材料。
  5. 可以用布谷鸟哈希减少比较范围。

所以可以这样理解：

MPC 是通用计算框架
PSI 是一个高频隐私计算问题
高性能 PSI 往往借用 MPC 里的 OT、秘密分享、VOLE 等工具
但会针对集合求交做专门优化

这也是为什么学 PSI 前，最好懂一点 MPC；学 MPC 时，PSI 又是最适合落地理解的案例之一。

11. 前沿关注点：MPC 正在解决什么

MPC 现在的前沿不是“能不能安全计算”，而是“能不能在真实业务规模下安全计算”。

11.1 更少通信

网络往往比本地 CPU 更贵，尤其是跨地域、云上、多机构场景。减少通信轮数和总通信量，是很多协议优化的核心目标。

11.2 更强恶意安全

真实业务里不能只假设半诚实。恶意安全、主动安全、可审计、可追责，都会影响协议选择。

11.3 预处理和 PCG

通过伪随机相关生成器 PCG、VOLE、Beaver triples，把大量材料提前生成，让在线阶段更快。

11.4 专用协议和通用 MPC 结合

真实系统经常不是只做一个函数。比如先做 PSI，再做聚合统计，再做模型训练。一个系统可能需要：

  1. PSI 找共同样本。
  2. MPC 做特征聚合。
  3. 差分隐私控制输出泄露。
  4. TEE 或审计系统辅助工程落地。

11.5 后量子安全

传统 OT、OPRF、密钥交换可能依赖 RSA/DH/ECC。长期安全场景需要关注基于 LPN、LWE、格密码等假设的 MPC/PSI 构造。

11.6 隐私机器学习

MPC 用在机器学习里时，真正困难的地方经常不是线性层，而是比较、ReLU、除法、排序、Top-k、浮点数表示。这些都会把协议成本放大。

12. 学习路线

如果是从密码学和 CTF/实验角度入门，可以按这个顺序：

  1. 先理解姚氏百万富翁问题和理想世界/现实世界。
  2. 学会区分半诚实和恶意安全。
  3. 看混淆电路，理解任意函数如何变成安全计算。
  4. 看 GMW，理解按位秘密分享和 OT 的关系。
  5. 看算术秘密分享，理解为什么加法便宜、乘法贵。
  6. 看 Beaver triples，理解离线预处理和在线计算。
  7. 看 SPDZ/MP-SPDZ，理解恶意安全工程系统。
  8. 回到 PSI，看 OPRF、OTE、VOLE、布谷鸟哈希如何服务集合求交。

这样 MPC 和 PSI 就会形成闭环：

MPC 给出安全计算框架
OT/OTE/秘密分享给出基础工具
PSI 是最重要的落地任务之一
现代 PSI 又把 MPC 工具优化到工程规模

13. 入门练习

题 1：百万富翁问题的函数表达

请把“比较谁更有钱”写成一个函数 f(x, y)，并说明输出会泄露什么、不会泄露什么。

题 2：半诚实和恶意参与方

下面行为分别属于半诚实还是恶意？

  1. 按协议发送消息，但保存所有中间消息做离线分析。
  2. 故意发送格式错误的 share。
  3. 输入一个超大集合，试图套出对方所有数据。
  4. 中途退出协议，让对方得不到输出。

题 3：XOR 秘密分享

设：

x = x_A XOR x_B
y = y_A XOR y_B

请证明：

(x_A XOR y_A) XOR (x_B XOR y_B) = x XOR y

并解释为什么 XOR 门可以本地计算。

题 4：Beaver 三元组推导

已知：

c = a * b
d = x - a
e = y - b

请展开证明：

x*y = c + d*b + e*a + d*e

题 5：MPC 和 PSI 的选择

下面任务更适合通用 MPC，还是专门 PSI？

  1. 两家公司只想找共同手机号。
  2. 多方想在共同样本上训练一个简单模型。
  3. 两个机构只想知道黑名单交集数量。
  4. 两方想比较两个私有数字谁更大。

说明理由。

参考资料

  1. Andrew C. Yao, Protocols for Secure Computations, 1982.
  2. Oded Goldreich, Silvio Micali, Avi Wigderson, How to Play any Mental Game, 1987.
  3. Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation, 1988.
  4. Ivan Damgard 等，Multiparty Computation from Somewhat Homomorphic Encryption, 2012.
  5. David Evans, Vladimir Kolesnikov, Mike Rosulek, A Pragmatic Introduction to Secure Multi-Party Computation
  6. MP-SPDZ GitHub 仓库
  7. SecretFlow PSI 文档