GMW协议：安全多方计算经典方案

可视化演示

步进式展示GMW协议核心流程：异或秘密共享拆分输入、布尔电路表示、异或门本地评估、与门遗忘传输评估及多方协议对比，理解隐私计算经典方案。

协议概述：拼图俱乐部的创立

小镇上新开的拼图密室有个奇特规矩：每次挑战，每个人都带来一张记着线索的卡片，想合作算出最终嫌疑人，但谁都不许把自己的卡片给别人看。这听起来像悖论——不交换数据，怎么联合计算？俱乐部的秘密，就藏在安全多方计算（MPC）这门学问中：n个参与方各持私有输入xᵢ，共同计算一个函数f，最后每个人都得到正确输出，但除了自己的输入和最终输出外，学不到任何额外信息。

GMW协议正是这个领域最经典的方案之一，由Goldreich、Micali和Wigderson在1987年提出。它做出了一个震撼性的理论承诺：“任何可高效计算的函数，都能被多方安全地计算。”GMW立足半诚实模型（semi-honest）：所有参与者都会严格遵守协议步骤，但会好奇地从中间消息中推断他人的秘密。这就像俱乐部的实习生们虽然守规矩，眼睛却总忍不住往别人桌上的碎片瞟。

回到俱乐部：实习生们把卡片投入碎纸机时，就已经踏上了GMW的旅程。他们不知道，墙上那张巨大的蓝图才是整场拼图的核心——那就是下一节要讲的布尔电路。

布尔电路：墙上的拼图蓝图

拼图密室墙上挂着一张巨大的蓝图，像乐高说明书一样把最终图案拆解成几百个标准积木块。实习生们不需要理解别人卡片上的内容，只要按照蓝图的指引，把积木一块块拼上去即可。这张蓝图，就是密码学家口中的“布尔电路”。

任何可计算的函数——无论是信用评分、求交集还是统计均值——理论上都能转换为一张由与门（AND）、异或门（XOR）、非门（NOT）构成的布尔电路。输入是比特，输出也是比特。电路的大小由门的总数衡量，深度则由最长路径上的门数决定，这两者直接关系到GMW的计算与通信开销。这种转换并不抽象：硬件编译器可以把高级语言翻译成逻辑门网表，正如蓝图把最终图案分解成积木块。

在GMW中，没人把真实比特直接喂给电路，而是把每个比特拆成“噪点碎片”再送进蓝图。这正是俱乐部的碎纸机——秘密共享机制，我们下一节细看。

秘密共享：碎纸机与噪点负片

拼图密室入口摆着一台神秘的碎纸机。实习生把卡片塞进去，出来的不是纸条，而是几张布满随机噪点的透明负片。每张负片单独看如同雪花屏般毫无意义；但把它们叠在一起对着光，原始卡片的内容便清晰浮现。更妙的是，任何一张负片丢失，都不会泄露原图的半点信息。

这套机制对应密码学中的秘密共享，GMW使用其中最简洁的一种——XOR共享（布尔共享）。设秘密是一个比特s，要分给n个人：随机生成前n-1个份额，最后一个份额取s与所有随机份额的异或，于是所有份额的异或正好还原s。任意少于n份的份额集合，在信息论意义上不泄露s的任何信息。这使得电路求值中的每个中间值都能以份额形式存在，没有任何参与者能看到真实值。

碎片分好后，实习生们各捏着几片噪点进入工坊。接下来，他们要按蓝图把碎片拼起来——有些积木轻轻一扣即合，有些则需要“魔法交换盒”帮忙。

门求值：两种积木的拼法

拼图蓝图上只有两种核心积木：XOR积木和AND积木。实习生们很快发现，XOR积木是“阴阳块”——两块形状完全互补，放在桌上一推就能咬合成一个完整方块，不需要询问任何人。AND积木则麻烦得多：两块积木的接缝处有一根交叉销钉，必须借助柜台上的盲选盒才能插好。

密码学中的对应关系极其精确。设导线a的共享为(a₁,a₂)，导线b的共享为(b₁,b₂)。XOR门的计算利用了异或的同态性质：各方只要把自己手上的两份碎片本地异或，就能得到输出a⊕b的份额，全程零通信。AND门则没有这种好运。把(a₁⊕a₂)和(b₁⊕b₂)相乘并展开后，会出现a₁b₂和a₂b₁两个交叉项——每项都同时涉及双方的秘密份额，任何一方都不能独自完成。GMW的做法是：利用不经意传输（OT）让双方交换交叉项而不泄露各自碎片。

把交叉项比作积木上那根销钉：正因为它连接两块碎片，才必须借用盲选盒。下一节，我们走进柜台，看看这个盲选盒内部到底发生了什么。

不经意传输：柜台上的盲选盒

俱乐部柜台摆着一个带两个抽屉的金属盒，叫“盲选盒”。发送方把两个不同的小物件分别放进左右抽屉，然后转过身去；接收方用自己的钥匙只打开其中一个抽屉，取走里面的物件。发送方全程不知道对方打开了哪一边，而接收方也只知道自己拿走的那件，另一边的东西对他永远是个谜。

这个“盲选盒”就是密码学中的不经意传输（Oblivious Transfer, OT），具体地说是1-out-of-2 OT。在AND门求值中，它精确派上用场：计算交叉项a₁b₂时，P1作为发送方提供(0, a₁)，P2作为接收方用选择位b₂去取。若b₂=0，P2取到0；若b₂=1，P2取到a₁。于是P2得到a₁∧b₂，而P1完全不知道b₂的值。OT协议可以通过RSA、ElGamal等公钥密码构造，它的安全性有两大要点：接收方的选择位对发送方隐藏，而发送方未被选中的消息对接收方隐藏。

有了碎纸机（秘密共享）和盲选盒（OT），再配合蓝图（电路），整个工坊就能完整运转了。实习生们从进门到出门的全程，就是下一节的完整协议流程。

计算流程：从进店到拼完离店

让我们跟拍一位实习生走一趟拼图密室。进门后第一件事，是把线索卡塞进碎纸机——这条“输入阶段”将每个输入比特拆成n份XOR份额，分别发给所有成员。随后大家进入大厅，面对蓝图开始“电路评估阶段”：按拓扑顺序逐门处理，遇到XOR门就本地拼一下，遇到AND门就两两到柜台用盲选盒交换一次。最后是“输出恢复阶段”：所有人将自己最终输出比特的份额亮出来，异或得到明文结果。

三个阶段串起来就是GMW协议的完整骨架。输入阶段的安全性来自秘密共享的信息论隐藏；电路评估阶段由XOR门零泄露和OT的双盲性共同保证；输出阶段因为输出本身就以份额形式存在，公开份额只暴露了协议设计允许暴露的结果。从性能角度看，在线通信轮数直接由电路深度决定——同一深度上相互独立的AND门可以并行调用OT，而总通信量则与AND门总数线性相关。

走出拼图密室时，实习生们手里只剩一堆用过的碎纸片，但每个人都知道了答案。有人小声问：城里另一家“算术工坊”也做类似的事，到底哪家更强？这就引出了GMW与BGW的对比。

协议对比：拼图工坊与算术工坊

小镇的另一头有一家“算术工坊”，招牌上写着BGW协议。它不玩拼图积木，而是用数字卡片做算术：把秘密用Shamir多项式插值拆成数值份额，加法和数乘随时可以本地做，只有乘法门需要一轮交互。拼图俱乐部（GMW）则擅长逻辑判断：它把一切计算都碾成布尔比特，用XOR/AND门逐位加工。

两者的分野恰在电路类型：GMW基于布尔电路，适合比较、选择、位运算等逻辑任务，AND门用OT处理；BGW基于算术电路（域上的加乘），适合求和、求均值、多项式计算等数值任务。秘密共享底层也不同：GMW用XOR共享（模2加法），BGW用Shamir共享（域上算术）。选择哪家取决于任务性质：若要计算“三个数是否都小于阈值”，布尔电路像乐高一样直观；若要计算“几千人工资的平均值”，算术电路能省下大量通信。在同样规模下，GMW的AND门每次都要跑OT，开销通常高于BGW的乘法共享，但GMW在恶意安全扩展上更自然。

两间工坊各有拥趸，但真正让拼图俱乐部名扬四方的，是它能把抽象杂技变成可落地的流水线。最后一节，我们看看工程上如何把这份蓝图搬进真实的隐私计算系统。

工程实践：把拼图工坊搬上流水线

拼图俱乐部门庭若市后，老板决定把手工流程改成生产流水线：引进一台“预处理器”，在营业前批量生产盲选盒；让不同拼图桌同时开工；还定制了一批“标准销钉包”减少AND门的现场操作。这些工程改造正是GMW从理论走向工业界的真实路径。

工程上最关键的性能瓶颈永远是AND门数量，因为每个AND门都意味着一次OT。优化主线有两条：一是减少AND门——把电路改写得更浅更小（如用更优的逻辑综合工具、将比较运算改成算术友好形式）；二是摊薄OT成本——用OT扩展（OT Extension）把少量公钥OT扩展成海量对称密钥OT，离线预处理阶段先算好，在线阶段只需高效的异或和哈希运算。有了这些加速，GMW已落地于隐私求交、联合风控、匿踪查询等场景。现代开源框架如ABY、EMP-toolkit、MP-SPDZ都实现了GMW风格的安全计算，让工程师不必从零手写OT和份额逻辑。

如今，拼图工坊的流水线日夜不停。实习生们依然不知道彼此的卡片内容，但答案总能准时出现在出口的屏幕上。这就是GMW协议跨越三十余年依然活跃的原因——它把“不可能”的安全合作，变成了一张可以量产的拼图蓝图。

AI 应用场景

Python 演示

import os  def xor_share(secret):    """把 0/1 比特拆成两份 XOR 份额"""    s1 = os.urandom(1)[0] & 1    s2 = secret ^ s1    return s1, s2  def ot_send(choice, m0, m1):    """模拟 1-out-of-2 OT：接收方按 choice 取得消息"""    return m0 if choice == 0 else m1  def gmw_and_gate(a1, b1, a2, b2):    """两方 AND 门求值：输入为两侧份额，输出仍为两份 XOR 份额"""    t1 = a1 & b1    t4 = a2 & b2    x1 = ot_send(b2, 0, a1)    x2 = ot_send(b1, 0, a2)    return t1 ^ x2, t4 ^ x1  def main():    a = 1    b = 1    a1, a2 = xor_share(a)    b1, b2 = xor_share(b)    print(f"输入: a={a}, b={b}")    print(f"份额: a1={a1}, a2={a2}, b1={b1}, b2={b2}")    c1, c2 = gmw_and_gate(a1, b1, a2, b2)    result = c1 ^ c2    print(f"输出份额: c1={c1}, c2={c2}")    print(f"AND 结果: {result}")    assert result == (a & b), "GMW AND 门计算出错"    print("正确性验证通过：c1 ^ c2 = a & b")  if __name__ == "__main__":    main()

1. s1 = os.urandom(1)[0] & 1生成均匀随机的比特，作为第一份份额。
2. s2 = secret ^ s1用异或补出第二份份额，保证两份份额合起来能还原秘密。
3. def ot_send(choice, m0, m1):模拟盲选盒OT，接收方只能按选择位取走一条消息。
4. x1 = ot_send(b2, 0, a1)P2 通过OT得到 a1*b2 的交叉项，而 P1 不知道 b2 的取值。
5. x2 = ot_send(b1, 0, a2)P1 通过OT得到 a2*b1 的交叉项，而 P2 不知道 b1 的取值。
6. return t1 ^ x2, t4 ^ x1把本地对角项与交换来的交叉项合并成两方各自的输出份额。
7. assert result == (a & b)验证两份额异或后，恰好等于真实AND门输出。

常见误区

面试题