4.1 GMW 协议：XOR 免费 AND 靠 OT
4.1 GMW 协议：异或免费，AND 靠 OT
本节摘要：GMW 把计算拆到比特级：所有值以异或份额存在，异或门各方本地搞定，与门用一轮 OT 完成交叉项清除。它天生支持两方以上、常数轮，是"布尔电路 + 多方"的第一条务实路线。
定位：本节解决什么
第 3 章的混淆电路有个隐含假设：电路由一方生成、一方求值——两方戏台。真实场景常常是三家以上机构联合计算。GMW（Goldreich-Micali-Wigderson，1987）给出多方布尔计算的经典答案：不做整电路的加密，而是回到第 2 章的秘密分享思路，把每个比特拆成异或份额，逐门本地或小交互地推进。它承接 2.1 节的"线性免费"哲学，把免费范围从加法推广到异或，再把最贵的与门用 OT（2.4 节）补上。
核心原理：两方版先吃透
异或份额的拆法：比特 x，生成随机比特 r，两方各持 r 与 x 异或 r。重组即两片再异或。异或门的免费来自线性：要算 z = x 异或 y，双方各自本地把自己两片异或（r 异或 s 与 r' 异或 s'），重组即得 z——零交互、零加密，与混淆电路的 Free-XOR 在精神上同源。
与门才是考验。z = x 与 y 展开后：z = (r1 异或 r2) 与 (s1 异或 s2) = (r1 与 s1) 异或 (r1 与 s2) 异或 (r2 与 s1) 异或 (r2 与 s2)。各自"本地那项"自己能算，两片交叉项 r1 与 s2、r2 与 s1 卡在双方之间——这正是 2.3 节 Beaver 三元组遇到的同一堵墙，只是世界从加法换成了异或。GMW 的解法恰好用上 2.4 节的 OT：要算 r1 与 s2，甲知道 r1、乙知道 s2，双方跑一次 1-out-of-2 OT——乙作为发送方提供 (0 与 s2, 1 与 s2) 两条消息，甲按 r1 作为选择比特取走对应那条。结果：甲拿到 r1 与 s2 的值（对甲可见），乙什么也没学到（选择保密），甲再把结果转成份额与乙分享。每个交叉项一次 OT，一扇与门两次 OT。
图：GMW 与门的 OT 交互与三方扩展
动手演练
import os def share_bit(x): r = os.urandom(1)[0] & 1 return r, x ^ r # 两片异或份额 x1, x2 = share_bit(1) # 比特 x = 1 y1, y2 = share_bit(0) # 比特 y = 0 # 与门本地项 local_a = x1 & y1 local_b = x2 & y2 # 模拟 OT：甲拿 r1 换 r1 与 s2，乙拿 s1 换 s1 与 r2 cross_1 = x1 & y2 # OT 后甲可见 cross_2 = x2 & y1 # OT 后乙可见 z1 = local_a ^ cross_1 ^ (cross_2 & 0) # 份额切分：可见项再随机分片 z2 = local_b ^ (cross_2 & 1) ^ cross_2 # 演示用简化分片 print((x1 ^ x2) & (y1 ^ y2)) # 明文与门：1 与 0 = 0
示例意在展示"四项凑齐"的结构；生产实现里交叉项可见方必须先把可见结果重新随机分享再交给对方，代码里用简化占位，完整分片逻辑见任何标准教材的 GMW 伪代码。
工程实践要点
GMW vs 混淆电路怎么选？ 同样是布尔电路，GMW 在线交互多（每扇与门两轮 OT）、通信省（不带门表）；GC 在线轮数少（一两轮）、通信大（门表全量传输）。局域网带宽富裕延迟低，GMW 的多轮交互不疼，通常更快；广域网高延迟下 GC 的少轮数占优。与门密度是另一个变量：与门越密集，GMW 的 OT 越多、GC 的表越大，两边同比变差，但 GC 的 32 字节单价往往仍低于两次 OT 的通信量。恶意安全上，GMW 升恶意要给 OT 与份额加校验，工程上更多人直接选 SPDZ 系（第 5 章）。
💡 关键直觉：GMW 与 Beaver 三元组是同一堵墙的两种翻墙姿势——墙叫"交叉项"，GMW 用 OT 逐项购买，Beaver 用预制的乘法关系整体代偿。看穿这一点，第 5 章的 SPDZ 会显得非常亲切。
本节要点：异或份额让异或门免费；与门交叉项用成对 OT 购买；多方扩展靠成对组合、交互随参与方数平方增长。下一节看另一条多方化路线：让所有人一起当电路生成者。
份额重随机化：GMW 最容易写错的一步
与门的四个与项凑齐后，还不能直接把它们当份额用——因为其中有的项对某一方是明文可见的（比如甲算出了 r1 与 s1）。把可见值直接当份额等于把半份明文交了出去。正确动作是重随机化：可见项的持有方先给结果加一片新随机数再分享出去，让各方最终持有的份额重新回到"均匀随机"状态。这一步在教材伪代码里常被一笔带过，在实现里却是安全的关键闸门——2.4 节 OT 演示代码里的简化占位，在这里必须补全。
轮数账再算细一点：与门需要 OT 一轮加重组一轮，深度为 d 的电路总轮数约 2d。这个数字对局域网友好（每轮亚毫秒），对广域网不友好（每轮几十毫秒起）。所以 GMW 的部署画像非常清晰：机房内或同城低延迟网络、布尔逻辑为主、批量处理——命中这三条的联合规则引擎、名单比对，GMW 至今仍是竞争力极强的选择。
GMW 的现代回声
GMW 论文发表于 1987 年，比混淆电路的工程化还早，但它的两个设计决定至今在回响。决定一：把最贵的操作换成 OT。 当年 OT 是纯理论原语，OT 扩展（2.4 节）发明后，"与门靠 OT"从性能劣势变成性能优势——今天基于 OT 的协议家族（IKNP 系、Silent OT 系）是两方计算性能榜的常青树，GMW 的路线判断被技术进步反向证明。这个故事的启示值得记住：协议设计的远见经常跑赢硬件演进，押注"更便宜的原语"而不是"当前最快的路径"。
决定二：逐门本地化。 每扇门只依赖输入线的份额，门与门之间没有隐藏状态——这个性质让 GMW 天然适配并行与流水：不同层的门可以并行算，同一层的门可以打包发。现代框架把"层"做成调度单位，本质上都是在吃 GMW 这口结构红利。
对工程师的实操提示落在调试上：GMW 的中间值全是份额，出了错既看不出哪扇门错、也看不出哪方错——成熟的调试方法是在测试环境对固定输入做"明文影子计算"，逐门对比份额重组值与明文值。这套影子调试法在后续所有分享类协议里通用，值得现在就写进你的调试工具箱。
一道多方扩展的推演题
两方 GMW 吃透后，用一道推演题检验迁移到三方的理解。三方异或分享下算一扇与门：乘积展开后交叉项变成 r1 与 s2、r1 与 s3、r2 与 s1、r2 与 s3、r3 与 s1、r3 与 s2 共六项——两方时是两项。六项按"知道哪两个因子"两两配对跑 OT，每项一次、共六次，各方拿到可见项后重随机化分享。推演到这里，再回答两个小问：n 方时交叉项是几项（n 乘 n 减 1 项）；为什么交互对数增长是平方级的（成对组合）。能推到底，GMW 的多方扩展就不再是背诵知识，而是你自己能推导的结构——这种"推得出"的感觉，正是布尔路线与算术路线之间最可靠的桥梁。