MPC协议 — BGW/GMW/SPDZ

日期: 2027-01-05 方向: 隐私技术 / FHE/MPC/TEE 阶段: Phase 4 - FHE & MPC & TEE (Day 244-258) 标签: #MPC #BGW #GMW #SPDZ #BeaverTriples #半诚实 #恶意

---

今日目标

---

1. MPC协议大图景

---

2. 半诚实 vs 恶意敌手

2.1 半诚实 (Semi-honest / Honest-but-curious)

• 严格执行协议（不偏离消息序列、计算正确）
• 但记录所有看到的中间值，事后分析
• 目标：不破坏正确性，仅试图泄露隐私
• 典型应用：内部审计、外包计算（基本信任服务方）

2.2 恶意 (Malicious / Active)

• 任意偏离协议：发错误消息、不发消息、合谋
• 必须保证：
  • 隐私性 (privacy)
  • 正确性 (correctness)
  • 公平性 (fairness — 敌手不能比诚实方先得到结果)
  • input independence (敌手不能把输入和诚实方的相关)

2.3 拓展安全模型

• Covert security (Aumann-Lindell 2007)：偏离会被以概率 ≥ε 检测，作为弱化的恶意
• UC (Universal Composability) Canetti 2001：在任意多协议组合下保持安全 — gold standard
• Adaptive security：corruption可在执行中发生，最强威胁模型

2.4 Output guarantees

关键定理(Cleve 1986)：dishonest majority下fairness不可能（除非概率性弱化）。

---

3. BGW协议（Ben-Or-Goldwasser-Wigderson 1988）

3.1 核心思想

• 用 Shamir SSS 分享每个wire值
• 加法门：本地相加（同Day 248）
• 乘法门：需要降度

3.2 加法门

输入：每方持 $f_a(i), f_b(i)$
输出：每方持 $f_c(i) = f_a(i) + f_b(i)$
0通信

3.3 乘法门（精华）

Step 1：每方本地算 $f_a(i) \cdot f_b(i) = h(i)$，$h$是 $2(t-1)$ 次多项式。

Step 2：Degree reduction

• 每方 $P_i$ 把 $h(i)$ 重新Shamir分享成 $h_i(j)$，给 $P_j$
• 每方 $P_j$ 收到 ${h_i(j)}{i=1}^{n}$，做线性组合： $$f_c(j) = \sum{i=1}^{n} \lambda_i \cdot h_i(j)$$ 其中 $\lambda_i$ 是Lagrange系数（恢复 $h(0) = f_a(0) \cdot f_b(0) = s_a \cdot s_b$）
• 这相当于"重新构造一个 $t-1$ 次多项式 $f_c$ 满足 $f_c(0) = s_a \cdot s_b$"

安全条件：$3t < n$（半诚实），$4t < n$（恶意，perfect security）。

3.4 BGW的意义

• 第一个支持任意函数（finite field上）的MPC
• 信息论安全（不依赖计算假设）
• honest majority前提

---

4. GMW协议（Goldreich-Micali-Wigderson 1987）

4.1 工作在Boolean电路 (XOR + AND)

• Wire用XOR分享：bit $b$ → 各方 $b_i$ 满足 $b = \bigoplus_i b_i$
• XOR门：本地 $c_i = a_i \oplus b_i$ → 输出share自动正确
• AND门：需要1次OT（或类似乘法triple）

4.2 AND门（双方版本）

输入 $(a_1, a_2, b_1, b_2)$ 满足 $a = a_1 \oplus a_2, b = b_1 \oplus b_2$，目标计算 $a \wedge b$ 的XOR分享 $(c_1, c_2)$。

$$a \wedge b = (a_1 \oplus a_2)(b_1 \oplus b_2) = a_1 b_1 \oplus a_1 b_2 \oplus a_2 b_1 \oplus a_2 b_2$$

• $a_1 b_1, a_2 b_2$ 各方本地算
• $a_1 b_2, a_2 b_1$ 是cross-term — 需要OT计算

4.3 OT (Oblivious Transfer)

1-out-of-2 OT：sender有 $(m_0, m_1)$，receiver有 bit $b$，receiver得 $m_b$，sender不知 $b$，receiver不知 $m_{1-b}$。

OT extension (Ishai et al)：用 $\lambda$ 个base OT扩展到任意多OT，每OT只需对称密码学。生产级MPC的核心。

---

5. SPDZ协议（Damgård-Pastro-Smart-Zakarias 2012）

5.1 设计目标

• Dishonest majority（任意 $t < n$ 作恶）
• 恶意安全 + abort
• 高online效率：把昂贵操作放offline预处理

5.2 总体架构

┌──────────────────────────────────────────────────────┐
│ OFFLINE PHASE (data-independent, slow)               │
│ - 生成 Beaver multiplication triples (a, b, c=ab)     │
│ - 生成 random shares & MACs                           │
│ - 用 SHE / OT / Overdrive 等                          │
└──────────────────────────────────────────────────────┘
                   │
                   ▼
┌──────────────────────────────────────────────────────┐
│ ONLINE PHASE (data-dependent, fast)                  │
│ - 输入分享                                            │
│ - 加法本地                                            │
│ - 乘法消耗1个triple + 2轮通信                         │
│ - 输出MAC验证                                         │
└──────────────────────────────────────────────────────┘

5.3 Beaver Triples

事先准备随机三元组 $(a, b, c)$ 满足 $c = a \cdot b$，全部shared。

乘法 $x \cdot y$（$x, y$ shared）：

1. 本地计算 $d = x - a$ 的share，$e = y - b$ 的share
2. 打开 $d, e$（广播）→ 大家知道 $d, e$（但不知 $x, y$，因 $a, b$ 隐藏）
3. 本地计算： $$z = c + d \cdot b_i + e \cdot a_i + d \cdot e$$ 其中 $b_i, a_i$ 是 $b, a$ 的share，$de$ 公开
4. 验证 $z$ 的share = $x \cdot y$ 的share

为什么对： $$x \cdot y = (a + d)(b + e) = ab + ae + bd + de = c + ae + bd + de$$ ✓

通信：每个乘法2轮（打开 $d, e$），其余本地。

5.4 SPDZ的MAC

关键创新：每个share带一个 MAC 标签： $$[x] = (x_i, \alpha_i x_i)_i, \text{ where } \alpha = \sum_i \alpha_i \text{ is a global MAC key (also shared)}$$

打开 $x$ 时各方公开 $x_i, \alpha_i x_i$ → 总和 $\alpha x$。 验证：$\alpha \cdot x \stackrel{?}{=} \sum_i \alpha_i x_i$。 敌手若篡改 $x_i$，需同时篡改 $\alpha_i x_i$ 满足 $\alpha (x_i + \delta) = \alpha_i x_i + \alpha \delta$ — 但 $\alpha$ secret，破解概率 $\le 1/p$。

5.5 性能（2026年水平）

真实benchmark: SCALE-MAMBA (open-source SPDZ), 3-party LAN: 几万乘法/秒；4-party WAN: ~5K mul/s。

---

6. UC (Universal Composability) 框架

6.1 核心思想（Canetti 2001）

定义"理想功能" $\mathcal{F}$（黑盒，magically安全）。证明协议 $\pi$ "emulates" $\mathcal{F}$：在任何环境 $\mathcal{Z}$ 下，$\pi$ 视图与 $\mathcal{F}$ + simulator视图不可区分。

保证：可任意组合，每用 $\pi$ 替换 $\mathcal{F}$ 安全性不丢失。

6.2 应用

• TLS/SSH composition
• 多MPC协议串联（如先KeyGen再Sign）
• ZK + MPC混合

---

7. 真实生产MPC系统

---

8. 三大MPC协议对比

---

9. 性能基准（开源框架）

---

10. 常见陷阱与攻击

10.1 半诚实假设的滥用

误以为"内部敌手不会作恶" → 实际生产中有内鬼/被hack → 应使用恶意安全协议。

10.2 Rushing Attack

恶意方"等"诚实方先发，自己后发好的消息 → 影响fairness。缓解：commit-then-open。

10.3 输入扩展攻击

恶意方故意用奇怪输入（如overflow边界）让协议泄漏信息。缓解：输入约束 + ZK证明input well-formed。

10.4 Beaver triple污染

若Offline阶段triple被破坏（$c \ne ab$）→ Online计算结果错误。缓解：sacrificing（用2x triples，一半检查另一半）。

10.5 MAC key泄漏

SPDZ的全局MAC key一旦泄漏 → 恶意方可任意篡改输出。缓解：MAC key严格隐藏 + abort on validation failure。

10.6 Network timing

WAN下乘法每round 50-100ms latency → 多乘法串联会很慢。优化：batched multiplication, depth reduction.

---

11. 合规视角

• GDPR Article 25 "Privacy by design" — MPC作为data minimization的实现
• 欧盟金融数据共享 (PSD2/Open Banking) — MPC做cross-bank分析（无需共享原数据）
• HIPAA + 23 NYCRR 500（NY金融）— MPC做federated risk analysis
• 中国《数据出境安全评估办法》 — MPC作为数据不出境的合规方案
• Aleo, Inco 等用MPC做threshold decryption应对监管"司法授权解密"

---

12. 关键速查

---

13. 面试题

Q1：BGW vs SPDZ核心区别？

BGW是honest majority（$t<n/3$ semi），信息论安全，乘法本地+1轮通信，不需要offline。SPDZ是dishonest majority（任意 $t<n$ corrupt），计算安全（基于MAC），online高效但需要重的offline triple生成。生产场景多用SPDZ，因为 dishonest majority 更接近现实威胁模型。

Q2：Beaver triple为什么有用？

直接做MPC乘法需要复杂degree reduction（BGW）或OT（GMW）。Beaver观察到：随机$(a,b,c=ab)$可"代理"乘法 — 用 $d=x-a, e=y-b$ 公开后即可恢复 $xy = c + ae + bd + de$。关键：$d, e$ 公开不泄漏 $x, y$（因为 $a, b$ 完全随机）。代价：把昂贵生成放offline。

Q3：MPC vs FHE对比？

MPC：多方协作计算，不必信任单点；通信开销随party数线性。FHE：单方计算密文；密文巨大、计算昂贵但无通信。取舍：

• 多方且对延迟敏感 → MPC
• 单方计算密文 → FHE
• 实践中常FHE+MPC混合：FHE做计算，MPC做threshold decryption（如Inco）

Q4：什么是UC框架？

Universal Composability：定义"理想功能" $\mathcal{F}$（magically安全），证明协议在任何环境下表现等同于 $\mathcal{F}$。最强属性：可任意串联组合而保持安全。生产级MPC都追求UC证明。

Q5：threshold ECDSA为什么比threshold Schnorr难？

Schnorr签名 $s = k + c \cdot d$（线性），可直接Shamir做threshold。ECDSA含 $s = k^{-1}(m + r \cdot d)$，模逆和乘法让线性失效。GG18/GG20/CGGMP用复杂MPC（Paillier或Class group + ZK proofs）才能做malicious-safe threshold ECDSA。这就是为何FROST(Schnorr threshold)只需1.5轮，GG20需要9+轮。

---

14. 明日预告

Day 250：阈值签名实战 — FROST协议 + Lit Protocol + 完整Rust代码（多人协作签Schnorr/Ed25519）。

---

今日产出: spdz.md(本文 ~700行)，含三大协议对比、Beaver triples推导、UC框架、生产系统、合规视角 Lines: ~700