Blum–Micali 1984：离散对数硬核怎样迭代成密码学伪随机比特

破除误解：硬核不是输出里藏着的某一坐标，发生器也不是已经造好的密钥流#

第一种最快的读法是：把 1984 听成 1982 年那六页 FOCS，或听成同一届芝加哥年会上姚期智那十二页。先行本与期刊共享标题，页码、篇幅与 DOI 却不是同一印刷。期刊把定义、归约与发生器写完整，封面停在第 13 卷第 4 期。姚期智的十二页问的是陷门、异或放大，以及「任一单向置换」这一档更宽的理论；本页问的是素数模上的原根指数，以及这一枚左右半谓词是否与求离散对数一样硬。把三份封面收成一句「布卢姆、米卡利与姚期智 1982」，会把具体数论发生器与抽象硬度放大焊成一次页码。

第二层误解把硬核听成「函数输出里已经藏好的某一指定比特」，或听成 1989 年那枚公开的内积。原文给的不是 $g^{x}\bmod p$ 的某一二进制位，而是把 $\{1,\ldots,p-1\}$ 从中剖开的那一刀：原像作为整数落在左半还是右半。猜的人看得见像，看不见原像，却仍不该比抛硬币好多少。戈德赖希–列文后来才证明，任意单向函数只要加上等长填充，原像与公开向量的模二内积就是硬核，而且安全强度只损失多项式。本页回答的是「这一族代数置换上，哪一枚指定谓词与整体一样硬」。两句不是同一印刷。把硬核听成密钥表里的某一列，会把一次公开的左右判定收成一次对秘密坐标的点名。

第三层误解把标题听成已经证明离散对数困难，或已经造出可部署的比特源。十五页是条件句：若在素数模的乘法群里求离散对数对多项式时间仍然困难，则这一枚左右半不可预测，于是下一比特测试被通过。它没有构造任何单向置换，也没有把「最坏点上难」收成「随机实例上难」之外的新假设——离散对数的随机自归约，本来就把可察觉的优势送回几乎处处可解。把条件句听成存在性定理，会把一次归约收成一次已经完成的密码学。哈斯塔德、因帕利亚佐、列文与卢比后来才从任意单向函数做出发生器；那是后十年的邻居，不是页码 850 至 864。

第四层误解把这里的发生器听成尼桑–维格德森那种「足够快」的去随机装置，或听成一份把模数、原根与迭代轮数焊进产品的装配说明。密码学发生器必须自身跑在多项式时间里，对手与发生器处于同一档，假设因此强到单向置换。去随机化只要求发生器快到枚举种子仍可接受，运行时间允许是种子长度的指数，假设可以降到电路下界。布卢姆–布卢姆–舒布用二次剩余另走一条数论路，封面也不是这一卷。经验上的统计检验只能说明「还没被这一张表抓住」，不能写成多项式时间观察者面前的不可预测。

单向置换、左右半硬核，以及反向吐出的下一比特#

装置从「什么样的随机算数」开始，而不是从一张密钥表开始。香农 1949 年的保密理论把互信息为零写成完美安全：看见输出，关于种子的不确定性丝毫不减。短种子拉长之后，发生器的输出只撑起一块极小的支撑集，统计距离上与真随机相距很远。多项式时间的观察者没有这种全能。布卢姆与米卡利采用的口径是下一比特测试：发生器从短种子写出一长串；若存在某个位置，多项式时间的预测器看见前面那些比特之后，对下一位的猜测显著好于二分之一，则整串就还不是假硬币。通过所有下一比特测试，被他们称作密码学意义上的强。姚期智在同一届 FOCS 上把下一比特与所有多项式时间统计测试写成等价；本页证明的是前一句在离散对数上成立，后一句作为邻居被引用，并不把 1982 年那十二页再印一遍。

单向置换是正向求值容易、反向求原像困难的双射。本页取的燃料是素数模上的离散指数：公开一个奇素数 $p$ 与模 $p$ 的一个原根 $g$，把指数送到幂。反复平方让正向落在多项式时间里；求离散对数则被当作平均情形困难。置换的原像唯一，是双射的代数事实，不是 Unique SAT。离散对数还带一条对密码学友好的随机自归约：若某台算法在不可忽略的一部分实例上能求出对数，随机乘上已知幂次就能把优势摊到几乎整个群上。于是「许多点上略微能算」与「几乎处处能算」在这一族问题上靠得更近。这句话解释的是为何平均情形假设站得住。它不是一份把询问送进具体模数的攻击日程。

硬核谓词把「整段原像难求」收成「一比特难猜」。给定像，左右半问的是原像作为 $1$ 到 $p-1$ 上的整数，有没有越过中点。若有预测器在看见像之后仍以不可忽略的优势猜中这一刀，则离散对数本身会变成多项式时间可解。被证明的是翻译手续存在：一比特上的缝可以被送回整段对数。放大并不在本页里用异或完成——姚期智的异或引理处理的是弱不可预测到强不可预测；本页直接钉住这一枚已经够硬的指定比特。戈德赖希–列文的内积后来才把「必须点名代数结构」这条限制拆掉。本页不把左右判定写成从线上系统抽取比特的步骤。

发生器把硬核拉成一长串假硬币。种子是置换的一个输入；正向迭代给出一串像。比特按相反次序吐出：观察者先看见更靠后的迭代所对应的硬核，再被要求猜更靠前的那一枚。下一比特测试里，已经给出的前缀落在像那一侧，要猜的是原像上的硬核。若这一位仍可预测，归约就把优势送回离散对数，与单向假设矛盾。反向不是为了把手续写复杂，而是为了让「看见前缀」在归约里对应「看见像」。自身必须跑在多项式时间里：每一步都是离散指数，输出长度相对种子可以拉长到任意多项式。短种子的输出与真随机在信息论上差得很远，计算上却可以分不开。把「分不开」听成「统计相同」，会把一次复杂性陈述收成一次概率恒等式。本页没有、也不把迭代轮数、模数生成或原根选取写成实现清单。

课堂后来把这一架子称作「单向置换加硬核」。燃料换成任意单向置换、硬核改由戈德赖希–列文提供之后，同一套迭代仍然走得通；任意函数、不一定可逆，仍要等到哈斯塔德–因帕利亚佐–列文–卢比。本页停在离散对数这一枚钉子。

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

它证明了：若素数模上的离散对数对多项式时间仍然困难，则离散指数是单向置换，原像的左右半是硬核谓词，从而存在自身落在多项式时间里、通过下一比特测试的发生器。它把「密码学意义上强」写成可行计算面前的不可预测，而不是写成通过某一张经验统计表。方法论上的句子是：一枚硬核足以把单向置换的平均情形硬度拉成任意多项式长的假硬币；正向迭代负责拉长，反向吐出负责让下一比特落在像那一侧。随机自归约说明，这一族问题上的平均情形与最坏情形靠得比一般单向函数更近。

它没有证明单向函数存在，也没有证明离散对数困难，更没有裁决 $P$ 对 $NP$。十五页是条件句：若这种数论对象在那儿，假硬币就会跟着在那儿。它没有给出戈德赖希–列文那种对任意单向函数都成立的内积硬核，也没有从任意单向函数构造发生器。它没有把下一比特测试与所有多项式时间统计测试的等价写成自己的主定理——那是姚期智同一届 FOCS 的邻居。它没有覆盖尼桑–维格德森的快速发生器与组合设计，没有覆盖因帕利亚佐–维格德森把最坏情形指数电路下界放大成 $P=\mathrm{BPP}$，也没有给出阿德尔曼那种不依赖硬度假设的 $\mathrm{BPP}\subseteq\mathrm{P/poly}$。二次剩余上的布卢姆–布卢姆–舒布发生器、戈德瓦塞尔–米卡利的概率加密，以及同一位米卡利参与的零知识对话，都不在页码 850 至 864 里。乘积密码、密钥流装配，以及如何从线上系统抽取可部署的预测器，同样不在。对照属于 计算复杂性 地图、密码学基础 总览与 随机算法 总览。本页把「离散对数上的一枚指定比特怎样迭代成假硬币」写成一次条件句。左右半回答的是间隙如何从整段原像收到一比特。两句都不是操作单。

跨域连接#

• 姚期智一九八二年陷门函数论文：同一本芝加哥 FOCS，页码 80 至 91 对 112 至 117。那十二页把下一比特与不可区分写成等价，并把发生器的燃料写成任意单向置换；本页把下一比特钉在离散指数的左右半上。没有 1982 年的等价语言，期刊里的「密码学意义上强」少了一张通往所有多项式测试的桥；没有本页的具体硬核，姚期智那一档仍停在「若有单向置换」。把两篇听成一次印刷，会把抽象放大与数论构造叠成一句。
• 戈德赖希–列文一九八九年论文：那八页把硬核从「某些代数函数上的指定比特」改写成任意单向函数上的内积。本页是被改写的那一档：必须先有离散对数，才能点名左右半。安全强度在 1989 年只损失多项式；本页不讨论切块，也不把内积再印一遍。把 1984 年听成已经给出通用硬核，会把一次数论归约收成一次对所有单向函数的定理。
• 密码学基础：总览需要单向函数、硬核与计算不可区分。本页提供 1984 年把三块焊在离散对数上的那一次：置换负责正算容易反算难，左右半负责「看见像不等于得到原像的一比特」，下一比特负责假硬币。它没有造出 Diffie–Hellman 密钥交换，也没有把模数与原根写成步骤。
• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：零知识把不可区分从发生器输出搬到证明对话的文本上。模拟器能造出的东西就不算额外知识。1985 年钉住的语言是二次非剩余，作者里同样有米卡利，对象却不是硬核迭代。把零知识听成又一条密钥流，会把传证问题收成传消息问题。
• 尼桑–维格德森一九九四年论文：那十九页把假设从单向置换降到指数时间里的难近似，发生器被允许慢到种子的指数。本页的发生器必须自己跑在多项式时间里，假设因此停在离散对数。没有 1984 年的下一比特口径，1994 年少了一句「骗过测试者」的密码学先例；没有 1994 年的设计，本页走不到 $P=\mathrm{BPP}$。
• 因帕利亚佐–维格德森一九九七年论文：那十页去随机的是姚期智的异或引理，并把最坏情形指数电路下界送进 $P=\mathrm{BPP}$。本页的发生器仍吃密码学硬度，并不去随机异或。把 1984 年听成已经证明 $P=\mathrm{BPP}$，会把一次数论条件句收成一次电路条件句。
• 随机算法：总览管蒙特卡洛误差如何被独立重复压下去，并已经把米勒–拉宾写成真硬币上的可靠性。本页问的是假硬币能否骗过多项式测试者。归约内部会用随机化把优势摊开，那是证明策略，不是把发生器焊进素数检测的轮数表。把下一比特听成又一次误差放大，会把一次不可预测收成一次正确性。
• 平均情况复杂性：五个世界问随机实例是否仍然难；单向置换是「几乎所有点上都难反演」这一档。离散对数的随机自归约让这一族问题的平均情形与最坏情形靠得更近，本页把这份平均情形硬度集中到左右半上。它不把难实例的抽样写成攻击步骤。

参考文献#

• 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. —— 本文对象：离散指数上的左右半硬核，以及通过下一比特测试的多项式时间发生器。
• Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, Chicago, 3–5 November 1982, pp. 112–117. DOI: 10.1109/SFCS.1982.72. —— 期刊论文的会议前身，六页摘要，不是本页封面。
• 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. —— 同一届 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. —— 把不可区分从发生器输出搬到证明对话；作者里有米卡利，封面不是硬核迭代。
• 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. —— 无条件的非均匀邻居：随机多项式时间具有小电路。
• Whitfield Diffie & Martin E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), 1976, pp. 644–654. DOI: 10.1109/TIT.1976.1055638. —— 离散对数作为公钥硬度的先行文本，不是本页封面。
• Lenore Blum, Manuel Blum & Michael Shub, "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing 15(2), 1986, pp. 364–383. DOI: 10.1137/0215025. —— 二次剩余上的后年发生器，封面陷阱。
• Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 同年邻居：语义安全需要硬核比特，不是本页发生器。

延伸阅读#

• 与 姚期智一九八二年论文 对读：同一届 FOCS 上的抽象发生器对数论发生器。
• 与 戈德赖希–列文一九八九年论文 对读：指定代数比特对通用内积硬核。
• 与 尼桑–维格德森一九九四年论文 与 一九九七年论文 对读：密码学发生器、快速发生器，以及被去随机的异或。
• 与 密码学基础 对读：硬核是定义，不是一份已造好的密钥流。