GMW 1987 — 任何函数都能让多方安全地一起算

是什么

GMW 协议（Goldreich-Micali-Wigderson 1987）是一套让多个互不信任的参与者，在不泄露各自秘密输入的前提下，共同计算任意约定函数的方法。

日常类比：想象五家竞争对手要比谁销售额最高，但谁也不愿意把自己的数字告诉别人。GMW 协议就像一个”公正的盲盒裁判”——它让五家公司把数字锁进密封信封，交给这套协议运行，最终只报出”A 公司最高”，没人知道其他人的具体数字。

GMW 的核心贡献是一个”通用性定理”：只要诚实参与者超过半数，任意函数都可以被这样安全地计算。它把”多方安全计算（MPC）“从”特定问题的巧妙技巧”变成了”有理论保证的通用框架”。

具体做法：把要计算的函数编译成布尔电路（由 AND 门和 XOR 门组成），然后对每个门单独设计安全子协议。XOR 门几乎免费（各方把秘密份额异或一下就行），AND 门借助”不经意传输”（OT）实现。两种门组合，理论上就能安全地算任何可计算函数。

为什么重要

不理解 GMW，下面这些事都没法解释：

为什么联邦学习、隐私计算、安全数据联合建模这些”热词”有理论依据——它们都建在 GMW 的通用性定理之上
为什么现代 MPC 框架（SPDZ、ABY、MP-SPDZ）可以自动把 Python 函数变成隐私协议——GMW 证明了这在理论上永远可行
为什么”诚实多数”是那么多安全协议的前提假设——GMW 就是从这个假设出发的第一个通用结论
为什么零知识证明、秘密分享、不经意传输这三个原语能”凑成”一整套安全计算体系——GMW 是第一个把它们串起来的论文

核心要点

GMW 协议可以拆成三个关键机制：

秘密分享（Secret Sharing）：每个参与者把自己的输入用 Shamir (t, n) 门限方案分成 n 份”碎片”，分发给其他 n-1 人（n 是参与总人数，t 是重建原始值所需的最少参与方数）。类比：把一把钥匙磨成 n 块碎片，任意 t+1 块才能拼出完整钥匙，少于 t+1 块什么都看不出来。这样任何单一参与者持有的碎片都无法还原出原始输入。
逐门安全计算（Gate-by-Gate Evaluation）：布尔电路的每个门都有对应的安全子协议。XOR 门（异或）：因为秘密分享是线性的，各方只需对自己的碎片做本地异或，无需通信，结果依然是正确的碎片组合。AND 门（与）：非线性的，需要一次”不经意传输”（OT）——这是通信的主要来源，每个 AND 门要 OT 一次。
不经意传输（Oblivious Transfer，OT）：OT 是一个”选 1 出 2 不泄露选择”的密码原语。先看类比：邮局放了两封信（信 A 和信 B），你只能拿一封，但邮局不知道你拿了哪封，且你不能同时读两封的内容。在协议里，发送方有两条候选消息（信 A、信 B），接收方选其中一条，拿到那条消息后：发送方不知道你选了哪条，接收方也不知道另一条的内容。AND 门的安全计算正好可以套进这个”选 1 不泄露”的框架来实现。

实践案例

案例 1：多家医院联合统计发病率（不共享病历）

场景：三家医院想统计某种罕见病的全国发病率，但各家都不愿把患者数据交给其他医院或第三方。

用 GMW 协议的思路：

# 伪代码示意（非生产可用，仅展示思路）
# 每家医院持有自己的患者人数 count_i（私密）

# Step 1: 秘密分享各自的 count
# threshold=2 意味着至少 2 方才能重建原始值；n_parties=3 是总参与医院数
shares = shamir_split(my_count, threshold=2, n_parties=3)
send_shares_to_others(shares)

# Step 2: 安全求和
# XOR 门（加法在整数域上类比）：本地直接加自己持有的碎片
local_sum_share = my_count_share + received_share_from_b + received_share_from_c

# Step 3: 重建结果（所有人一起公布自己的碎片）
total_count = shamir_reconstruct([share_a, share_b, share_c])
# 最终结果：总发病人数，没人知道其他医院的 count

逐部分解释：

shamir_split：把你的数据切成碎片，每家医院拿到不同碎片
求和不需要看原始值：碎片可以直接相加（Shamir 方案是线性的）
最后只公布重建后的总数，不泄露任何单家的 count

案例 2：隐私保护竞价（谁出价最高，但金额保密）

场景：五家公司竞标一个项目，裁判需要宣布谁中标，但所有人的出价必须保密。

GMW 协议把”比较最大值”编译为布尔电路：

比较两个数 a vs b 的布尔电路：
a = a_{k-1} ... a_1 a_0  （k 位二进制）
b = b_{k-1} ... b_1 b_0

从最高位开始逐位比较：
if a_i > b_i → a wins（剩余位不影响）
if a_i < b_i → b wins
if a_i = b_i → 继续比下一位

每次比较 = 若干 AND 门 + XOR 门的组合

GMW 对电路中的每个 AND 门执行 OT，对每个 XOR 门做本地计算。最终输出”A 公司中标”，没有人知道其他公司的具体出价。

# 伪代码：单个 AND 门如何用 OT 安全计算
# 参与方 A 持有 bit_a（出价某一位的秘密份额），参与方 B 持有 bit_b
# 目标：双方安全计算 bit_a AND bit_b，谁也不知道对方的原始 bit

# 参与方 A 扮演 OT 发送方，生成两条候选消息
r = random_bit()                        # A 的随机掩码
msg0 = r                                # 如果 B 选 0，返回 r
msg1 = bit_a XOR r                      # 如果 B 选 1，返回 bit_a XOR r

# 参与方 B 扮演 OT 接收方，用自己的 bit_b 选择其中一条
received = oblivious_transfer(msg0, msg1, choice=bit_b)  # B 得到 msg_{bit_b}

# 结果：A 持有 r，B 持有 received；两者 XOR 才是 AND 门真实输出
# 双方都只知道自己那一半，无法单独推断 AND 结果

代价：k 位数字、n 方参与，电路约 O(k·n) 个门，每个 AND 门一次 OT，总通信量 O(k·n²)。

案例 3：分布式机器学习中的安全梯度聚合

名词先解释：梯度是机器学习模型训练时每次迭代产生的”调参方向”——可以理解为一组描述”参数应该往哪儿移动”的数字向量。多家公司联合训练模型时，每方需要上传自己数据计算出的梯度，但上传原始梯度可能泄露各自的私有数据。

场景：多个设备（手机/机构）参与联邦学习，服务器要聚合梯度但不能看到任何设备的原始梯度。

# 类 GMW 的安全求和协议示意
# 每个参与方 i 持有梯度向量 grad_i（私密）

# Step 1：参与方 i 把梯度按维度做秘密分享
for dim in range(gradient_dim):
    shares[dim] = shamir_split(grad_i[dim], t=threshold, n=n_parties)
    distribute(shares[dim])

# Step 2：所有参与方本地加各维度碎片（XOR/加法门，无需通信）
local_agg_share = sum(received_shares_per_dim)

# Step 3：各方公布聚合结果的碎片，服务器重建
aggregated_gradient = shamir_reconstruct(agg_shares_from_all_parties)
# 服务器拿到聚合梯度，看不到任何人的原始 grad_i

关键点：如果聚合函数只有加法，全程只需要秘密分享，不需要 OT（无 AND 门），通信量大幅降低。GMW 对非线性函数（如比较大小、ReLU）才需要 AND 门的 OT 开销。

踩过的坑

诚实多数是硬性前提，不是软性建议：基础 GMW 协议只在恶意方数量严格小于 n/2 时保证安全。若一半及以上的参与者合谋，恶意方能从碎片中还原其他人的输入——协议直接失效，没有降级模式。
AND 门是性能杀手：每个 AND 门都需要一次 OT，而现实函数编译成布尔电路后往往有数百万个 AND 门（AES 电路约 3.4 万个 AND 门，神经网络推理则更多）。直接用基础 GMW 在百万门电路上跑会慢到无法实用，必须用 OT Extension（IKNP 2003）把通信量压缩 1000 倍。
半诚实与恶意模型天壤之别：基础 GMW 只对”遵守协议流程但试图推断输入”的半诚实（半可信）方安全。对付会主动撒谎、篡改消息的恶意方，需要在 AND 门计算时附加零知识证明，协议复杂度倍增。不要把两个安全模型混在一个系统里描述。
布尔电路转换代价被低估：把”求两个浮点数的乘积”或”计算平均数”等操作编译成布尔电路，电路规模会远大于直觉预期。实践中常用混合协议（算术秘密分享处理加法，布尔电路处理比较），而不是把所有运算都塞进 GMW 的布尔电路框架。

适用 vs 不适用场景

适用：

诚实多数假设成立（如学术合作、受监管机构间）、且参与方都会遵守协议流程
被计算函数以加法为主（XOR 门多，AND 门少）——如联邦统计、安全求和
安全性要求比性能要求更高的场景（离线/批量运算可接受小时级延迟）
需要理论安全证明的系统，zk-snark 验证等对正确性有形式化要求的场景

不适用：

恶意方可能超过 n/2 的开放互联网场景 → 需要 BGW 协议（信息论安全）或 SPDZ 系列（恶意安全）
实时交互应用（金融交易、在线竞价）→ 毫秒级延迟无法接受 GMW 的 OT 轮次，考虑 yao-garbled-circuits-1986（两方）或 SPDZ 预处理模型
仅两方场景 → yao-garbled-circuits-1986 的乱码电路通常更高效
函数含大量非线性运算（矩阵乘法、排序）→ 用算术秘密分享 + SPDZ，或混合 Yao+GMW 框架

历史小故事（可跳过）

1982 年：姚期智（Andrew Yao）在 FOCS 1982 提出”百万富翁问题”：两个富翁想知道谁更富有但都不愿透露财富，这是两方安全计算的第一次形式化表达。
1986 年：Yao 在 FOCS 1986 给出第一个通用方案——乱码电路（Garbled Circuit），解决了任意两方安全计算问题，但只限于两方。
1987 年：Goldreich、Micali、Wigderson 在 STOC 1987 把这个框架推广到任意 n 方，以”任何智力游戏都能玩”（How to Play any Mental Game）为标题，首次证明通用多方安全计算在诚实多数下可行。
1988 年：Ben-Or、Goldwasser、Wigderson（BGW）在 STOC 1988 独立给出信息论安全版本——不依赖任何计算复杂度假设，只要诚实方超过 2/3（n > 3t），即便密码学假设被打破也仍然安全；代价是安全阈值更严格。
2003 年：Ishai 等提出 OT Extension（IKNP），把 GMW 中每个 AND 门的通信从”一次完整 OT”压缩到”几乎零成本”，使实用 MPC 成为可能。
2010 年代至今：GMW 框架被 SPDZ、ABY、MP-SPDZ 等工程框架继承，隐私计算、联邦学习等工业应用都建在这条理论脉络上。

学到什么

通用性来自”可以把函数变成电路”：布尔电路是通用计算模型，GMW 只需要处理好”一根线上的秘密数”和”两种门的安全操作”，就自动继承了通用计算的能力——这是把”特殊问题技巧”变成”通用框架”的典型范式
安全性从密码原语的组合中涌现：秘密分享（信息论安全）+ 不经意传输（计算安全）两个各自解决局部问题的工具，组合后解决了更大的问题，且可形式化证明安全
诚实多数假设是整个体系的地基：很多复杂的安全性质都建在”大多数参与者诚实”这个假设上；当这个假设不成立时，代价是指数级增加——诚实多数 → 恶意多数的跨越代价昂贵
理论正确 ≠ 工程可用：GMW 1987 证明了”可以做”，但要真正工程落地还差 16 年（2003 年 OT Extension）加另外十年的工程迭代——基础理论和实用系统之间的鸿沟是密码学工程的常态

关联

yao-garbled-circuits-1986 —— GMW 的两方版前驱，同为 MPC 两大理论支柱；乱码电路在两方场景比 GMW 更常用
diffie-hellman-1976 —— 公钥密码学奠基，OT 的构造依赖 DH 类假设
rsa —— RSA 提供了 GMW 中 OT 原语的另一种构造方式
aes —— 布尔电路安全评估的经典基准测试对象（AES 电路约 3.4 万个 AND 门）
zk-snark —— 恶意安全 GMW 需要零知识证明，zkSNARK 是现代高效替代
ot-1989 —— 不经意传输：每个 AND 门的密码原语，GMW 的核心构件
chaum-1981-mix —— 同时代的隐私保护思路：Mix Networks；GMW 和 Chaum Mix 共同构成早期密码学隐私保护两条路线

反向链接

chaum-1981-mix —— Chaum Mix Network — 把匿名通信从理论变成工程
freedman-psi-2004 —— Freedman-Nissim-Pinkas PSI 2004 — 两个人怎么找共同好友而不暴露各自通讯录
rsa —— RSA 公钥密码
yao-garbled-circuits-1986 —— Yao 混淆电路 — 让两人合算函数却互不泄密
zk-snark —— zk-SNARK 零知识证明