Goldreich–Levin 硬核位定理

固定隐藏字符串 $x$ 后，全部随机内积构成它的 Hadamard 编码。预测器虽然经常答错，但只要略偏向正确答案，就在这张极长的编码表里留下一个可检测的相关方向。

恢复不应逐一猜 $2^n$ 个字符串。重 Fourier 系数搜索公理库Kushilevitz–Mansour 算法Kushilevitz-Mansour algorithm利用成员查询估计一组 Fourier 系数的总平方质量，递归剪枝找出全部显著系数而不枚举整个频谱。能找出全部显著相关方向，并且数量是多项式。真正的密码学归约还要补三件事：把平均优势转换成足够多的好输入，允许同一点查询带独立随机噪声，最后把候选方向交回 $f$ 验证。

第一步：平均优势不能只属于极少数输入 ​

固定 $x$，令它的预测相关度为

它等于该 $x$ 上预测成功率的两倍减一，取值于 $[-1,1]$。总成功率假设给出 ${\mathbb{E}}_X{c}_X\ge 2\epsilon$。

称 $c_x\ge \epsilon$ 的输入为好输入，比例记为 $q$。不好输入的相关度小于 $\epsilon$，好输入最多为一，因此

这一步保证反演器有至少逆多项式比例的机会遇到可恢复输入。只证明“某个输入可恢复”不足以反驳平均情形单向性。

第二步：固定像后，预测器提供一个有噪声的函数接口 ​

反演器收到 $y=f(x)$，不知 $x$。对任意自行选择的 $r$，它可以重新运行公开算法 $A(y,r)$。定义理论上的平均响应函数

它不需要被精确计算；每次运行 $A$ 就得到一个取值为 $\pm 1$、期望为 $g_y(r)$ 的独立样本。其Fourier 系数公理库Fourier–Walsh 展开与影响度Fourier-Walsh expansion · Boolean Fourier analysis在均匀布尔立方体上用字符正交基展开函数，把方差和坐标影响写成 Fourier 系数的平方和。为

对真实隐藏输入 $x$，有 ${\hat{g}}_y(x)=c_x$。如果 $x$ 好，这个系数至少为 $\epsilon$。

这里不能固定一份会在不同 $r$ 上造成未知相关性的噪声表，再假装已有精确成员查询。每次调用 $A$ 使用新的独立随机币，才得到下面需要的乘积无偏性。

第三步：复用重系数搜索，生成短候选表 ​

已有 KM 搜索页证明了以 $\theta$ 为阈值找到所有重系数的前缀质量算法。它在此只需一个明确扩展：把确定的 Boolean 函数换成 $g_y\in [-1,1]$，并用独立随机响应查询。

Parseval 给出 $\sum _z{\hat{g}}_y(z{)}^2=\mathbb{E}{g}_y^2\le 1$，所以重系数仍至多 $1/{\theta }^2$ 个。对共享后缀的两次成员查询，独立响应 $B,B^{\prime }\in \{-1,1\}$ 满足

于是 KM 的前缀质量估计器仍然无偏，取值仍在 $[-1,1]$，原来的集中界、剪枝余量与节点上限原样适用。这核对了接口，不必重新发明一套频谱搜索。

取 $\theta =\epsilon$、失败概率 $1/3$。得到的列表 $L_y$ 包含全部 $|{\hat{g}}_y(z)|\ge \epsilon$ 的位置，并且可以用该页的保守实现，在

次预测器调用内完成，列表规模至多 $2/{\epsilon }^2$。在所有估计准确的事件上，每个好输入 $x$ 都在列表中。上述次数计的是 $A$ 调用；总运行时间还要乘每次调用成本并加上记录前缀的多项式工作。

第四步：列表方向必须变成可验证原像 ​

反演器依次计算 $f(z)$，只要 $z\in L_y$ 且 $f(z)=y$ 就输出。错误候选不会通过验证；若其中有别的有效原像，输出它同样成功。对好输入，列表以至少 $2/3$ 的概率包含真实 $x$，所以由式 (1)，总反演成功率至少 $2q/3\ge 2\epsilon /3$。

若预测优势在无穷多个长度上至少为某个逆多项式，可用该逆多项式作搜索阈值，在这些长度上得到不可忽略反演概率，违反单向性。无需假装反演器事先知道实际每一长度的精确优势。

一个小编码例子 ​

取 $x=101$，按 $r=000,001,\dots ,111$ 排列，内积位为

它不是某个固定坐标，而是所有坐标按公开 $r$ 选择后的奇偶。若平均响应函数为

则 $g\in [-0.7,0.7]$，可通过随机返回 $+1$ 的概率 $(1+g(r))/2$ 实现。真实方向 $101$ 的相关度为 $0.4$，对应预测成功率 $0.7$。搜索可能还留下 $010$ 这个相关方向；只有最后的 $f(z)=y$ 验证才把“有相关”与“是有效原像”区分开。这个三位例子演示接口，不提供小参数密码安全。

$F(x,r)=(f(x),r)$ 仍然单向：若能反演 $F$，给定 $f(x)$ 后自选均匀 $r$，再丢掉反演输出中的 $r$ 即可反演 $f$。若 $f$ 原本是长度保持置换，$F$ 也是置换，因而可以接上硬核位生成器构造。

若 $f$ 只是一般单向函数，Goldreich–Levin 提供硬核位，却没有让 $f(U_n)$ 自动变均匀。从一般单向函数到密码学 PRG 仍需要额外构造，不能跳过这个分布形状问题。