【随机性放大】

伪随机生成器具有一个非常重要的性质：它们是高效的随机性放大器（Amplifiers/Expanders of Randomness）。也就是说，伪随机生成器只需要使用很少的真正随机性，例如一个随机选择的种子，就能够产生很长的序列，并且这些序列在任何高效观察者看来都像是真正随机的。

如果一个伪随机生成器 $G$ 输入一个 $n$ 比特的随机种子 $s\leftarrow U_n$，然后输出一个多项式长度的字符串：

【引入】

在标准伪随机生成器中所定义的伪随机生成器是固定输出长度的，一旦生成器 $G$ 被确定，并且输入种子 $s$ 也被确定，那么该生成器输出的伪随机序列长度也就确定了。

换句话说，标准伪随机生成器具有一个预先给定的扩展因子 $l(n)$，当输入种子的长度为 $n$ 时，输出长度就是 $l(n)$。

【引入】

在标准伪随机生成器中，对扩展因子 $l(n)$ 的要求是很宽松的，只要求：

那么，如果一个伪随机生成器 $G$ 的扩展因子只有

【引入】

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

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

【引入】

在密码学中，伪随机性（Pseudorandomness）通常指的是相对于多项式时间算法的伪随机性。也就是说，所谓伪随机，并不是指统计意义上接近真正随机，而是指与均匀分布计算不可区分。

在计算不可区分性中，一个特殊但非常重要的情形是：两个概率系综中，有一个是均匀分布系综。

【引入】

计算不可区分性，是基于概率多项式时间算法来定义的，即如果不存在任何 PPT 区分器能够有效区分两个概率系综，就称它们是计算不可区分的。

考虑一个更强的不可区分性概念：多项式规模电路意义下的不可区分性（Indistinguishability by Polynomial-Size Circuits）。其不只考虑统一的多项式时间算法，而是允许对每个输入长度 $n$，都有一个专门设计的电路 $C_n$ 作为区分器。

【基本问题】

根据计算不可区分性的定义，两个概率系综 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$ 被认为是计算不可区分的，是指任何高效算法都无法根据单个样本区分它们。

也就是说，区分器只能拿到一个样本 $X_n$ 或 $Y_n$，然后判断这个样本来自哪个分布。但是在很多密码学应用中，敌手往往不止看到一个样本，而是可能看到多个独立样本。

【统计距离】

对于每个可能的字符串 $\alpha$，分别比较 $P[X_n=\alpha]$ 和 $P[Y_n=\alpha]$，两者的差值表示两个分布在字符串 $\alpha$ 上分配的概率相差多少，将所有可能字符串上的概率差取绝对值后相加，再乘以 $\frac12$，就得到两个分布之间的整体差异。

设两个概率系综分别为 $X=\{X_n\}_{n\in\mathbb N}$，$Y=\{Y_n\}_{n\in\mathbb N}$，对于每个安全参数 $n$，随机变量 $X_n$ 和 $Y_n$ 之间的统计距离（Statistical Distance）定义为：

【基本思想】

计算不可区分性（Computational Indistinguishability）是定义伪随机性的基础，它刻画的不是两个对象在数学上是否完全相同，而是任何高效算法能否发现它们之间的差异。

其基本思想是：如果不存在任何高效算法能够区分两个对象，那么对于一切能够由高效算法描述的实际用途，可以将这两个对象视为等价。

【基本概念】

伪随机生成器

伪随机生成器（Pseudorandom Generator，PRG）是一类高效的确定性程序，它能够将一个较短的、随机选取的种子（Seed）扩展为一个长度更长的伪随机序列（Pseudorandom Sequence）。