Yao 1982：陷门函数怎样把单向置换的硬度放大成假硬币

破除误解：异或引理不是后年综述，陷门也不是已经造好的公钥#

第一种最快的读法是：把姚期智听成 1979 年的通信复杂度，或听成同一届 FOCS 上那五页安全计算。1979 年问的是两人各握一半输入时必须说多少话，算力被假定无限。1982 年这十二页问的是多项式时间观察者还看得见多少信息，算力被当成对手的预算。百万富翁协议计量的是比较大小时泄漏哪些比特，封面是安全求值，不是陷门与发生器。把三份印刷收成一句「姚期智 1982」，会把通信、安全电路与计算伪随机焊成一次页码。

第二层误解把课堂「姚氏异或引理」听成戈德赖希、尼桑与维格德森后来的讲义，或听成必须等到列文 1987 年那篇《Combinatorica》才算有对象。课堂把名字钉在这份 FOCS 文本上：弱不可预测的布尔谓词，把若干独立实例的值异或起来，优势会指数下降，直到几乎只剩一次公平抛硬币。列文随后写出第一份完整印刷证明；后年综述把几种证明并排，并提醒读者：印刷正文对引理的展开不如口头报告完整。那些是把钉子写清楚的邻居，不是把封面改挂到另一卷。本页不把异或手续写成把多个实例焊进协议的步骤。

第三层误解把这里的发生器听成布卢姆–米卡利 1984 年那条离散对数密钥流，或听成 1994 年、1997 年那种「足够快、允许自己跑到种子的指数」的去随机发生器。布卢姆–米卡利与姚期智同年宣读、期刊晚两年：前者给出具体数论函数上的下一比特不可预测；本页把下一比特测试与多项式时间不可区分写成等价，并把发生器的燃料写成任意单向置换。尼桑–维格德森把假设降到指数时间里对小电路难近似；因帕利亚佐–维格德森再把最坏情形指数电路下界送进 $P=\mathrm{BPP}$，并为此去随机本页的异或引理。把四份封面收成一句「硬度换随机性」，会把密码学发生器与复杂度类内部的模拟叠成一次印刷。

第四层误解把陷门听成已经部署的公钥方案，或把单向置换的唯一原像听成 Unique SAT。陷门是一句话：正方向容易，反方向对没有那串额外信息的人困难，对握有那串信息的人又容易。这句话是存在性定义，不是一份把模数、指数或填充写成实现的装配说明。置换的原像唯一，是函数为双射时的代数事实；Unique SAT 问的是布尔公式是否恰好一个满足赋值，瓦利安特–瓦齐拉尼用随机隔离证明「零个或一个」在随机归约下仍与 SAT 一样硬。两句都说到「唯一」，窗口不同。本页没有、也不声称已经裁决 $P$ 对 $NP$，或已经造出可部署的陷门。

陷门、异或放大，以及单向置换上的发生器#

装置从「什么样的信息算数」开始，而不是从一张密码表开始。香农 1949 年的保密理论把互信息为零写成完美安全：看见密文，关于明文的不确定性丝毫不减。多项式时间的观察者没有这种全能。两串比特在统计距离上可以相距很远——短种子拉长之后，发生器的输出只撑起一块极小的支撑集——可是任何多项式规模的测试电路，把真随机串与这块支撑集当成输入时，接受概率之差仍然可以小到可忽略。姚期智把这种关系称作计算不可区分。它不是把香农作废，而是标明：一旦对手的算力被写成多项式，统计上的远并不自动等于「看得见」。反过来，不可区分也不等于已经证明两分布相同。

下一比特测试是同一句话的另一面。发生器从短种子写出一长串；若存在某个位置，多项式时间的预测器看见前面那些比特之后，对下一位的猜测显著好于二分之一，则整串就还不是假硬币。混合论证把「整段可区分」翻译成「某一比特可预测」：从真随机一比特一比特地换成发生器的输出，若两端可分，则相邻两步里必有一步可分，那一步就是一个下一比特预测器。于是，通过所有下一比特测试，与通过所有多项式时间统计测试，在这份框架里是等价的。被证明的是翻译手续存在。它不指出该去预测哪一个具体方案的哪一位，也不给出可部署的预测器。

陷门函数把「正算容易、反算难」再加一把合法的后门。一族函数带着公开的索引：给定索引，正向求值是多项式时间；没有陷门时，反演对随机实例仍然困难；握有陷门时，反演重新变得容易。公钥故事需要的正是这种不对称：任何人都能把明文推进去，只有持有陷门的人能退回来。单向函数没有这把后门，它只要求反演困难；单向置换再要求函数是双射，于是每个像都恰好对应一个原像。发生器这一支其实吃的是单向置换，并不调用陷门：迭代正向求值，把某一个对原像略微不可预测的谓词吐成输出比特。陷门留在密码学那一支，用来说明公开运算与私藏反演可以并存。本页证明这种对象一旦存在，就会同时喂饱假硬币与公钥式的不对称。它不把索引生成、陷门保管或迭代轮数写成实现清单。

异或放大处理的是「略微难还不够」。一个布尔谓词若对所有多项式规模电路都只比乱猜好上一个不可忽略的缝，课堂并不把它叫做硬核。把 $k$ 个独立实例上的值异或成一比特，那条缝会按 $k$ 指数变窄，直到预测优势掉到几乎 $2^{-k}$ 这一档；电路规模会付一点多项式税，因为归约要把对异或的预测送回对单实例的预测。燃料是独立样本，不是一份把多个明文异或进协议的配方。定量形状后来由列文的印刷证明写清楚，因帕利亚佐 1995 年的硬核分布与 1997 年那篇去随机异或，再把「必须真独立」这条硬币账单逐步拆掉。本页作为课堂对象，钉住的是放大方向：弱不可预测可以变成强不可预测。戈德赖希与列文 1989 年才给出对任意单向函数都成立的内积硬核；那是后年的邻居，不是把 1982 年的异或再印一遍。

发生器把放大过的谓词拉成一长串假硬币。种子是置换的一个输入；正向迭代给出一串像，每一拍输出那一比特硬核，观察者看见的是像而不是原像。下一比特若仍可预测，异或引理就把这份优势送回「单次反演并不那么难」，与单向假设矛盾。于是假硬币在多项式测试者面前站住。抽象复杂性读法写在同一部分：若这样的发生器存在，有界错误的随机多项式时间就可以靠枚举短种子做多数票，模拟时间变成种子长度的指数。种子若能短到输入长度的某个正次幂，模拟就是亚指数——后来尼桑与维格德森写明，姚期智从单向置换推出过这一档，假设却强到 $\mathrm{NP}\cap\mathrm{coNP}$ 上的难近似，因为双射的反演既可验证「这就是原像」，也可验证「没有别的原像」。本页给出的是条件句，不是已经完成的去随机化，更不是把种子表交给求解器之前的预处理。香农互信息在这里不够用：短种子的输出与真随机在信息论上差得很远，计算上却可以分不开。把「分不开」听成「统计相同」，会把一次复杂性陈述收成一次概率恒等式。

它证明了什么，没有覆盖什么#

它证明了：可行计算面前的信息，可以用不可区分与下一比特不可预测来计量，并且两句话在多项式测试者那里等价。它把陷门函数写成一种可同时服务密码学与伪随机的对象：公开的正向、私藏的反向、以及没有陷门时的平均情形困难。它给出课堂所称的异或引理作为硬度放大：独立实例上的异或把弱优势压成强不可预测。它还证明：若单向置换存在，则存在自身落在多项式时间里的发生器，从而有界错误随机多项式时间可被亚指数确定性手续模拟。用后来课堂的话说，这就是密码学假设上的硬度—随机性权衡，比 1994 年那条「指数时间里有难近似函数」更强，也更早。

它没有证明单向函数存在，也没有证明陷门函数存在。十二页是条件句：若这种对象在那儿，假硬币与不对称就会跟着在那儿。它没有给出布卢姆–米卡利那种钉在离散对数上的具体发生器，也没有给出戈德赖希–列文那种对任意单向函数都成立的内积硬核。它没有把 $\mathrm{BPP}$ 无条件送进 $P$，也没有给出阿德尔曼那种不依赖硬度假设的 $\mathrm{BPP}\subseteq\mathrm{P/poly}$。它没有覆盖尼桑–维格德森的快速发生器与组合设计，没有覆盖因帕利亚佐–维格德森把最坏情形指数电路下界放大成 $P=\mathrm{BPP}$，更没有去随机异或引理本身——那是 1997 年标题里的那一步。唯一可满足性的随机完全性不在页码 80 至 91 里。零知识、交互证明与概率可验证明同样不在。对照属于 计算复杂性 地图、密码学基础 总览与 随机算法 总览。本页把「略微难的谓词怎样沿异或变成假硬币」写成一次条件句。混合回答的是间隙从字符串搬到比特上的存在性。两句都不是操作单。

跨域连接#

• 姚期智一九七九年通信复杂度论文：那五页把算力拿掉，只计跨缝比特；本页把算力写回多项式，问观察者还看得见多少。1979 年的识别函数在确定性一侧必须说全；1982 年的发生器则问，探针所用的硬币能否被单向置换冒充。把通信下界听成已经给出陷门，会把一条无条件的割收成一条密码学假设。
• 密码学基础：总览需要单向函数、陷门与计算不可区分。本页提供 1982 年把三块焊在一起的那一次：陷门负责不对称，不可区分负责「看见不等于得到」，异或负责把略微的平均情形硬度写成硬核。它没有造出 RSA，也没有把离散对数写成步骤。
• 尼桑–维格德森一九九四年论文：那十九页把假设从单向置换降到指数时间里的难近似，发生器被允许慢到种子的指数。本页的发生器必须自己跑在多项式时间里，假设因此停在密码学。没有 1982 年的不可区分语言，1994 年没有「骗过测试者」可写；没有 1994 年的设计，本页走不到 $P=\mathrm{BPP}$。
• 因帕利亚佐–维格德森一九九七年论文：那十页去随机的正是本页的异或引理。独立样本会把输入胀成多项式倍，指数电路下界在新长度上只剩亚指数；1997 年用线性种子走完放大，指数才保住。把 1982 年听成已经证明 $P=\mathrm{BPP}$，会把一次密码学条件句收成一次最坏情形电路条件句。
• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：零知识把本页的不可区分从发生器输出搬到证明对话的文本上。模拟器能造出的东西就不算额外知识。1985 年钉住的语言是二次非剩余，不是陷门迭代。把零知识听成又一条密钥流，会把传证问题收成传消息问题。
• 阿德尔曼一九七八年论文：无条件的非均匀上界说，每个长度都有一条好硬币，造硬币的手续却不必可算。本页若假设成立，发生器本身可算，枚举才给出均匀的亚指数模拟。一张存在性电路与一台多项式时间发生器，不是同一印刷。
• 平均情况复杂性：五个世界问随机实例是否仍然难；单向置换是「几乎所有点上都难反演」这一档。异或引理处理的是从「略微难」到「几乎不可预测」的平均情形放大，不是最坏点上的一枚反例。本页不把难实例的抽样写成攻击步骤。
• 证明：十二页证明的是翻译手续存在：弱优势可被异或改写成强不可预测，整串可区分可被混合改写成某一比特可预测。证书是归约，不是一张已写出的种子表。把条件句听成已经造出陷门，会把存在性翻译说成求值手续。

参考文献#

• Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, Chicago, 3–5 November 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 本文对象：计算不可区分、陷门函数、异或放大，以及单向置换上的发生器与亚指数模拟。
• Andrew C. Yao, "Some Complexity Questions Related to Distributive Computing (Preliminary Report)", Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, 1979, pp. 209–213. DOI: 10.1145/800135.804414. —— 1979 年通信复杂度封面，用以标明与本页不是同一印刷。
• Andrew C. Yao, "Protocols for Secure Computations", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 160–164. DOI: 10.1109/SFCS.1982.88. —— 同一届 FOCS 的安全两方计算邻居，页码不是 80 至 91。
• Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits", SIAM Journal on Computing 13(4), 1984, pp. 850–864. DOI: 10.1137/0213053. —— 离散对数上的密码学发生器；会议先行本为同一本 1982 年 FOCS 页码 112 至 117。
• Noam Nisan & Avi Wigderson, "Hardness vs Randomness", Journal of Computer and System Sciences 49(2), 1994, pp. 149–167. DOI: 10.1006/jcss.1994.1039. —— 后年邻居：把假设降到指数时间难近似的快速发生器。
• Russell Impagliazzo & Avi Wigderson, "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma", Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 220–229. DOI: 10.1145/258533.258590. —— 去随机本页异或引理，并从最坏情形指数电路走向 $P=\mathrm{BPP}$。
• Leonard Adleman, "Two Theorems on Random Polynomial Time", Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978, pp. 75–83. DOI: 10.1109/SFCS.1978.37. —— 无条件的非均匀邻居：随机多项式时间具有小电路。
• Leonid A. Levin, "One-way Functions and Pseudorandom Generators", Combinatorica 7(4), 1987, pp. 357–363. DOI: 10.1007/BF02579323. —— 异或引理第一份完整印刷证明，课堂仍把名字留在 1982 年 FOCS。
• Oded Goldreich & Leonid A. Levin, "A Hard-Core Predicate for all One-Way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32. DOI: 10.1145/73007.73010. —— 任意单向函数上的内积硬核，不是本页封面。
• Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 291–304. DOI: 10.1145/22145.22178. —— 把不可区分从发生器输出搬到证明对话。

延伸阅读#

• 与 姚期智一九七九年论文 对读：跨缝比特对多项式观察者。
• 与 尼桑–维格德森一九九四年论文 与 一九九七年论文 对读：密码学发生器、快速发生器，以及被去随机的异或。
• 与 密码学基础 对读：陷门是定义，不是一份已造好的公钥。