Yao Garbled Circuits — 两个人不摊牌也能一起算答案

待复核

是什么

Yao 这篇论文解决的是：两个人各有秘密输入，想一起算一个函数，却不想把自己的秘密交出去。日常类比：像两个人各拿半张拼图，只想知道拼出来是不是同一幅画，但不想把自己那半张给对方复印。

最有名的入口叫“百万富翁问题”：Alice 和 Bob 想知道谁更有钱，但谁都不想暴露具体资产。普通做法是找中介，Yao 的问题是：能不能只靠协议本身，做到“该知道的答案知道，不该知道的细节不知道”？

换句话说：中介可以换成一串双方都遵守的消息交换规则。

论文题目说的是“生成和交换秘密”，不是现代乱码电路（garbled circuits）教程。它后来常被放进那条源头脉络，是因为把任意任务看成要算的函数、并说明可在密码学假设下控制知识转移；后来的乱码电路才把想法工程化成“每根线的真假值换成随机标签”。

为什么重要

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

为什么安全两方计算不是“加密后再解密”，而是把计算过程本身变成协议。
为什么隐私计算总说“只泄露输出”，因为输入之外的信息也可能被消息顺序和中间值泄露。
为什么公平性很难：一方先拿到结果后退出，另一方可能什么都得不到。
为什么后来的隐私协议都爱问同一类问题：谁看见了什么、能不能假装成“只知道答案的人”、对方中途耍赖怎么办。

核心要点

把任务写成函数：先别问怎么加密，先问两个人到底要算 f(i, j) 和 g(i, j)。类比：做饭前先写菜单，否则锅碗瓢盆再高级也不知道要端出什么菜。函数定了，才谈得上正确性、隐私和公平。
隐私看的是“视图”：协议不只检查最后答案，还检查每个人沿途看到的消息、随机数和中间结果。类比：考试只公布分数可以，不能把草稿纸也发出去。若外人分不清“真实对话记录”和“只知道答案的人伪造的记录”，隐私才算站住。
公平性是另一条约束：隐私保证你少知道，公平性保证你不能先知道后跑路。类比：交换礼物不能一方先拆完盒子就关门。论文还讨论作弊与恢复：一方偏离流程时，另一方仍要有机会拿到该拿的结果。

实践案例

案例 1：百万富翁问题怎么抽象

Alice 输入 i = 7
Bob   输入 j = 5

目标函数：
f(i, j) = 1  如果 i > j
f(i, j) = 0  如果 i <= j

逐部分解释：

i 和 j 是私有输入，协议开始前只有各自知道。
f(i, j) 是共同想知道的答案，不是两个输入本身。
安全协议的目标不是“让 Bob 永远不知道任何东西”，而是“Bob 只知道 i > j 这个输出能推出的东西”。

案例 2：乱码电路的最小直觉

真实电路：AND(a, b)
线标签：a0/a1，b0/b1，输出 o0/o1
手上只有 a1 和 b0 → 只能解出 o0
外人看见 a1，仍分不清它代表 1 还是随机串

逐步：

换标签：每根线的真假 0/1 先换成随机字符串，外人看不出标签对应哪边。
解门表：门的真值表被打乱并加密；只有手上这对标签能打开其中一格，其他格打不开。
映射输出：解出的输出标签再对照回真实答案。像只给你能开的一串保险箱钥匙。

案例 3：交换秘密为什么难

Alice 有秘密 SA：一个大数的分解
Bob   有秘密 SB：一个图的哈密顿回路

目标：
Bob 得到 SA 当且仅当 Alice 也能得到 SB

逐部分解释：

两个秘密可以完全不同类，不能简单按“字节数相等”交换。
论文关心的是知识转移的节奏：谁在什么时候已经能恢复什么。
公平协议要让“我拿到你的秘密，但你拿不到我的秘密”的概率变得可忽略。

踩过的坑

把 1986 论文等同于现代乱码电路教程：这篇是 extended abstract，重点是一般协议、秘密生成和公平交换，现代门级构造要看后续整理。
以为加密消息就等于隐私：消息被加密仍可能泄露长度、轮次、是否停止等信息，所以论文用视图和不可区分来约束。
忽略公平性：只做到“输入不泄露”还不够，一方可能在知道答案后中断，让另一方无法得到对应结果。
把半诚实实现直接丢进恶意场景：半诚实假设对方照流程走；恶意允许中途 abort。只测“输入不泄露”会漏掉“一方先拿到结果就跑”的公平性坑。

适用 vs 不适用场景

适用：

两方各有私有输入、只想公开 f(i,j)（比较、投票、谈判），先建立问题骨架。
区分“只泄露输出”和“公平交换”：后者通常要更多轮次与恢复逻辑。
读现代 2PC 库（半诚实乱码电路常见千门级秒级；恶意模型开销常高一个数量级）前先对齐目标。

不适用：

要可复制工程代码或具体延迟/带宽数字；这篇是 extended abstract，不是库文档。
要抗量子或具体效率参数；假设背景是大整数分解困难。
只关心通道加密；TLS 防窃听，安全计算防“两端的人互相不全信”。
需要三方以上且要恶意安全的现成部署方案；应转向后续 MPC 工程文献与库。

历史小故事（可跳过）

1982 年：Yao 在 “Protocols for Secure Computations” 里提出百万富翁问题，给安全计算立了一个清晰问题样板。
1986 年：这篇 FOCS 论文把重点推进到秘密生成、秘密交换、隐私和公平性，并把一般两方计算纳入同一框架。
1987 年以后：Goldreich、Micali、Wigderson 等工作把多方安全计算理论继续系统化，形成现代 MPC 语言。
1990–2010 年代：乱码电路从理论走向可实现协议，出现半诚实与恶意模型下的工程优化。
2000 年：Yao 获图灵奖，安全计算只是他贡献版图的一部分，但这条线深刻影响了密码学和隐私计算。

学到什么

安全计算的核心不是藏答案，而是控制知识转移：该输出的输出，不该多知道的别多知道。
函数化是第一步：把业务写成 f(i, j)，才有机会讨论协议是否正确、隐私、是否公平。
公平性比隐私更难工程化：因为它涉及中途退出、恢复、作弊检测，而不是单纯的消息保密。
理论抽象会变成工程接口：今天的 2PC 框架让开发者写电路或程序，背后仍是在回答 Yao 提出的那组问题。

关联

diffie-hellman-1976 —— 提供“一方向函数 / 公钥”这类密码学假设的历史起点。
rsa —— 大整数分解困难是假设背景之一，论文里的秘密示例也常用分解。
cryptoverif-2008 —— 后来的协议验证工具，关心的仍是“协议到底泄露了什么”。
easycrypt-2011 —— 把密码协议证明写成可检查脚本，延续形式化安全证明路线。
zero-knowledge-proofs —— 同样追求“证明一件事但不多泄露”。
secure-multiparty-computation —— Yao 这条线的直接后代：多方一起算、输入仍私有。

反向链接

gmw-mental-game-1987 —— GMW Mental Game — 多个人不交出秘密也能一起算答案
rabin-ot-1981 —— Rabin OT 1981 — 不知道对方是否收到的秘密交换