3.2 多方安全计算 (Secure Multi-Party Computation, MPC)
3.2 多方安全计算 (Secure Multi-Party Computation, MPC)
本节摘要：多方各持私密数据，怎么联合计算不泄露各自数据？MPC 给答案。本节讲清楚 MPC 原理（秘密共享+协议）、两大流派（混淆电路/秘密共享）、半诚实 vs 恶意、性能权衡、工程落地。读完你能选对 MPC 方案。
一、MPC 的核心问题（详解）
MPC 工作原理
多方安全计算（MPC）：n 方各持私密输入 x₁,...,xₙ，联合计算函数 f(x₁,...,xₙ)，每方学到结果但不学到其他方的输入。
经典起源——姚期智百万富翁问题（1982）：两个百万富翁想知道谁更富，但都不想透露自己财富。MPC 解决——两方比较财富但不交换财富值。
应用场景：
- 跨组织联合分析：银行联合风控、医院联合研究、广告跨平台归因。
- 隐私拍卖：竞标者联合算最高价不泄露各报价。
- 隐私投票：统计票数不泄露各人选票。
- 联邦统计：多部门联合统计不交换原始数据。
核心保证：
- 输入隐私：任何方学不到其他方输入（除可从结果推断的）。
- 正确性：输出是 f 的正确结果（恶意方不能改）。
- 公平性（可选）：要么所有方得结果，要么都不得。
二、MPC 的基本思路
MPC 用"分而治之"——把数据拆成"份额"，多方各持一份，协议让份额合起来能计算但不暴露原始。
秘密共享（Secret Sharing）：把秘密 s 拆成 n 份 s₁,...,sₙ，分给 n 方。任何 t 份合不出 s（t < 门限），t 份合出 s（t = 门限）。如 Shamir 秘密共享——t-of-n，任意 t 份重构。
MPC 协议：各方把输入秘密共享，在份额上执行计算。每步运算产生新份额，最后合并得结果。全程任何方只持份额，不见原始。
两大流派实现这思路：
- 混淆电路（Garbled Circuit, GC）：把函数编译成布尔电路，加密每个门的真值表，两方协作求值。
- 秘密共享协议：把函数编译成算术电路，各方在份额上交互计算。
三、混淆电路（Garbled Circuit）
混淆电路：姚期智提出，两方计算（一方生成混淆电路，另一方求值）。
流程：
- 电路生成：生成方把函数编译成布尔电路（与/或/非门）。
- 混淆：对每个门，加密真值表——每个输入/输出线对应两个加密标签（代表 0/1），真值表用输入标签加密输出标签。
- 发送：生成方把混淆电路和自己的输入标签发给求值方。
- 输入获取：求值方通过"不经意传输（OT）"拿到自己输入的标签，不泄露输入给生成方。
- 求值：求值方用标签逐门解密，得输出标签，转成输出值。
特点：
- 两方为主：原生两方，扩展到多方复杂。
- 非交互为主：生成方一次发电路，求值方求值，交互少（除 OT）。
- 布尔电路：适合比较、分支等逻辑运算。
- 性能：电路大小决定性能，复杂函数电路大。
不经意传输（OT）：求值方从生成方拿输入标签，但生成方不知道求值方拿了哪个——这是隐私关键。OT 是 MPC 基础组件，有高效扩展（OT 扩展）。
四、秘密共享协议
秘密共享 MPC：多方（≥2）各持份额，交互计算。
代表协议：
- GMW（Goldreich-Micali-Wigderson）：布尔电路，多方，每方持份额，每层门交互。
- BGW（Ben-Or-Goldwasser-Wigderson）：算术电路，多方，Shamir 共享，安全多方。
- SPDZ（Speedz）：恶意安全的算术电路协议，预处理+在线，现代主流。
- Shamir 共享：t-of-n 共享，算术运算在份额上做。
流程（算术电路）：
- 各方把输入 Shamir 共享给其他方。
- 加法：份额直接加（无交互）。
- 乘法：各方交互（用 Beaver 三元组辅助），得乘积份额。
- 最后合并份额得结果。
特点：
- 多方自然：支持 n 方。
- 算术电路：适合加乘密集计算（统计、线性代数、ML）。
- 交互多：每层乘法要交互，通信开销大。
- 预处理：重计算（Beaver 三元组生成）离线做，在线快。
五、半诚实 vs 恶意
MPC 的安全模型：
1. 半诚实（Semi-Honest, Honest-but-Curious）
- 参与方按协议执行，但记录所有信息尝试推断。
- 协议保证：从协议记录不能推断其他方输入。
- 简单、性能好，多数 MPC 协议先证半诚实。
2. 恶意（Malicious）
- 参与方可能任意偏离——输入假数据、错误计算、中途退出、串通。
- 协议保证：即使恶意方作弊，要么被检测（中止），要么不能破坏正确性/隐私。
- 加机制：MAC 校验（验证计算正确）、承诺（防中途改输入）、零知识证明（证明按协议执行）。
- 性能开销大——比半诚实慢 2-10 倍。
3. 隐蔽（Covert）
- 介于——参与方可能作弊，但怕被发现（声誉损失）。
- 协议保证作弊以高概率被发现。
- 性能介于半诚实和恶意。
选模型：合同约束的合作伙伴半诚实够，跨竞争企业要恶意，怕声誉损失的隐蔽够。
六、MPC 的性能
MPC 性能是工程核心：
1. 计算开销：
- GC：电路大小决定，每门加密/解密，慢 10-100 倍。
- 秘密共享：乘法交互，慢 100-1000 倍。
- 预处理能加速在线（离线做重计算）。
2. 通信开销：
- GC：一次发电路，通信大但少轮。
- 秘密共享：每层乘法一轮交互，轮次多，通信总量大。
- 多方时通信按 O(n²) 增长（每对交互）。
3. 轮次：
- GC：常数轮（1-2 轮 + OT）。
- 秘密共享：乘法深度决定轮次，深电路轮多。
- 轮次影响延迟——高延迟网络下轮次敏感。
4. 扩展性：
- 两方 MPC 性能好，多方（>10）性能下降明显。
- 门限 t（容忍 t 方串通）影响——t 大协议复杂。
5. 函数复杂度：
- 简单函数（求和、比较）快，复杂函数（ML 训练）慢。
- 非线性（比较、分支）在算术电路中贵（要转布尔或近似）。
七、MPC 的工程落地
1. 框架：
- MP-SPDZ：多协议框架，支持多种 MPC 变体，研究/工业用。
- CrypTen：Meta 开源，PyTorch 风格，ML 友好。
- TF-Encrypted：TensorFlow 隐私 ML。
- Concrete-ML：Zama，结合 HE 和 MPC。
- Sharemind：商用 MPC 平台。
- Privy：多方隐私计算框架。
2. 应用案例：
- Boston Women's Workforce Council：用 MPC 让波士顿企业联合统计薪酬差距，不交换薪资数据。
- Google Ads 归因：用 MPC 跨平台广告归因，不暴露用户。
- 密码泄露检测：Google/Microsoft 用 MPC 让用户检查密码是否泄露不暴露密码。
- 隐私基因组：iDASH 用 MPC 联合基因分析。
3. 部署要点：
- 选流派：两方逻辑运算用 GC，多方算术用秘密共享。
- 选安全模型：半诚实够就别用恶意（性能差）。
- 用预处理：离线做重计算，在线快。
- 评估通信：网络带宽/延迟是瓶颈，多方时尤甚。
- 简化函数：把函数写成 MPC 友好形式（少乘法、少非线性）。
- 门限选择：容忍 t 方串通，t 大协议复杂，按信任选。
八、MPC 在 PETs 中的定位
1. 多方联合场景：MPC 是"多方各持数据联合算"的首选——跨组织合作、联邦统计。
2. 和 HE 互补：HE 适合单方外包，MPC 适合多方联合。混合（HE+MPC）——HE 做重计算，MPC 做关键交互。
3. 和 TEE 信任权衡：MPC 不依赖硬件信任（数学证明安全），TEE 依赖硬件。能接受信任硬件用 TEE（快），不能接受用 MPC（慢但可信）。
4. 不是银弹：MPC 通信重、性能慢、函数要 MPC 友好——适合低频高价值多方合作，不适合高频实时。
⚠️ 常见误读：以为"MPC 就是多方加密计算"。MPC 是多方在份额上交互计算，不是"各自加密后合"。秘密共享是核心，每方持份额不见原始。
💡 关键直觉：MPC 让多方各持私密输入联合计算不泄露输入。两大流派——混淆电路（GC，两方布尔电路，少轮，姚期智）、秘密共享（多方算术，交互多，GMW/BGW/SPDZ）。安全模型半诚实（只偷看）/恶意（任意作弊，加 MAC/承诺/ZKP）/隐蔽（怕被发现）。性能慢 10-1000x、通信重、轮次敏感。框架 MP-SPDZ/CrypTen。适合多方联合场景，和 HE/TEE 互补，不是银弹。
一节小结
- MPC 核心：多方各持私密输入联合算 f，学到结果不学输入，保证输入隐私/正确性/公平性。
- 起源：姚期智百万富翁问题（1982），比较财富不交换财富。
- 基本思路：秘密共享拆数据成份额，协议在份额上计算，合并得结果。
- 混淆电路 GC：两方，布尔电路，加密真值表，OT 获取输入标签，少轮，适合比较/分支。
- 秘密共享协议：多方，算术电路，Shamir 共享，乘法用 Beaver 三元组交互，GMW/BGW/SPDZ，适合加乘密集。
- 安全模型：半诚实（只偷看，简单）、恶意（任意作弊，加 MAC/承诺/ZKP，慢 2-10x）、隐蔽（怕被发现）。
- 性能：计算慢 10-1000x、通信重（多方 O(n²)）、轮次敏感（深电路轮多）、预处理加速在线。
- 框架：MP-SPDZ（多协议）、CrypTen（PyTorch ML）、TF-Encrypted、Concrete-ML、Sharemind。
- 案例：波士顿薪酬统计、Google 广告归因、密码泄露检测、隐私基因组。
- 定位：多方联合首选，和 HE（单方外包）/TEE（信任硬件）互补，不是银弹（低频高价值多方合作）。