伪随机生成器

密码学 PRG 用一小段真正随机的均匀种子确定性扩展出更长比特串；输出并非“数学上随机”，而是要求任何高效测试都找不到可利用的偏差，无法将其与真正均匀串区分。信息论上它不可能均匀：输出支持集最多 $2^n$，小于 $2^{\ell (n)}$，安全依赖区分器无法高效识别这个集合。stretch 必须为正，重复调用或扩展要保持整体不可区分。

线性同余发生器可通过线性关系被高效区分，不是密码学 PRG。下一位不可预测性理路下一位不可预测性与伪随机性Next-bit unpredictability · Yao next-bit theorem用前缀混合把整串区分器变成下一位预测器，明确随机位置的均匀算法版本及输出长度造成的优势损失。精确刻画“给出前缀后仍不能预测下一位”：混合论证把整串区分优势分摊到随机位置。若只有一个多输出一位的安全生成器，伸长放大理路伪随机生成器的伸长放大PRG stretch amplification将长度加一生成器迭代为状态链，用从早到晚替换的混合证明多项式伸长安全，说明最终状态何时能输出及为什么不能与未来输出同时公开。说明怎样逐轮更新内部状态、释放比特，并核算总优势损失。

固定或低熵种子不符合定义；即使算法本身正确，重复种子也会重复全部输出。伸长必须超过种子长度，否则恒等映射会使定义失去生成随机性的意义。

若 $G:\{0,1{\}}^s\to \{0,1{\}}^{2s}$ 安全，则给定 $G(U_s)$ 或 $U_{2s}$，任何多项式算法只能以可忽略优势判断来源。简单输出 $G(x)=x\Vert x$ 显然不安全，区分器检查两半是否相等即可。

统计测试通过不是密码学证明；攻击者可利用任意高效结构。种子若低熵、重复或泄露，输出不再保密；普通模拟/游戏 PRNG 也未必达到密码学不可预测性。有种子提取器理路有种子随机性提取器Seeded randomness extractor · Seeded extractor用独立均匀短种子把任意高最小熵弱源映为统计上接近均匀的输出。处理的是另一方向：它用独立均匀短种子净化较长的 min-entropy 弱源，输出通常更短但统计接近均匀；PRG 不能因输入“有一些熵”就替代 extractor。

在两端采用同一 uniform PPT、标准多项式长度参数化与可忽略优势约定时，PRG 的存在与单向函数理路单向函数One-way function易于正向计算，但随机输入所产生的像难以被任何高效算法反演的函数族。的存在等价。单向函数到 PRG 是 Håstad–Impagliazzo–Levin–Luby 的深刻构造定理，见原论文 Theorem 6.3。[1] 反向先通过伸长放大理路伪随机生成器的伸长放大PRG stretch amplification将长度加一生成器迭代为状态链，用从早到晚替换的混合证明多项式伸长安全，说明最终状态何时能输出及为什么不能与未来输出同时公开。得到 $n\to 2n$ 的生成器，再把反演器包装成“返回种子后重新计算并验证”的判别器。其真实世界接受率等于反演成功率，均匀世界接受率至多为像集占比 $2^{-n}$，故反演成功率至多为区分优势加 $2^{-n}$。这证明加长后的生成器是单向的，而不需要它是置换。

这条等价关系是存在性层次的双向归约，不是两个对象逐字相同，也不把一般单向函数的输出直接当作随机串。计算不可区分性理路不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。给出这里的安全目标；计算安全理路计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。规定对手资源。GGM 构造进一步由 PRG 得PRF理路伪随机函数Pseudorandom function · PRF由短密钥索引且对高效查询者不可与真随机函数区分的函数族。，流密码、随机性扩展和适当的去随机化构造再利用这些资源；各自的查询模型和归约损失仍需单独分析。提取器的统计误差与剩余哈希引理理路剩余哈希引理Leftover hash lemma · LHL二通用哈希把弱随机源压缩为公开种子和经典旁信息后仍接近均匀的输出，误差由平均条件最小熵控制；条件化与 Jensen 不等式给出证明，三比特例子精确算出联合距离。属于弱源净化主线。