下一位不可预测性与伪随机性

若一整串有可识别的结构，总要有某一步开始让“真实位”和“新抛的公平硬币”产生差别。把真实串一位一位替成均匀位，区分优势的总变化会分摊到这些交界处。

单个断点的差别可能很小，均匀位置版本至多为 $K<2m$ 个位置支付线性因子。但只要 $m$ 是多项式，这不会把可见的逆多项式优势变成可忽略量。

预测器直接给出一个检验 ​

给定 $(1^n,z)$，区分器按同一个二的幂规则抽取 $i\in [K]$。当 $i\le m$ 时，让 $P$ 看见 $(1^n,i,z_{<i})$，检查它是否猜中 $z_i$；当 $i>m$ 时，给 $P$ 空前缀，并检查其输出是否等于另抽的一枚独立公平比特。

若 $z\sim U_m$，真实位置的下一位独立于整个前缀和预测器随机币，补位的目标也独立公平，所以检验通过概率恰为 $1/2$。若 $z\sim Z_n$，通过概率就是 $P$ 的实际预测成功率。因此预测优势直接成为区分优势。这一步不需要观察者知道生成种子。

从区分器构造预测器 ​

设统一算法 $D$ 在带安全参数的输入上满足

这里先对显示的正差值计算。用混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。定义

其中后缀是独立均匀位。记

望远镜求和给出 $\sum _i{\mathrm{\Delta }}_i=\epsilon$。接到真实前缀 $z_{<i}$ 后，预测器独立抽一个候选位 $b$ 和均匀后缀 $r$，运行 $D(1^n,z_{<i},b,r)$：若输出一，就猜 $b$；否则猜 $1-b$。

固定前缀与真实下一位 $z_i$，记 $d_0,d_1$ 为补位分别为零和一时，$D$ 对后缀及内部随机币平均后的接受概率。预测成功率为

而把真实位替换成公平位造成的接受概率差恰好是

再对真实前缀和下一位平均，成功率就是 $1/2+{\mathrm{\Delta }}_i$。对补位 $i>m$，记 ${\mathrm{\Delta }}_i=0$。位置 $I$ 在 $[K]$ 上均匀时，最终优势为

对于一个固定的统一区分器，设其差值为 $\delta (n)$，符号可以随 $n$ 改变。固定构造两台预测器 $P_D,P_{1-D}$，它们的带符号预测优势分别为 $\delta (n)/K(n)$ 与 $-\delta (n)/K(n)$。若 $|\delta (n)|$ 不可忽略，在满足某个逆多项式下界的无穷多个长度中，总有一种符号出现无穷多次；对应的那一台固定预测器便有不可忽略的正优势。因此至少一台违反下一位安全性，无须任何逐长度求符号的算法。

预测器只需自己产生补位和后缀，并运行一次 $D$；它没有请求隐藏分布的条件采样 oracle。这也是均匀版本不必假设 $Z_n$ 可高效采样的原因。

单个容易预测的末位也会暴露 ​

取 $m\ge 2$，令 $Z=(U_1,\dots ,U_{m-1},U_1)$，前 $m-1$ 位完全独立，末位重复首位。最后一位可被完美预测；在本页的补位实验中，仅利用这一位置、其余位置随机猜，优势为 $1/(2K)$；若数学上直接均匀选取 $[m]$ 中的位置，则对应值为 $1/(2m)$。

这个优势会随串长变小，却在 $m$ 多项式时仍不可忽略。整串检验只需比较首末两位，真实串通过概率一，均匀串通过概率 $1/2$。所有单个位的边缘分布都均匀，仍不足以保证伪随机。

硬核位构造常先证明“给出公开函数像，仍不能预测一个比特”，再把该比特作为生成器的新输出。硬核谓词公理库单向函数的硬核谓词Hard-core predicate · Hard-core bit区分整份输入难反演与某一位难预测，定义带公开像的硬核谓词，并证明单向置换加一枚硬核位得到长度加一生成器。讨论这种预测问题；这里只在一个已经给定的串分布上比较两种安全标准。

本定理依赖可见优势与输出长度的预算。若允许指数长输出，却只给一个位置的逆指数级预测优势，前面的归约未必导出多项式安全意义下的攻击。预测器也必须只看前缀；允许它看目标位本身，或者额外得到生成种子，就改变了实验。