GMW Mental Game — 多个人不交出秘密也能一起算答案

待复核

是什么

GMW 这篇论文解决的是：多个人各有秘密输入，想共同完成一个游戏或计算，却不想把秘密交给任何可信中介。日常类比：像一桌人打牌，大家都希望牌局按规则推进，但没人愿意让某个“总裁判”同时看见所有人的手牌。

论文把问题抽成 Turing-machine game：第 i 个玩家有私有输入 x_i，大家想算出 y = M(x_1, ..., x_n)。协议的目标不是“什么都不泄露”，而是只泄露输出 y 本来就会透露的信息。

它最强的结论是：只要存在 trap-door function，并且诚实玩家超过一半，就可以把任意这类游戏变成一个多方协议来执行。换句话说，可信第三方能做的事，协议也能模拟。

为什么重要

不理解 GMW，下面这些事都很难解释：

为什么现代 MPC 总说“只泄露输出”，因为协议安全看的是每个参与方沿途看到的全部视图。
为什么“诚实多数”是一个分水岭：超过一半诚实，协议能恢复偏离者的输入和随机性；不超过一半，某些任务根本做不到。
为什么 oblivious transfer、secret sharing、zero-knowledge 会在同一篇论文里出现：它们分别解决选择、分摊和防作弊。
为什么隐私计算不是一个个手写特例，而可以有“任意函数都能安全计算”的通用性定理。

核心要点

先定义理想世界：如果有可信第三方，大家把输入交给它，它算出答案再公开。类比：所有人把信封交给公证员，公证员只念最终结果。
再模拟这个公证员：GMW 把计算拆成电路或小步骤，让每个玩家只持有随机碎片。类比：每个人拿一块拼图，单独一块看不出图案，合起来才还原答案。
最后约束作弊者：恶意玩家必须用零知识证明说明“我这条消息确实按规则生成”。类比：你不必公开手牌，但每次出牌都要证明自己没有偷换牌。

三步合起来就是“通用安全多方计算”：不是为投票、扑克、签合同各写一个协议，而是给任意可计算任务一个编译器式方案。

实践案例

案例 1：工资总和不暴露个人工资

玩家输入：
Alice: 30
Bob:   40
Carol: 50

目标函数：
M(x1, x2, x3) = x1 + x2 + x3

公开输出：
120

逐部分解释：

输出 120 本身会透露“其他人总共 90 / 80 / 70”，这是结果不可避免的泄露。
协议要阻止的是额外泄露，比如 Bob 不能从消息记录反推出 Alice 的具体工资。
这就是论文里 privacy constraint 的直觉：额外消息不能比“自己的输入 + 最终输出”多给有效信息。

案例 2：一选二 OT 像只开一个抽屉

Alice 有两个比特：
b0 = 0
b1 = 1

Bob 选择：
alpha = 1

协议保证：
Bob 只学到 b1
Alice 不知道 Bob 选的是 0 还是 1

逐部分解释：

OT 是 GMW 构造里的小齿轮：它让一方“只拿到自己选择的那份信息”。
Alice 不能看出 Bob 的选择，因为 Bob 发来的两个值在分布上看起来一样。
Bob 不能拿到两份，因为另一份被一个他无法预测的随机位遮住。

案例 3：恶意玩家被变回“只能半诚实”

每一轮消息：
msg_i = Next(program_i, input_i, random_i, history)

额外要求：
player_i 给出零知识证明：
“我知道 input_i 和 random_i，
并且 msg_i 正是按 Next 算出来的。”

逐部分解释：

零知识证明让别人相信消息合规，但不看见输入和随机数。
如果玩家中途退出，诚实多数可以用事先的 secret sharing 重构它的输入和随机性。
所以恶意玩家要么按程序发消息，要么被大家接管，最终像半诚实玩家一样不能破坏协议。

踩过的坑

把 GMW 当成高效工程协议：论文给的是通用性和可行性证明，不是今天可直接部署的最快 MPC 实现。
以为“诚实多数”表示大多数人不会偷看：它是严格的故障阈值，恶意人数必须小于 n/2，否则有些任务无法同时保证正确和隐私。
忽略输出本身的泄露：如果函数输出是“谁工资最高”，那这个事实必然被公开；协议只能防额外泄露。
混淆 passive 和 malicious：passive 会照流程跑但偷看信息，malicious 可以乱发消息；后者需要承诺、秘密分享和零知识证明一起处理。

适用 vs 不适用场景

适用：

多方各有私密输入，只想公开某个函数结果，比如投票、竞价、联合统计。
理解 MPC 为什么可以从“几个特例”上升到“任意函数”。
解释诚实多数、秘密分享、零知识证明之间的协作关系。

不适用：

需要低延迟生产系统的实现细节；这篇主要是理论 extended abstract。
没有诚实多数或没有合适密码学假设的场景；论文的主定理依赖这些条件。
侧信道、实现 bug、用户输入造假等工程问题；协议模型不会自动覆盖现实所有漏洞。

历史小故事（可跳过）

1982 年：Yao 提出安全计算的经典问题，把“各有秘密还要一起算”变成清晰研究对象。
1985 年：verifiable secret sharing、coin flipping、probabilistic encryption 等工具逐渐成形。
1986 年：GMW 另一条线证明 NP 语言有零知识证明，给“证明消息合规”提供核心工具。
1987 年：这篇 STOC 论文把这些工具拼成通用 MPC 定理，说明任意协议问题都能自动求解。
1988 年以后：Ben-Or 与 Wigderson、Goldreich 与 Vainish 等后续工作继续改进效率和假设。

学到什么

可信第三方是一种规格，不一定要真实存在：先写清理想世界，再用协议模拟它。
隐私要按“视图”来定义：每条消息、随机数和中间状态都可能泄露信息，不能只看最终答案。
通用性来自组合：OT 处理选择，secret sharing 处理分摊，zero-knowledge 处理作弊，组合后才能覆盖任意函数。
不可能性也很重要：诚实多数不是随口假设，而是这类通用协议能成立的关键边界。

关联

yao-garbled-circuits-1986 —— GMW 把 Yao 风格安全计算推进到多方与诚实多数。
byzantine-generals-1982 —— 都在处理“有人可能撒谎时，系统还能不能按规则前进”。
pbft-1999 —— 工程系统里的拜占庭容错，和 GMW 的恶意参与者模型共享问题意识。
cryptoverif-2008 —— 后来的工具把这类“计算不可区分”证明机械化。
zk-snark —— 零知识证明是限制恶意玩家乱发消息的重要后代技术。
secure-multiparty-computation —— 合理预测会存在；GMW 是现代 MPC 的基础节点。

反向链接

（暂无反向链接）

GMW Mental Game — 多个人不交出秘密也能一起算答案

是什么

为什么重要

核心要点

实践案例

案例 1：工资总和不暴露个人工资

案例 2：一选二 OT 像只开一个抽屉

案例 3：恶意玩家被变回“只能半诚实”

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接