Impagliazzo–Levin–Luby 1989：一般单向函数怎样交出多项式时间伪随机发生器

破除误解：一般单向不是已经可逆的置换，发生器也不是已经造好的密钥流#

第一种最快的读法是：把 1989 听成会议录下一篇戈德赖希–列文，或听成十年后那份三十三页期刊。内积硬核问的是哪一比特仍不可预测；本页问的是假硬币能不能从单向函数里长出来。两句共用同一本会议录，页码却差一页。1999 年的期刊把任意单向函数写完整，并并入哈斯塔德 1990 年；摘要已宣布等价，篇幅却只够写清两类单向。把三份封面收成一句「哈斯塔德–因帕利亚佐–列文–卢比定理」，会把一次扩展摘要收成一次已经印完的期刊证明。

第二层误解把「从单向函数做发生器」听成布卢姆–米卡利或姚期智已经做完的事。置换是双射：正向迭代给出一串像，硬核按相反次序吐出，下一比特测试里已经看见的前缀落在像那一侧。一般函数不必可逆。同一个像可以有许多原像，不同的像还可以带着不同的原像个数。再把函数作用到自己的输出上，信息会丢，原像集合的大小也会漂。规则单向函数——每个像的原像个数大致相同——还允许戈德赖希–克拉夫奇克–卢比在 1988 年写出一条发生器；退化度可以很大、原像个数随点剧烈变化的那一档，十三页没有写成已经闭合的均匀构造。把「一般单向」听成「已经可以当置换用」，会把一次去掉代数点名的进展收成一次已经走完的任意函数定理。

第三层误解把标题里的伪随机听成经验上的统计检验，或听成一份把轮函数焊进产品的装配说明。十三页采用的口径是计算不可区分，以及与之等价的下一比特不可预测：多项式时间观察者看见前缀之后，对下一位的猜测不该显著好于二分之一。短种子拉长之后，输出只撑起一块极小的支撑集，信息论上与真随机相距很远；可行计算没有这种全能。剩余哈希引理在本页首次被写下：若一串随机变量还剩足够的最小熵，随机挑一枚通用哈希，就能统计上抽出一段接近均匀的短串。这句话是归约里的存在性装置，用来说明「看见像之后仍藏着的不确定性」可以变成看起来均匀的比特。它不是从线上系统抽取会话密钥的步骤。

第四层误解把这里的发生器听成尼桑–维格德森那种「足够快」的去随机装置，或听成因帕利亚佐 1995 年那块硬核分布。密码学发生器必须自身跑在多项式时间里，假设因此强到单向函数。去随机化允许发生器慢到种子的指数，假设可以降到电路下界。1995 年的硬核集中的是实例测度，不是短种子拉长。把四份封面收成一句「硬度换随机性」，会把密码学发生器与复杂度类内部的模拟叠成一次印刷。

两类单向、下一比特，以及置换为何比一般函数容易#

装置从「什么样的单向」开始，而不是从一张密钥表开始。摘要给出两档。第一档：函数容易正算；输入均匀抽取之后，小电路很难从像里找回任意一个原像。安全写在非均匀对手上。第二档：函数的退化度小——看见像之后，原像里还剩的不确定性被上界管住——并且快速算法很难找回原来那一个输入。安全写在均匀算法上。两档都比「必须是置换」或「必须是离散指数」宽。先前能把发生器写出来的，是布卢姆–米卡利的数论置换、姚期智的任意单向置换、列文 1987 年《组合学》第 7 卷第 4 期那条仍要求函数在迭代下保持单向的构造，以及戈德赖希–克拉夫奇克–卢比对规则函数的结果。本页把「特殊结构」往下拆了一档。它没有、也不声称已经造出任何具体的单向函数。

下一比特测试与不可区分在姚期智 1982 年已经被写成等价。发生器从短种子写出一长串；若存在某个位置，多项式时间预测器看见前面那些比特之后仍对下一位保持不可忽略的优势，则整串还不是假硬币。通过所有下一比特测试，就通过所有多项式时间统计测试。本页要证明的是：上述两档单向函数各自给出一台通过这些测试的多项式时间发生器，并且反过来也成立。自身必须跑在多项式时间里，输出相对种子可以拉长到多项式。短种子的输出与真随机在信息论上差得很远，计算上却可以分不开。把「分不开」听成「统计相同」，会把一次复杂性陈述收成一次概率恒等式。本页不把区分游戏写成对部署系统的检测步骤。

置换更容易，是因为原像唯一，正向迭代不会把支撑集揉乱。有了戈德赖希–列文的内积硬核，布卢姆–米卡利那一套「正向走、反向吐」对任意单向置换都走得通，不必再点名左右半或离散对数。一般函数没有这张双射。像的原像个数一旦随点变化，看见 $f(x)$ 之后 $x$ 还剩多少最小熵，就会变成一件随实例漂的事。剩余哈希处理的是熵还够用的那一段：通用哈希把剩余最小熵收成统计上接近均匀的短串。硬核处理的是「函数值不泄露哪一比特」。两件装置要焊在一起，才能把「难求原像」翻译成「输出看起来像硬币」。规则函数的原像个数差不多，熵的账好算；退化度很大时，账本本身就难估计。十三页把小退化度写进第二档，正是承认均匀算法面前这本账还没有对任意函数结清。1999 年的期刊才把「不必规则、也不必先限制退化度」写成完整构造。这些句子回答的是间隙如何从求逆回到假硬币。它们不是查询日程，也不是轮密钥表。

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

它证明了：存在上述第一档单向函数，当且仅当存在能骗过小电路的多项式时间发生器；存在上述第二档单向函数，当且仅当存在能骗过快速算法的多项式时间发生器。必要性几乎是白送的——发生器的输出已经难与真随机分开，截一段当作函数值，求原像就会给出区分器。充分性才是十三页的重量：硬核来自会议录里下一篇，剩余哈希在本页首次写下，置换上的反向吐出被收成特例，规则函数与小退化度函数被推进到一般单向这一档。方法论上的句子是：单向性不必先长成双射，只要像里还藏着不可求的原像，假硬币就可以在多项式时间里被拉长。

它没有证明单向函数存在，也没有裁决 $P$ 对 $NP$。十三页是条件句：若这种平均情形对象在那儿，假硬币就会跟着在那儿。它没有把任意、高度不规则、退化度不受控的单向函数写成已经印完的均匀构造——那是哈斯塔德 1990 年 STOC 与 1999 年期刊完成稿的邻居。它没有给出种子长度后来可接受的发生器；十三页里的拉伸极不经济，后年的简化与效率改进另文。它没有给出因帕利亚佐 1995 年那种硬核分布，也没有把最坏情形指数电路下界送进 $P=\mathrm{BPP}$。它没有覆盖尼桑–维格德森的快速发生器与组合设计。同一届西雅图 STOC 页码 44 至 61 的因帕利亚佐–鲁迪奇文本问的是单向置换能不能黑盒地长成密钥协商，对象也不是本页的发生器。乘积密码、密钥流装配，以及如何从线上系统抽取可部署的预测器，同样不在页码 12 至 24 里。对照属于 计算复杂性 地图、密码学基础 总览与 平均情况复杂性 总览。本页把「一般单向函数怎样冒充假硬币」写成一次条件句。两类单向回答的是摘要实际覆盖到哪一档。两句都不是操作单。

跨域连接#

• 戈德赖希–列文一九八九年论文：同一本西雅图会议录，页码 12 至 24 对 25 至 32。那八页交出任意单向函数上的内积硬核；本页把这枚比特当成发生器的燃料，并在摘要里写明「以本质的方式使用」紧随其后的那一篇。没有硬核，单向置换上的反向吐出少了一枚不必点名代数结构的钉子；没有本页，硬核仍停在谓词，还没有变成多项式长的假硬币。把两篇听成一次印刷，会把一比特与一长串叠成一句。
• 布卢姆–米卡利一九八四年论文：那十五页在离散指数上指定左右半，再按相反次序吐出。本页保留「正向走、反向吐」这套几何，却把燃料从原根指数换成一般单向。左右半是一枚数论谓词；内积是后年才通用的谓词。把 1984 年听成已经给出任意函数上的发生器，会把一次数论归约收成一次对所有单向函数的定理。
• 姚期智一九八二年陷门函数论文：那十二页把下一比特与不可区分写成等价，并把发生器的燃料写成任意单向置换。本页沿用这套总体语言，要去掉的是双射。没有 1982 年的等价，十三页里的「骗过测试者」少了一张通往所有多项式测试的桥；没有本页，姚期智那一档仍停在「若有单向置换」。异或引理在那边是硬度放大，在这边不是封面。
• 密码学基础：总览需要单向函数、硬核与计算不可区分，并把发生器写成同一棵树上的果实。本页提供 1989 年把「一般单向已经够用」钉进会议录的那一次：置换不再是必经的中间站，离散对数也不再是必点名的代数。它没有造出迪菲–赫尔曼密钥交换，也没有把拉伸参数写成步骤。把本页听成一份密钥流说明书，会把一次归约收成一次对部署系统的构造。
• 尼桑–维格德森一九九四年论文：那十九页把假设从单向函数降到指数时间里的难近似，发生器被允许慢到种子的指数。本页的发生器必须自己跑在多项式时间里，假设因此停在单向函数。引言把分野写在对照里：因帕利亚佐–列文–卢比证明单向函数与多项式时间发生器等价；1994 年证明难近似与快速发生器等价。两套等价共享「硬度可以冒充硬币」，效率与假设强度却不是同一档。
• 平均情况复杂性：五个世界问随机实例是否仍然难；单向函数是「几乎所有点上都难反演」这一档，也是 Minicrypt 的门槛。本页把这档平均情形硬度翻译成假硬币，从而把「单向函数存在当且仅当发生器存在」写成五个世界里可以移动的一堵墙。它不把难实例的抽样写成攻击步骤，也不把 Minicrypt 与 Cryptomania 之间那道因帕利亚佐–鲁迪奇的墙再印一遍。
• 克劳德·香农：1949 年的保密理论把互信息为零写成完美安全；短种子一旦拉长，统计距离上已经不可能再冒充真随机。本页的假硬币承认这一笔信息论亏空，只要求多项式时间观察者看不见缝。剩余哈希处理的是还剩的最小熵，不是把互信息重新算成零。把计算不可区分听成完美安全，会把一次复杂性陈述收成一次香农等式。
• 熵与时间之箭：玻尔兹曼的 $S=k\ln\Omega$ 数的是宏观标签下有多少微观排法；本页的最小熵数的是，看见像之后原像还剩多少不可被猜中的不确定性。两本账都在数可能性，窗口不同。热力学熵不依赖对手的计算预算；剩余哈希抽出来的均匀性是统计语句，再被硬核改写成计算语句。把假硬币听成热力学时间之箭，会把一次归约收成一次孤立系统的不可逆。

参考文献#

• Russell Impagliazzo, Leonid A. Levin & Michael Luby, "Pseudo-random Generation from One-way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, 15–17 May 1989, pp. 12–24. DOI: 10.1145/73007.73009. ISBN: 0-89791-307-8. —— 本文对象：两类一般单向函数与多项式时间发生器的等价，以及剩余哈希引理。
• 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. —— 同一本会议录的下一篇：任意单向函数上的内积硬核，本页以本质方式使用。
• Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits", SIAM Journal on Computing 13(4), November 1984, pp. 850–864. DOI: 10.1137/0213053. —— 数论邻居：离散指数上的左右半硬核与下一比特。
• Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 单向置换、不可区分与异或放大；本页要去掉双射。
• Leonid A. Levin, "One-Way Function and Pseudorandom Generators", Combinatorica 7(4), 1987, pp. 357–363. DOI: 10.1007/BF02579324. —— 先行邻居：迭代下仍保持单向的函数。
• Oded Goldreich, Hugo Krawczyk & Michael Luby, "On the Existence of Pseudorandom Generators", SIAM Journal on Computing 22(6), 1993, pp. 1163–1175. DOI: 10.1137/0222069. —— 规则单向函数上的发生器，摘要所引 1988 年结果的期刊。
• Johan Håstad, "Pseudo-Random Generators under Uniform Assumptions", Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 395–404. DOI: 10.1145/100216.100270. —— 均匀假设下的后年邻居，1999 年期刊与本页合并。
• Johan Håstad, Russell Impagliazzo, Leonid A. Levin & Michael Luby, "A Pseudorandom Generator from any One-way Function", SIAM Journal on Computing 28(4), 1999, pp. 1364–1396. DOI: 10.1137/S0097539793244708. —— 期刊完成稿：任意单向函数上的完整构造，不是封面。
• 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. —— 去随机邻居：发生器可慢到种子的指数。
• Russell Impagliazzo, "Hard-Core Distributions for Somewhat Hard Problems", Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995, pp. 538–545. DOI: 10.1109/SFCS.1995.492584. —— 封面陷阱：硬核分布，不是发生器。

延伸阅读#

• 与 戈德赖希–列文一九八九年论文 对读：同一本会议录上的硬核谓词对发生器。
• 与 布卢姆–米卡利一九八四年论文、姚期智一九八二年论文 对读：置换对一般单向。
• 与 尼桑–维格德森一九九四年论文 对读：多项式时间发生器对快速发生器。
• 与 密码学基础 对读：发生器是条件句，不是已造好的密钥流。