形式陈述

伪随机生成器是确定性多项式时间函数族

$$ G:\{0,1\}^n\to\{0,1\}^{\ell(n)},\qquad \ell(n)>n, $$$$G:\{0,1{\}}^n\to \{0,1{\}}^{\ell (n)},\ell (n)>n,$$

使均匀种子 $U_n$$U_n$ 的输出 $G(U_n)$$G(U_n)$ 与均匀分布 $U_{\ell(n)}$$U_{\ell (n)}$ 对任意概率多项式时间区分器都计算不可区分：其区分优势随安全参数 $n$$n$ 可忽略。$\ell(n)-n$$\ell (n)-n$ 称伸长量。由于输出支撑至多有 $2^n$$2^n$ 个点，它与真正均匀分布在统计上通常相距很远；安全性完全依赖计算受限观察者。

直觉

用一小段真正随机种子确定地产生更长串；输出不是“数学上随机”，而是任何高效测试都找不到可利用的偏差。

例子与边界

线性同余发生器可通过线性关系被高效区分，不是密码学 PRG。把一个安全 PRG 的前缀直接公开并不必然泄漏其余位，正式结论需由不可区分混合论证给出。固定或低熵种子不符合定义；即使算法本身正确，重复种子也会重复全部输出。伸长必须超过种子长度，否则恒等映射会使定义失去生成随机性的意义。

推论与应用

PRG 把少量随机位扩展到流密码、随机化算法去随机化和其他密码原语所需的伪随机性。它也是计算安全与信息论安全分界的典型对象。

参考资料

• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，Chs. 3–4, pseudorandom generators and indistinguishability。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Ch. 2, computational pseudorandomness and PRGs。