Goldreich–Levin 1989：每个单向函数都有一枚内积硬核谓词

破除误解：硬核谓词不是藏在原像里的某一指定比特#

第一层误解把标题听成「单向函数已经把某一命名比特藏起来了」，例如最高位、最低位，或离散对数里布卢姆–米卡利挑出的那一枚。原文给的不是 $f$ 自己的某一坐标，而是填充之后的内积 $B(x,p)$：向量 $p$ 与 $x$ 等长、随函数值一起公开，谓词是它们的模二点积。猜的人看得见 $f_0(x)$ 也看得见 $p$，却仍不该比抛硬币好多少。把硬核听成「输出里藏着的那一位」，会把一次公开的线性抽样收成一次对秘密坐标的点名。布卢姆–米卡利 1982 年对离散指数、以及阿莱克西–乔尔–戈德赖希–施诺尔对 RSA 与拉宾函数的结果，回答的是「某些代数函数上哪一枚指定比特与整体一样硬」。本页回答的是「任意单向函数，不必再点名代数结构」。两句不是同一印刷。

第二层误解把 1989 年听成姚期智已经做完的事，或听成「异或引理换了封面」。1982 年的 $f^*$ 把输入切成许多短块、对每一块并行求 $f$，再用异或把弱不可预测放大成强不可预测。原文把这笔账写清楚：安全强度小于原函数的任意正次幂；块一短，穷举就顶得上归约。本页的句子是等价而不是切块。定理 1：若填充后的 $f$ 在分布 $d$ 上以安全强度 $s$ 单向，则同一 $s$ 上 $B$ 是硬核。求逆与猜内积，对多项式时间概率算法是同一档任务。异或出现在这里，是因为布尔内积本来就是被 $p$ 选中的那些坐标的异或。它是这枚谓词的写法，不是 1982 年那条要把许多独立实例并在一起的放大引理。

第三层误解把「硬核」听成因帕利亚佐 1995 年的硬核分布，或听成已经证明单向函数存在。分布版问的是：一个只是略微难的判定问题，是否藏着一块几乎处处都难的测度。谓词版问的是：函数值已经在手，哪一比特仍然不可预测。本页没有构造任何单向函数，也没有把「平均情形难」收成「最坏情形难」。它只说，若求逆已经难，则这一枚内积同样难。把条件句听成存在性定理，会把一次归约收成一次已经完成的密码学。哈斯塔德–因帕利亚佐–列文–卢比后来才从任意单向函数做出伪随机发生器；那是后十年的邻居，不是页码 25 至 32。本页至多把布卢姆–米卡利式的发生器从「需要一枚已知硬核的置换」放到「任意单向置换都够用」。任意函数、不一定可逆，仍要另文。

第四层误解把主引理听成一份对已部署系统抽比特的操作单，或把托普利茨矩阵听成乘积密码的轮函数。主引理给出的是归约的存在性：若某台算法对内积仍有不可忽略的猜测率，则存在另一台算法列出一份短名单，其中包含所有本地猜测率够高的原像。名单用正向计算 $f$ 来核对。致谢里列文记下彼得·埃利亚斯关于列表译码的评论，那是证明策略的来源，不是把哈达马码写成攻一个系统的查询表。推论 1 用双倍填充与托普利茨矩阵一次交出大约 $\log s(n)$ 枚硬核比特，并说明再多就需要额外假设：单向函数可以只作用在 $\log s$ 个比特上、其余原样输出。概念证据到此为止。它不指出该查询哪一个具体方案，也不给出可部署的预测器。

填充、内积，以及把猜测率收成候选名单#

装置从两个速率开始。求逆算法 $I$ 的求逆率 $R_{I,f,d}$ 同时记下成功概率与平均时间：时间可以被随机时限吸收进成功率，于是「单向」就是对所有概率算法，这个率相对安全强度 $s$ 可忽略。猜测算法 $G$ 输出 $\{+1,-1,0\}$，零表示拒猜。猜测率 $R_{G,f,b,d}$ 记下谓词与猜测的相关，同样吸收时间。硬核谓词就是对所有 $G$，这个率相对 $s$ 可忽略。谓词在文中取 $\pm 1$，布尔异或对应乘法。这套会计让「安全强度相同」可以写成同一函数 $s$，而不必另开一张多项式表。

填充把公开的抽样向量焊进函数值。称 $f$ 为填充的，当它形如 $f(x\circ p)=f_0(x)\circ p$ 且 $|p|=|x|$。双倍填充则取 $|p|=2|x|$。内积谓词 $B(x,p)$ 按 $x$ 与 $p$ 的模二点积取 $\pm 1$。定理 1：任意填充的 $f$ 与实例分布 $d$，只要 $f$ 在 $d$ 上以强度 $s$ 单向，则 $B$ 在同一 $d$ 上是强度 $s$ 的硬核。简单情形 $d(x)=x$ 就是均匀输入；一般 $d$ 允许单向性只对某一可有效抽样的分布成立。列文 1987 年猜想的正是这一句，而不是「再造一台更碎的 $f^*$」。

主引理把定理收成名单。给定子程序 $G$、硬币源与精度 $\varepsilon$，算法 $I$ 输出一份名单，其中包含所有本地猜测率至少为 $\varepsilon$ 的 $x$。名单长度由猜测率控制，失败只发生在一小部分硬币上。第一阶段调用 $G$，第二阶段不再调用，只用已经记下的相关去筛前缀。证明把 $B(\cdot,\cdot)$ 看成一张正交的哈达马型矩阵：不同原像的内积行互相正交，平方和守恒，因此「相关够高」的候选不会多到指数。逐步延长前缀时，只需近似一个二次型上界 $c(z)$，不必真去穷举余下的比特。近似靠中位数重复，而不是靠对某一固定系统的自适应询问。并行写法可以把各段子串的候选名单并起来，时间变成 $\varepsilon$ 的对数。这些句子回答的是间隙如何从一比特回到整段原像。它们不是查询日程。

多比特停在对数。定义 3 把硬核函数写成：给定 $f(x)$，其输出与真随机串在可行时间内不可区分。推论 1：双倍填充之后，由 $p$ 决定第一行与第一列的托普利茨矩阵乘上 $x$，在 $k(n)=\log s(n)$ 时是硬核函数，强度仍是 $s$。证明借用瓦齐拉尼 1987 年的抽样与瓦齐拉尼–瓦齐拉尼 1984 年的异或条件：一串比特整体难猜，当且仅当任意非空子集的异或难猜；而子集异或正是内积。原文写明，这个数目不能在没有新假设或复杂性突破的情况下再加大，因为存在只碰 $\log s$ 个比特的单向函数。线性抽取这一受限口径下的最优，可以单独证明。托普利茨在这里是一份组合证据，不是轮密钥表。

它因此改写了 1980 年代的两档答案。一档依赖离散对数、RSA 或拉宾函数的代数结构，才能指出哪一枚指定比特硬。另一档用姚期智的切块得到通用硬核，却把安全强度切碎。八页把两档收成一句：填充后的内积对每个单向函数都硬，而且硬得与求逆同阶。伪随机发生器、概率加密在引言里被写成需要硬核的应用；本页提供谓词，不提供发生器的迭代表，更不把布卢姆–布卢姆–舒布或戈德赖希–戈德瓦塞尔–米卡利的随机函数写成封面。

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

它证明了：每个填充后的单向函数都有一枚内积硬核谓词，安全强度与求逆相同。猜内积与列出原像，在多项式时间概率算法的尺度上等价。它证明了大约 $\log s(n)$ 枚这样的比特可以一次交出，且在线性抽取的口径下这已接近最优。方法论上的句子是：单向性可以集中到一比特上，而不必先把输入切成可穷举的碎块。列表而不是单点复原，是因为噪声下的内积只保证短名单，核对仍要靠正向计算。

它没有证明单向函数存在，也没有裁决 $P$ 对 $NP$。它没有从任意单向函数构造多项式时间的伪随机发生器；那一步是哈斯塔德、因帕利亚佐、列文与卢比的后话。它没有给出因帕利亚佐 1995 年那种硬核分布，也没有把最坏情形电路下界放大成平均情形不可预测。它没有打开交互式证明，没有把零知识写成对象，也没有给出任何显式函数的超多项式电路下界。姚期智 1982 年的异或放大、布卢姆–米卡利对离散指数的指定比特、阿莱克西等人对 RSA 与拉宾函数的指定比特，都是邻居，不是把这八页再印一遍。乘积密码、密钥流装配，以及如何从线上系统抽取可部署的预测器，都不在页码 25 至 32 里。对照属于 计算复杂性 地图、密码学基础 总览与 平均情况复杂性 总览。本页把「任意单向函数怎样交出一枚公开的线性比特」写成一次归约。名单回答的是噪声下为何仍能回到原像。两句都不是操作单。

跨域连接#

• 密码学基础：总览把单向函数写成公钥体系的工作假说，并把伪随机发生器、语义安全列成同一棵树上的果实。
• 本页补上缺失的那一枚通用比特：不必先有离散对数或 RSA 的指定硬核，填充后的内积已经够用。
• 发生器、加密与签名仍要另做拼装；八页只把「函数值不泄露哪一比特」写成与求逆同阶的谓词。
• 把本页听成一份密钥流说明书，会把一次归约收成一次对部署系统的构造。
• 平均情况复杂性：五个世界问的是随机实例是否仍然难；硬核谓词问的是函数值已经给出之后，哪一比特仍然不可预测。
• 单向函数本身就是平均情形对象，本页把这份平均情形硬度集中到内积上，而不把最坏点上的难实例冒充成密码学。
• 列文的分布—问题对，与猜测率 $R_{G,f,b,d}$ 的相关对，共用「只在最坏点上难不够」。
• 年的硬核分布是另一枚钉子：它集中的是实例测度，不是这一比特。
• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把额外知识写成可模拟的对话，对象是二次非剩余与零知识。
• 本页的作者是戈德赖希与列文，对象是内积能否被多项式时间猜中。
• 引言引用的是 1984 年概率加密对硬核比特的需求，不是 1985 年的知识复杂度。
• 把两份 STOC 焊成一次「戈氏密码学」，会把传证问题与求逆问题叠成一句。
• 尼桑–维格德森一九九四年论文：那十九页把平均情形难近似换成快速发生器，去骗过 $\mathrm{BPP}$ 测试者。
• 发生器分析里「整段可区分则某一比特可预测」，与本页「整段可求逆则内积可猜测」共用同一方向的间隙搬运。
• 本页提供被搬运的那枚比特；1994 年把它接进组合设计。
• 两页都不是产品里的种子表。
• 因帕利亚佐–维格德森一九九七年论文：十页去随机姚期智的异或引理时，明确把戈德赖希–列文写成把直接积收成布尔内积的装置。
• 异或是内积的布尔特例，在那边是放大步骤，在这边是硬核谓词本身。
• 没有 1989 年的名单，1997 年就还缺一枚把「猜对整段」送回「猜对一比特」的钉子。
• 把本页读成已经证明 $P=\mathrm{BPP}$，会把一次密码学归约收成一次电路下界条件句。
• 姚期智一九七九年论文：五页把布尔表劈成两半，计量跨缝必须说多少话；内积后来成为通信复杂度里最硬的双线性形式之一。
• 本页的 $B(x,p)$ 是同一张模二点积表，硬度却改写在另一根轴上：一边看不见 $x$ 只看见 $f(x)$ 与 $p$，问的是预测优势而不是对话长度。
• 通信下界不依赖单向函数；硬核谓词完全依赖。
• 把 1979 年的资源定义听成 1989 年的密码学归约，会把一次缝上的比特数收成一次求逆率。
• 随机算法：总览管蒙特卡洛误差如何被独立重复压下去。
• 本页的硬币用在归约内部：随机时限吸收运行时间，中位数重复近似二次型，名单对一小部分硬币允许失败。
• 随机算法页问的是真硬币上的正确性；本页问的是假想的猜测算法一旦存在，求逆率会怎样被抬起来。
• 把中位数重复读成对线上系统的查询轮数，会把一次存在性归约收成一次操作单。
• 证明：主引理是归约，不是构造单向函数的手续。
• 一份只证明「猜内积则列出原像」的论证，并不自动给出任何具体的难函数，也不自动给出可部署的发生器。
• 列表译码是证明策略，用来说明噪声下的线性测量仍把候选限制在短名单里。
• 被排除的不是证明的可能性，而是把指定代数比特、切块异或、硬核分布与本页内积焊成同一定理的那一类跳跃。

参考文献#

• 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, Seattle, May 1989, pp. 25–32. DOI: 10.1145/73007.73010. ISBN: 0-89791-307-8. —— 本文对象：填充后的内积是任意单向函数的硬核谓词，安全强度与求逆相同。
• 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. —— 切块构造与异或引理：通用硬核的邻居，安全强度损失更大。
• 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. —— 硬核谓词的来源：离散指数上的指定比特，以及用硬核迭代发生器。
• 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. —— 封面陷阱：交互证明与零知识，不是内积硬核。
• 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. —— 封面陷阱：硬核分布，不是硬核谓词。
• Leonid A. Levin, "One-Way Function and Pseudorandom Generators", Combinatorica 7(4), 1987, pp. 357–363. DOI: 10.1007/BF02579324. —— 第 5.6.2 节猜想：标量积是填充单向函数的硬核。
• Werner Alexi, Benny Chor, Oded Goldreich & Claus-Peter Schnorr, "RSA and Rabin Functions: Certain Parts are as Hard as the Whole", SIAM Journal on Computing 17(2), 1988, pp. 194–209. DOI: 10.1137/0217013. —— 代数邻居：RSA 与拉宾函数上的指定比特。
• 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. —— 把本页内积当作去随机异或的装置。

延伸阅读#

• 与 密码学基础 对读：单向函数树上这枚通用比特落在哪一层。
• 与 平均情况复杂性 对读：平均情形硬度如何被集中到一比特，以及与硬核分布的分叉。
• 与 戈德瓦塞尔–米卡利–拉科夫一九八五年论文 对读：零知识对话对内积猜测。
• 与 尼桑–维格德森一九九四年论文 对读：难近似发生器如何调用一比特间隙。
• 与 因帕利亚佐–维格德森一九九七年论文 对读：直接积怎样被收成布尔内积。
• 与 姚期智一九七九年论文 对读：同一张内积表在通信资源与预测优势上的两种硬度。
• 与 证明 对读：被给出的是归约，不是单向函数的存在性。