标准伪随机生成器

【引入】

在均匀分布系综与伪随机系综中定义的伪随机系综有一个重要作用：在任何高效应用中，它都可以替代真正的均匀随机系综，并且性能最多只会有可忽略的下降。

原因是，如果某个高效应用在使用伪随机系综和使用均匀随机系综时表现差异明显，那么这个应用本身就可以被改造成一个高效区分器，从而区分伪随机系综和均匀系综。这就违背了伪随机的定义。

但是，这种替代只有在一个前提下才有意义：能够以比生成真正均匀随机系综更低的代价生成伪随机系综。

而生成一个概率系综的代价有很多方面，包括：

1. 时间复杂度（Time Complexity）：生成过程需要多少计算时间
2. 空间复杂度（Space Complexity）：生成过程需要多少存储空间
3. 随机源的数量和质量（Quantity and Quality of Random Source）：算法需要多少真正的随机性，以及这些随机性是否可靠

在随机算法中，真正的随机性通常是昂贵的。因此，很多应用希望用尽可能少的真正随机性，生成看起来像真正随机的输出，这就引出了伪随机生成器（Pseudorandom Generator, PRG）。

在伪随机生成器的基本概念中简单介绍过伪随机生成器与两类随机性，下面给出伪随机生成器的标准定义。

【标准定义】

定义

一个伪随机生成器是一个确定性的多项式时间算法 $G$，并且满足以下两个条件：

（1）扩展性（Expansion）：存在一个函数 $l : \mathbb{N} \to \mathbb{N}$，使得对所有 $n \in \mathbb{N}$，都有 $l(n) > n$，并且对任意输入串 $s \in \{0,1\}^{*}$，都有：

$$|G(s)| = l(|s|)$$

（2）伪随机性（Pseudorandomness）：由均匀随机种子产生的输出系综 $\{G(U_n)\}_{n \in \mathbb{N}}$ 是伪随机的。

其中，函数 $l$ 称为生成器 $G$ 的扩展因子（Expansion Factor），输入 $s$ 称为生成器 $G$ 的种子（Seed）。

直观理解

伪随机生成器本质上要同时满足两个条件：

1. 短输入变成长输出：输入的种子 $s$ 长度为 $n$，输出 $G(s)$ 长度为 $l(n)$，并且输出长度 $l(n)$ 必须严格大于输入长度 $n$
2. 输出看起来像真随机：虽然 $G$ 是一个确定性算法，但如果种子 $s$ 是均匀随机选择的，那么输出 $G(s)$ 应该让任何多项式时间算法都无法有效地区分它和真正的 $l(n)$ 比特均匀随机串

因此，伪随机生成器的核心思想可以概括为：用少量真正随机比特作为种子，通过确定性算法生成更多比特，使得这些输出在计算上看起来像真正随机。

【伪随机性与统计接近】

伪随机生成器的输出分布虽然在计算上不可区分于均匀分布，但它并不在统计意义上接近均匀分布。

这是由于，输入种子只有 $n$ 比特，所以最多只有 $2^n$ 种可能的种子，因此，生成器 $G$ 最多只能产生 $2^n$ 种不同的输出。

但是，真正的 $l(n)$ 比特均匀分布 $U_{l(n)}$ 的取值空间大小是 $2^{l(n)}$，由于 $l(n)>n$，所以：

$$2^{l(n)} > 2^n$$

这说明，$G(U_n)$ 的输出只落在所有 $l(n)$ 比特串中的一个很小子集里，而真正的均匀分布 $U_{l(n)}$ 会在所有 $2^{l(n)}$ 个字符串上均匀取值。

因此，从统计意义上看，$G(U_n)$ 和 $U_{l(n)}$ 的分布差异是明显的，但从计算意义上看，如果 $G$ 是伪随机生成器，那么任何概率多项式时间算法都无法有效发现这种差异。

这正体现了伪随机性的核心思想：伪随机生成器的输出不是真的均匀随机，但它在任何高效观察者看来与均匀随机没有区别。

【统计距离的下界】

设生成器 $G$ 所有可能输出构成的集合为：

$$S = \{G(s) : s \in \{0,1\}^n\}$$

因为 $G(U_n)$ 一定落在集合 $S$ 中，所以：

$$P[G(U_n) \in S] = 1$$

而对于真正的均匀分布 $U_{l(n)}$，它落入 $S$ 的概率最多是：

$$P[U_{l(n)} \in S] \leq \frac{2^n}{2^{l(n)}} = 2^{-(l(n)-n)}$$

所以 $G(U_n)$ 和 $U_{l(n)}$ 的统计距离至少为：

$$\begin{align*} \frac{1}{2}\sum_x \left| P[U_{l(n)}=x]-P[G(U_n)=x] \right| &= \max_S \left\{ P[U_{l(n)} \in S] - P[G(U_n) \in S]\right\} \\ &\geq 1 - 2^{-(l(n)-n)} \\ &\geq \frac{1}{2} \end{align*}$$

这说明两者的统计距离至少是 $\frac{1}{2}$。其中，由于 $l(n) \geq n+1$，因此 $1 - 2^{-(l(n)-n)} \geq \frac{1}{2}$。

进一步，如果扩展因子满足：

$$l(n) \geq 2n$$

那么统计距离至少为：

$$1 - 2^{-n}$$

这已经非常接近 1，说明二者在统计意义上相距很远。

【扩展因子的要求】

上述定义中，对扩展因子 $l(n)$ 的要求是很宽松的。它只要求：

$$l(n) \geq n+1$$

并且由于 $G$ 是多项式时间算法，所以输出长度不能超过多项式级别，即：

$$l(n) \leq \operatorname{poly}(n)$$

此外，$l(n)$ 本身也可以在多项式时间内计算。

但是，如果一个伪随机生成器的扩展因子只是 $l(n) = n+1$，那么它在实际中价值并不大，因为它只多生成了 1 个比特，几乎没有节省随机投掷的数量。

虽然 $l(n)=n+1$ 的扩展看起来很弱，但它在理论上已经足够重要。在伪随机生成器的扩展因子中证明了即使只存在这种扩展 1 比特的伪随机生成器，也可以构造出具有任意多项式扩展长度的伪随机生成器。

也就是说，对于任意两个可以在多项式时间内计算的扩展因子 $l_1(n), l_2(n)$，只要存在一个扩展因子为 $l_1$ 的伪随机生成器，就存在一个扩展因子为 $l_2$ 的伪随机生成器。

更具体地说，只要有一个满足：

$$l_1(n) = n+1$$

的伪随机生成器，就可以对任意多项式 $\mathrm{poly}(\cdot)$，构造出一个扩展因子为 $\mathrm{poly}(\cdot)$ 的伪随机生成器。