【基本思想】

基于单向置换的伪随机生成器构造与基于置换集合的伪随机生成器构造中的伪随机生成器的构造均基于硬核谓词，硬核谓词的输出长度为 $1$ 比特，因此每进行一次单向置换 $f_i$，只能产生一个伪随机比特。

将该思想推广到硬核函数上，即不再要求 $H(x)\in\{0,1\}$，而允许 $H(x)\in\{0,1\}^{m},m>1$。此时，每执行一次单向置换，可以输出多个伪随机比特。

【基本思想】

基于置换集合的伪随机生成器构造，是在基于单向置换的伪随机生成器的基础上的推广，其不再使用固定的单个置换 $f$，而是从一个单向置换集合（Collection of One-way Permutations）中随机选择一个置换，然后进行迭代。

这种构造可以直接应用于多个经典密码学假设，例如：

【基本思想】

基于单向置换构造伪随机生成器的方法有两种等价的构造方式：

1. 间接构造：构造一个简单的伪随机生成器 $\{0,1\}^{n}\rightarrow \{0,1\}^{n+1}$，将长度为 $n$ 的随机种子扩展为长度为 $n+1$ 的伪随机串。然后结合标准伪随机生成器的扩展因子中的构造方法，将其扩展为任意多项式长度 $\mathrm{poly}(n)$ 比特的字符串。
2. 直接构造：将间接构造的构造过程展开，直接构造一个能够输出任意多项式长度伪随机序列的生成器。这种展开后的构造不仅本身具有意义，同时也是后续基于单向置换集合构造伪随机生成器的基础。

【单向函数存在性命题】

在讨论伪随机性时，一直假设伪随机生成器的存在，并研究其具有的性质。但是，一个自然的问题是：伪随机生成器是否真的存在？

在密码学中，伪随机生成器的存在性与单向函数密切相关，具体来说，伪随机生成器存在的充分必要条件是单向函数存在，二者在计算复杂性意义下是等价的。

【引入】

伪随机序列在密码学应用中有一个非常重要的性质：不可预测性（Unpredictability）。

直观来说，一个序列是不可预测的，即代表任何高效算法即使已经看到了这个序列的前面若干位，也无法以明显高于随机猜测的概率预测下一位。

【随机性放大】

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

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

【引入】

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

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

【引入】

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

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

【引入】

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

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

【引入】

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

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