单向函数的硬核谓词

把一份完整答案找回来，与回答其中一个简单问题，难度可能差得很远。一个单向函数可以把输入的第一位明文写在输出里，只把其余部分做困难变换。攻击者看懂第一位，并没有因此恢复整份输入。

硬核谓词要求某个特定二元问题连偏向哪边都难判断。它的基线是 $1/2$，所以若谓词在均匀输入下总为零，就绝不可能是硬核位：不看公开像也能完美预测。

单向函数可以泄露坐标 ​

假设 $g$ 是一个单向函数，定义

若能有效反演 $f$，给定 $g(x)$ 后随机选 $a$、调用反演器，再丢掉返回的首位，就能找到 $g(x)$ 的有效原像。因此 $f$ 仍单向。

但谓词 $b(a,x)=a$ 明显不是硬核位，因为输出第一位已直接给出它。这个例子没有改变“反演可返回任意原像”的定义：攻击者仍需恢复足以通过 $g$ 验证的尾部。

硬核性等价于“真实位与公平位难区分” ​

考虑两个联合分布

其中 $U_1$ 独立。若一个预测器有优势，检查其预测是否等于最后一位即可区分它们。

反向固定一个统一判别器 $D$，先在其带符号接受概率差 $\delta (n)>0$ 的长度上计算。给定 $(1^n,y=f_n(X))$，随机选 $u\in \{0,1\}$，若 $D(1^n,y,u)=1$ 就猜 $u$，否则猜 $1-u$。条件于 $y,b_n(X)$ 的二选一计算表明，预测优势恰为 $\delta (n)$。另一台固定预测器把所有猜测取反，优势为 $-\delta (n)$。若 $|\delta (n)|$ 不可忽略，则在达到某个逆多项式下界的无穷多个长度中，至少一种符号出现无穷多次，对应的固定预测器便违反硬核性。无须逐个长度有效判断差值符号，也不需知道 $X$。

从单向置换得到长度加一的生成器 ​

进一步取 $k(n)=n$，假设 $f_n$ 是 $\{0,1{\}}^n$ 上的单向置换公理库单向函数One-way function易于正向计算，但随机输入所产生的像难以被任何高效算法反演的函数族。，且 $b$ 为其硬核谓词。定义

硬核性说明它与 $(f(U_n),U_1)$ 不可区分。置换把均匀分布送到均匀分布，所以后一分布恰好是 $U_{n+1}$。这就得到 $n\to n+1$ 的伪随机生成器公理库伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。。

关键不只是 $f$ 单向，还有“均匀输入经 $f$ 后仍均匀”。若普通单向函数输出前总带一位零，即使它有硬核谓词，直接拼接该谓词后的整串仍会被“检查首位是否为零”区分。不能把上述一行构造直接用于任意单向函数。

Goldreich–Levin 定理公理库Goldreich–Levin 硬核位定理Goldreich–Levin theorem把随机内积预测器的平均优势转为好输入比例、带独立随机响应的重Fourier列表及原像验证，完整证明通用硬核位的反演归约。给出通用入口：若 $f$ 是单向函数，令 $X,R$ 为独立均匀的输入，将函数扩为 $F(x,r)=(f(x),r)$，则随机内积 $b(x,r)=⟨x,r⟩mod2$ 是 $F$ 的硬核谓词。这是对输入进行公开随机查询后的谓词，不是声称原输入的某个固定坐标必然安全。

有了长度加一的安全生成器，伸长放大公理库伪随机生成器的伸长放大PRG stretch amplification将长度加一生成器迭代为状态链，用从早到晚替换的混合证明多项式伸长安全，说明最终状态何时能输出及为什么不能与未来输出同时公开。可以经多项式次状态更新得到长输出。组合证明必须保留公开像、随机输入及辅助位的联合分布；伸长页给出相应的逐轮混合。只证明最后一位的边缘近似公平不够。