姚期智

破除误解：算力无限之后，困难并不消失#

通信复杂度最容易被听成网络协议课。姚期智抽象掉延迟、丢包与带宽，只保留「信息必须跨过某条缝」。正因为如此彻底，它才能给别的模型做下界：若某函数即使在算力无限时也必须传送 $n$ 比特，那么任何真实系统都逃不掉这条界——它不依赖 P 对 NP，也不依赖单向函数。

第二个误解是把姚氏原理当成一句口号「随机等于平均」。精确陈述来自冯·诺依曼的极小极大定理。把算法设计者与输入选择者写成零和博弈：一方选随机算法，一方选输入。均衡处，随机算法在最坏输入上的期望代价，等于确定性算法在最坏输入分布上的期望代价。因而要证明随机下界，只需展示一个分布，让一切确定性算法都贵。随机性被消掉，不是因为随机无用，而是因为最坏分布已经把随机能够帮忙的那部分吃进期望里。

第三个误解是把混淆电路当成「把电路画乱」。乱是实现细节；机制是加密的真值表。每条导线准备两把密钥，每个门的四种输入组合被加密成四条密文并打乱顺序。求值者只持有自己输入对应的密钥，每个门只能解开正好一行，从而得到输出导线的密钥。他沿电路走完，只学习输出，不学习中间导线的明文比特。

现场：极小极大如何变成随机下界#

姚期智 1977 年 FOCS 论文《概率计算：朝向复杂性的统一度量》把上述博弈写进算法领域。设代价 $C(A,x)$。随机算法 $A$ 的最坏期望是 $\max_x \mathbb{E}[C(A,x)]$。输入分布 $D$ 上确定性算法的期望是 $\mathbb{E}_{x\sim D}[C(A_{\mathrm{det}},x)]$。极小极大给出

$$\min_{A\ \mathrm{randomized}}\ \max_x\ \mathbb{E}[C(A,x)] = \max_{D}\ \min_{A_{\mathrm{det}}}\ \mathbb{E}_{x\sim D}[C(A_{\mathrm{det}},x)].$$

左边是我们想下界的对象（随机算法的最坏期望），右边是往往更好下手的对象（找一个毒分布）。通信复杂度里这条原理几乎是默认手法：要证明随机协议需要 $\Omega(n)$ 比特，就设计一个输入分布，证明任何确定性协议的期望通信仍是 $\Omega(n)$。集合不相交（DISJ）的 $\Omega(n)$ 随机下界（拉兹博罗夫）是这一方法的高峰之一，见 通信复杂度。

把同一原理送回 计算复杂性，它成为随机算法分析的标准杠杆：有时你并不分析硬币，你分析最坏输入的分布。决策树、电路大小、流空间，都可以写成这类博弈。姚期智的贡献不是发明极小极大——那是冯·诺依曼的——而是指出：复杂性下界可以当作博弈值来取。算法博弈论 后来把均衡的可计算性变成主题；姚氏原理是更早的、方向相反的一击：用博弈论给算法的随机性定价。

通信复杂度的等式函数 $\mathrm{EQ}$ 把反差写得很干净。确定性协议必须传送 $n$ 比特（矩形覆盖论证）；允许错误的随机协议用多项式指纹只需 $O(\log n)$ 比特。随机性在这里指数级地有用。不相交则相反：随机性几乎省不下渐近通信。姚期智给出模型；何种函数对随机性敏感，成为此后四十年的分类学。

百万富翁与混淆电路：把函数藏在门里#

1982 年 FOCS 论文《安全计算的协议》提出百万富翁问题。爱丽丝有整数 $i$，鲍勃有 $j$，双方要知道是否 $i>j$，且不泄漏 $i$ 与 $j$ 本身。姚期智用公钥加密构造比较：把数值编码进一组密文，让对方只能解开与比较结果相关的那一层。细节随后被更干净的不经意传输（OT）语言重写，但问题本身成为安全两方计算的种子——目标不是保密信道，而是计算一个约定函数且只泄漏输出。

1986 年 FOCS《如何生成并交换秘密》给出混淆电路。对任意布尔电路 $C$，一方（混淆者）为每条导线 $w$ 抽样两把密钥 $k_w^0,k_w^1$。对每个门 $g(u,v)=w$，生成四条密文

$$\mathrm{Enc}_{k_u^a,k_v^b}(k_w^{g(a,b)}) \quad (a,b\in\{0,1\}),$$

随机排列后交给求值者。求值者通过 OT 取得自己输入比特对应的密钥，再逐门解密恰好一行。输出门的密钥被译回明文比特。半诚实模型下，视角可被模拟：求值者看见的每条密文与随机串不可区分，除了他能解开的那一行。

这套构造把「任意多项式时间函数的安全两方计算」从一串特设协议，收成「先把函数编译成电路，再对电路做一次混淆」。戈德赖希–米卡利–维格德森的 GMW 协议走另一条路：用零知识证明强制各方遵守电路的门，适用于恶意模型的经典路径。姚期智的路线在半诚实两方、布尔电路上更直接，也因此成为后来自由异或、半门、剪枝等工程优化的底板。密码学基础 里的安全定义——半诚实、恶意、模拟——是阅读 1986 年论文时必须自行补上的现代译文；原文更短，更像存在性论证。

不经意传输是混淆电路真正的密码学接口。求值者必须取得自己输入比特对应的密钥，且不能知道另一把，混淆者也不能知道求值者选了哪一把。没有 OT，混淆者若直接把两把输入密钥都交给对方，对方就能解开真值表的多行，从而学习不该学习的中间值。姚期智 1986 年的论文把这一接口当成给定；后续实现的常数优化，很多是在 OT 扩展与门加密上省密文，而不是改写模拟定义。把「混淆电路很慢」只归咎于四个条目的真值表，会漏掉 OT 才是每条输入导线都必须付一次的固定成本。自由异或把线性门的四条密文减到几乎为零，半门把与门的密文减半，这些工程论文的对照物始终是 1986 年的那张表。

姚氏 XOR 引理（常引自1982 年关于陷门函数的讲稿与论文）则属于硬度放大：若布尔函数 $f$ 只是「略难」（任意高效算法优势只比 $1/2$ 大一点），则足够多份独立输入上 $f$ 值的异或会变得「非常难」。这把轻微的平均情况硬度推进到适合伪随机发生器的强硬度，是后续 Nisan–Wigderson 式去随机化的前置引理之一。通信复杂度、混淆电路、XOR 引理，三条线看起来分属三个子领域，共用的是同一种翻译习惯：把计算对象改写成游戏或电路，再对资源做无条件或基于假设的定价。

清华姚班，以及把理论做成可教的制度#

姚期智在哈佛取得物理博士，转攻计算机科学，先后任教于 MIT、斯坦福、伯克利、普林斯顿。2000 年图灵奖的引文并列三件事：基于复杂性的伪随机、密码学、通信复杂度。2004 年他全职回到清华大学，创办理论计算机科学研究所（ITCS）；2005 年「计算机科学实验班」（姚班）招生。课程以理论为主干，强调数学与证明，目标是把图灵奖层级的问题意识前移到本科。

姚班成为中国计算机科学教育的一个符号：高选拔、重理论、毕业生大量进入海外与国内研究机构。支持者视之为把「可证明」的品味制度化；批评者指出精英小班无法自动改写整体教育结构，也可能把理论兴趣过度绑定在竞赛式选拔上。这些争论属于教育政策，不是对 1977–1986 年定理的否证。把姚期智写成「回国办学的名人」或写成「只证明下界的隐士」，都会切掉另一半。

代价与争议#

模型与实现。 混淆电路在半诚实两方上优雅，一旦进入恶意模型、多方可串通、电路极大或需要持续计算，代价陡增。OT 的轮次、密钥长度、每个门四条密文，曾让「任意函数可安全计算」停留在渐近存在性。2000 年代之后的工程优化改变了常数，没有改变定理：安全性仍相对明确的对手类与泄露函数。宣称「姚氏电路已经解决隐私计算」与宣称「它只是玩具」，都忽略了模型边界。

优先权。 安全多方计算是一条多人故事：Rabin 的 OT、Yao 的两方电路、GMW 的多方与恶意、后来的不经意 RAM 与同态加密。教材若只留「姚氏百万富翁」，会把 OT 与模拟定义从画面里擦掉。姚期智自己的论文是存在性与模型，不是产品白皮书。

下界的社会解释。 通信复杂度的 $\Omega(n)$ 界有时被通俗读成「合作必须全盘交出数据」。定理说的是特定函数在特定划分下的比特下界，不是禁止一切压缩、抽样与近似。近似版本、随机版本、多路版本会给出完全不同的数字。把下界当成政策结论，是类别错误。

提出最小通信，等于提出一种新的下界工厂。过去要证明某问题需要很多时间，你得限制计算模型；现在可以构造一个通信问题，证明任何协议都得说很多话，再把原问题归约到这个协议。流算法把数据流切开、电路深度把导线看成通道、数据结构把查询者与数据库切开。都是在重复 1979 年的那一下：先找边界，再数跨越边界的比特。无穷算力是故意的。它保证测到的困难纯粹来自输入被切开。若即便如此仍必须传送线性比特，这个下界对任何真实机器都成立。

百万富翁是混淆电路的最小标本。比较大小等价于一个极浅的电路，但电路一旦被混淆，双方不必交换财产的二进制展开，只要交换标签与一张加密表。输出是一比特的比较结果，中间导线的标签看起来像随机串。姚期智没有把这个标本写成社交游戏：他要的是任意函数都能如此编译的存在性。后来的专用比较协议可以更快，却不能替代那句话。函数先被当成电路，电路再被当成双方都不该阅读的对象。问题选择再次先于优化。

伪随机那一条与通信复杂度同源。若电路无法区分真随机与某类生成器的输出，生成器就可以在证明里把随机硬币换成短种子。姚期智把「看起来随机」写成计算不可区分，于是随机性不再是物理噪声的配额，而是一种相对电路族的资源。图灵奖把伪随机、密码学与通信复杂度放进同一句颁奖词，不是把人物合并，而是承认 1970 年代末到 1980 年代的理论计算机科学，正在集体改写什么东西算数。

跨域连接#

• 纳什均衡：姚氏原理就是零和博弈的均衡值。算法与输入是对立双方，混合策略一边是随机算法，一边是输入分布。均衡存在保证两种复杂性度量重合；因此随机下界可以改写成分布上的确定性下界。后来的算法博弈论问均衡好不好算；姚期智问的是如何用均衡给算法的硬币定价——同一套极小极大，箭头相反。
• 概率：通信复杂度里随机协议的错误必须对最坏输入成立，硬币是双方共享或私有的资源，不是数据上的平均。姚氏原理把这组硬币消进对分布的期望。XOR 引理则把独立重复的轻弱优势指数压低。三条陈述都要求对概率空间的量词顺序保持清醒：先全称输入，再期望硬币，不能对调。
• 信息不对称：百万富翁问题把「谁更富」从必须公开账本的比较，改成只泄漏一位比较比特。混淆电路把不对称写进密钥：各方只持有自己输入的密钥，中间导线的明文对求值者仍是不对称的。安全计算的产品承诺若写成「数据不出域」，必须补上一句：不出域不等于函数的全部中间值都不可学——泄露由协议的模拟定义划定。
• 组合学：确定性通信下界的主工具是单色矩形覆盖与组合维。函数的通信矩阵被切成组合矩形，每一次说话对应一次划分。姚期智把计算问题译成矩阵，组合学者的覆盖数就变成复杂性。不相交、内积、间隙汉明，后续下界几乎都在这张矩阵上做组合或多项式方法。
• 图论：电路是有向无环图；混淆沿着拓扑序给每个顶点（门）挂四条密文。通信复杂度的协议树也是图：每条边是一次消息，叶子是输出。两种图把「局部检查」变成可计价的对象——门的局部真值表、协议的局部分支——于是全局函数的代价可以从局部结构累加或用割来下界。

人物小记：把边界当成第一等资源#

姚期智的工作几乎都在问同一类问题：信息或随机性跨过某条边界时，必须付多少。磁带上的步数、电路里的门、信道上的比特、协议里的密钥，在他手里可以互相翻译。图灵奖引文看起来像三个方向，读论文则像一个习惯。

姚期智在量子计算上也留下早期界碑。1980 年代末期到 1990 年代，他把通信复杂度推到量子消息：双方可以交换量子比特，下界手法改成矩阵的迹范数与割范数。若干函数在量子通信下仍需 $\Omega(\sqrt{n})$ 或更高，说明「量子」不是一张免费的减比特券。伪随机性方面，他强调发生器的安全必须相对多项式观察者，而不是相对统计距离的绝对不可区分——这与语义安全的认识论是同一退让：从信息论式的静默，退到复杂性式的不可区分。图灵奖把伪随机、密码学、通信复杂度并列，不是三份履历的拼盘，是同一次退让在三个对象上的实例。

清华年代把这个习惯变成课程表。能够制度化的是品味——先写模型，再写下界或模拟；不能制度化的是具体定理的下一块。通信复杂度仍在产生新下界，混淆电路仍在被工程改写常数，姚班的学生会不会继续问「这条缝值多少比特」，才是比奖项更长的那条线。他提问的方式是，先假定你已经无限聪明，再看你仍然必须付出什么。付出的若是比特，那就是通信复杂度；付出的若是可见的中间值，那就是安全计算；付出的若是对最坏分布的期望，那就是姚氏引理。

参考文献#

• Yao, A. C. Probabilistic Computations: Toward a Unified Measure of Complexity. FOCS, 1977.（姚氏原理）
• Yao, A. C. Some Complexity Questions Related to Distributive Computing. STOC, 1979.（通信复杂度）
• Yao, A. C. Protocols for Secure Computations. FOCS, 1982.（百万富翁问题）
• Yao, A. C. How to Generate and Exchange Secrets. FOCS, 1986.（混淆电路）
• Yao, A. C. Theory and Applications of Trapdoor Functions. FOCS, 1982.（含硬度放大与 XOR 引理的经典出处）
• Razborov, A. A. On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 1992.
• Yao, A. C. Turing Award Lecture. ACM A.M. Turing Award, 2000.
• Goldreich, O., Micali, S. & Wigderson, A. How to Play any Mental Game. STOC, 1987.（GMW，多方与恶意模型的对照路线）

延伸阅读#

• Kushilevitz, E. & Nisan, N. Communication Complexity. Cambridge University Press, 1997.
• Evans, D., Kolesnikov, V. & Rosulek, M. A Pragmatic Introduction to Secure Multi-Party Computation. NOW Publishers, 2018.