Alex_McAvoy

想要成为渔夫的猎手

标准伪随机生成器的扩展因子

发表于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

【引入】

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

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

即只能把一个 $n$ 比特的随机种子扩展成 $n+1$ 比特的字符串，只多产生 $1$ 个比特。

从实际角度看，这种扩展非常弱，因为它几乎没有节省多少真正随机性。但从理论角度看，这已经足够了。只要存在一个能扩展 1 比特的伪随机生成器，就可以构造出具有任意多项式扩展长度的伪随机生成器。

这一节的目标就是证明：如果存在一个扩展因子为 $l(n)=n+1$ 的伪随机生成器 $G_1$，那么对任意多项式 $\mathrm{poly}(\cdot)$，都可以构造一个把 $n$ 比特种子扩展成 $\mathrm{poly}(n)$ 比特输出的伪随机生成器 $G$。

【扩展因子的构造】

构造

Construction：设 $G_1$ 是一个确定性的多项式时间算法，它把长度为 $n$ 的字符串映射为长度为 $n+1$ 的字符串：

又设 $\mathrm{poly}(\cdot)$ 是一个多项式，定义新的生成器 $G$，给定输入种子 $s$，令 $s_0=s$，并记 $n=|s|$，然后重复执行 $\mathrm{poly}(n)$ 次。在第 $i$ 次迭代中，对当前种子 $s_{i-1}$ 应用 $G_1$，得到一个长度为 $n+1$ 的字符串：

其中，$\sigma_i \in \{0,1\}$ 是输出的第一个比特，而 $s_i$ 是剩下的 $n$ 比特后缀。也就是说，$\sigma_i$ 被作为最终输出的一部分，而 $s_i$ 被作为下一轮迭代的新种子。

最终，新的生成器 $G$ 输出所有额外比特的连接，即：

因此，$G$ 把一个 $n$ 比特的种子扩展成了 $\mathrm{poly}(n)$ 比特的字符串。

直观理解

上述构造可以理解为反复使用 $G_1$，具体构造如下图所示。

在每一次使用 $G_1$ 时：

  1. 输入当前的 $n$ 比特种子 $s_{i-1}$
  2. 得到一个 $n+1$ 比特的输出
  3. 把第一个比特 $\sigma_i$ 拿出来作为最终输出
  4. 把剩下的 $n$ 比特 $s_i$ 留作下一轮的新种子

也就是说，$G_1$ 每运行一次，就得到一个额外比特，同时更新种子，经过 $\mathrm{poly}(n)$ 次迭代后，就可以得到 $\mathrm{poly}(n)$ 个输出比特。

此外，由于 $\mathrm{poly}(n)$ 是多项式，并且 $G_1$ 是多项式时间算法，所以新构造的 $G$ 仍然是多项式时间算法。

【扩展因子正确性定理】

Theorem：设 $G_1$、$\mathrm{poly}(\cdot)$ 和 $G$ 如上述构造所定义，并且满足：

若 $G_1$ 是一个伪随机生成器，则 $G$ 也是一个伪随机生成器。

该定理说明，只要 $G_1$ 能安全地把 $n$ 比特扩展成 $n+1$ 比特，那么通过重复调用 $G_1$，就可以安全地把 $n$ 比特扩展成任意多项式长度 $\mathrm{poly}(n)$。

直观上看，$G$ 的伪随机性来自 $G_1$ 的伪随机性。如果 $G_1(U_n)$ 和真正的均匀分布 $U_{n+1}$ 在多项式时间内不可区分，那么一次调用 $G_1$ 的结果就可以被看成伪随机的。

而现在 $G$ 只是把 $G_1$ 调用了多项式次，因此可以直观地认为：

  1. 一次调用 $G_1$ 和一次真正随机过程不可区分
  2. 多项式次调用 $G_1$ 和多项式次真正随机过程也应该不可区分
  3. 所以 $G$ 的整个输出应该和真正的 $\mathrm{poly}(n)$ 比特均匀随机串不可区分

【定理证明】

证明思路

上述定理只需要证明 $G$ 是伪随机生成器，采用反证法。

假设 $G$ 不是伪随机生成器。那么，存在一个概率多项式时间算法 $D$，能够区分 $G(U_n)$ 和真正的均匀分布 $U_{\mathrm{poly}(n)}$。也就是说，存在某个多项式 $\mathrm{poly}(\cdot)$，使得对无穷多个 $n$，区分器 $D$ 的区分优势：

如果能从这个 $D$ 构造出另一个多项式时间算法 $D’$，使得 $D’$ 能够区分 $G_1(U_n)$ 和 $U_{n+1}$，那么就与 $G_1$ 是伪随机生成器这一假设矛盾。

因此，证明的核心任务是：根据区分 $G(U_n)$ 和 $U_{\mathrm{poly}(n)}$ 的算法 $D$，构造出区分 $G_1(U_n)$ 和 $U_{n+1}$ 的算法 $D’$。

证明

混合分布

定义混合分布 $H_n^0,H_n^1,\ldots,H_n^{\mathrm{poly}(n)}$，对于每个 $0\leq k\leq \mathrm{poly}(n)$，定义：

其中：

  • $U_k^{(1)}$ 是一个均匀随机的 $k$ 比特字符串，$U_n^{(2)}$ 是一个均匀随机的 $n$ 比特字符串，二者相互独立
  • $\operatorname{pref}_j(\alpha)$ 是字符串 $\alpha$ 位长为 $j$ 的前缀，即 $\alpha$ 的前 $j$ 个比特
  • $x\cdot y$ 表示字符串 $x$ 和 $y$ 的连接

因此，$H_n^k$ 的含义是：前 $k$ 个比特是真正随机的，后面 $\mathrm{poly}(n)-k$ 个比特来自 $G(U_n)$ 的前缀。

也可以从构造过程本身来理解 $H_n^k$。在构造过程中，生成器 $G$ 是从初始种子 $s_0=s$ 出发，不断调用 $G_1$，依次得到：

其中，$\sigma_i$ 是第 $i$ 轮输出的额外比特，$s_i$ 是下一轮使用的新种子。

而在混合分布 $H_n^k$ 中，前 $k$ 个输出比特 $\sigma_1\cdots\sigma_k\in\{0,1\}^k$ 直接从 $\{0,1\}^n$ 中均匀随机选取，同时第 $k$ 轮后使用的种子 $s_k$ 也直接从 $\{0,1\}^n$ 中均匀随机选取，并且从第 $k+1$ 轮开始，继续按照原来的构造运行 $G_1$，即对于：

仍然令：

最后输出：

因此，$H_n^k$ 也可以理解为：前 $k$ 个比特是真正随机的，从第 $k+1$ 个比特开始，则由生成器 $G$ 从一个新的均匀随机种子 $s_k$ 继续生成。

上述过程如下图所示。

特别地，当 $k=0$ 时，有：

此时没有任何比特被替换为真正随机比特，所以整个输出都来自生成器 $G$。

当 $k=\mathrm{poly}(n)$ 时，有：

此时所有 $\mathrm{poly}(n)$ 个比特都是真正均匀随机的。

所以，这组混合分布把两个端点连接起来，即有：

这正是混合技术的基本思路：如果区分器 $D$ 能够区分两个端点分布 $H_n^{0}$ 和 $H_n^{\mathrm{poly}(n)}$，那么一定能够区分某一对相邻的混合分布 $H_n^k$ 和 $H_n^{k+1}$。

相邻混合分布

直观含义

混合分布 $H_n^k$ 和 $H_n^{k+1}$ 之间只差一个位置。

在 $H_n^k$ 中，前 $k$ 个比特是真随机的，从第 $k+1$ 个比特开始仍然由生成器 $G$ 产生；而在 $H_n^{k+1}$ 中，前 $k+1$ 个比特都是真随机的，从第 $k+2$ 个比特开始再由生成器继续产生。

因此，从 $H_n^k$ 到 $H_n^{k+1}$ 的变化，本质上就是把一次 $G_1$ 的输出 $G_1(U_n)$ 替换成真正的均匀随机串 $U_{n+1}$。

所以，如果区分器 $D$ 能够察觉这种替换，那么就可以利用 $D$ 构造出一个新的区分器 $D’$，从而区分 $G_1(U_n)$ 和 $U_{n+1}$。

前缀后缀记号

为了严格描述相邻混合分布的关系，引入记号 $\operatorname{pref}_j(\alpha)$ 表示字符串 $\alpha$ 的前 $j$ 个比特，$\operatorname{suff}_j(\alpha)$ 表示字符串 $\alpha$ 的后 $j$ 个比特。

对于任意 $x\in\{0,1\}^n$，设：

其中，$\sigma=\operatorname{pref}_1(G_1(x))$ 是 $G_1(x)$ 的第一个比特，$y=\operatorname{suff}_n(G_1(x))$ 是 $G_1(x)$ 的后 $n$ 个比特。

那么根据 $G$​ 的构造，$G_1(x)$ 的第一个比特 $\sigma$ 会作为当前输出比特，而后 $n$ 个比特 $y$ 会作为下一轮种子继续运行，故有：

也就是：

更一般地，对于任意 $j\geq 0$，有：

也就是对于 $G(x)$ 的前 $j+1$ 个比特，可以分成两部分：一部分是调用 $G_1(x)$ 得到的第一个比特，另一部分是把 $G_1(x)$ 的后 $n$ 比特作为新种子后，继续运行 $G$ 得到的前 $j$ 个比特。

记号表示

在前缀记号与后缀记号的基础上，对于 $0\leq k\leq \mathrm{poly}(n)-1$，对相邻混合分布 $H_n^k$ 和 $H_n^{k+1}$ 进行形式化展开。

根据混合分布的定义，有：

由于 $\mathrm{poly}(n)-k=(\mathrm{poly}(n)-k-1)+1$，因此上式可以写为：

进一步，根据 $G$ 的构造，$G(U_n^{(2)})$ 的第一个输出比特来自 $G_1(U_n^{(2)})$ 的第一位，而之后的输出来自 $G_1(U_n^{(2)})$ 的后 $n$ 比特继续作为新种子，故有：

其中，$\equiv$ 表示两个随机变量具有相同分布。

类似地，对于 $H_n^{k+1}$​，根据定义，有：

由于 $U_{k+1}^{(1)}$ 可以看成前 $k$ 个随机比特加上第 $k+1$ 个随机比特，而一个均匀的 $(n+1)$ 比特串 $U_{n+1}^{(3)}$ 可以分成第一位和后 $n$ 位，因此可以等价写为：

由此可以看出，$H_n^k$ 和 $H_n^{k+1}$ 的结构几乎完全相同，它们的区别只在于：

  • $H_n^k$ 中间嵌入的是 $G_1(U_n^{(2)})$
  • $H_n^{k+1}$ 中间嵌入的是 $U_{n+1}^{(3)}$

也就是说，从 $H_n^k$ 到 $H_n^{k+1}$，本质上就是把一次调用 $G_1$ 的输出替换成真正均匀随机的 $(n+1)$ 比特串。

区分器 $D’$ 的构造

辅助函数

为把相邻混合分布和 $G_1$ 的输出联系起来，定义辅助函数：

其中，$\alpha \in \{0,1\}^{n+1}$。该函数模拟了从第 $k+1$ 个位置开始继续生成的过程，即把输入 $\alpha$ 的第一个比特作为当前输出比特，并把 $\alpha$ 的后 $n$ 个比特作为新种子，继续运行 $G$。

因此，其值域为：

断言

Claim：对于每个 $k\in\{0,1,\ldots,\mathrm{poly}(n)-1\}$，有：

  1. $H_n^k$ 与分布 $U_k^{(1)}\cdot f_{\mathrm{poly}(n)-k}(G_1(U_n^{(2)}))$ 相同
  2. $H_n^{k+1}$ 与分布 $U_k^{(1)} \cdot f_{\mathrm{poly}(n)-k}(U_{n+1}^{(3)})$ 相同

证明：

先证明第一个结论。

由混合分布的定义：

再由前缀分解式，令 $j=\mathrm{poly}(n)-k-1$，可得：

因此：

进一步，根据辅助函数 $f_{\mathrm{poly}(n)-k}$ 的定义，有：

再证明第二个结论。

根据混合分布的定义，有：

其中，$U_{k+1}^{(1)}$ 可以分解为：

而一个均匀的 $(n+1)$ 比特随机串 $U_{n+1}^{(3)}$ 可以分解为：

其中，$\operatorname{pref}_1(U_{n+1}^{(3)})$ 是均匀随机的 1 比特，$\operatorname{suff}_n(U_{n+1}^{(3)})$ 是均匀随机的 $n$ 比特字符串，且二者相互独立。

故有：

根据辅助函数的定义，有：

综上，断言成立。

构造过程

由上面的断言可知，只要能够区分 $H_n^k$ 和 $H_n^{k+1}$，就能够区分 $G_1(U_n)$ 和 $U_{n+1}$。

下面构造新的概率多项式时间算法 $D’$。

算法 $D’$ 的输入是 $\alpha\in\{0,1\}^{n+1}$，它不知道 $\alpha$ 来自 $G_1(U_n)$，还是真正的均匀分布 $U_{n+1}$。

算法 $D’$ 的运行过程如下：

  1. 均匀随机选择一个整数 $k\in\{0,1,\ldots,\mathrm{poly}(n)-1\}$
  2. 均匀随机选择一个 $k$ 比特字符串 $\beta\in\{0,1\}^k$
  3. 计算 $f_{\mathrm{poly}(n)-k}(\alpha)$
  4. 将 $\beta$ 拼接在前面，得到 $\beta\cdot f_{\mathrm{poly}(n)-k}(\alpha)$
  5. 将该字符串输入给区分器 $D$，并输出 $D$ 的结果：

由于 $k$、$\beta$ 的选择可以在多项式时间内完成，辅助函数 $f_{\mathrm{poly}(n)-k}$ 只涉及运行 $G$ 和简单的字符串操作，而 $G$ 和 $D$ 都是多项式时间算法，所以 $D’$ 也是一个概率多项式时间算法。

这个构造的直观含义是，$D’$ 把自己的输入 $\alpha$ 嵌入到第 $k+1$ 个位置对应的那一次生成过程中，然后让 $D$ 去判断整个输出像不像真正随机：

  • 如果 $\alpha=G_1(U_n)$，那么 $D$ 看到的是类似 $H_n^k$ 的分布
  • 如果 $\alpha=U_{n+1}$，那么 $D$ 看到的是类似 $H_n^{k+1}$ 的分布。

因此，$D’$ 可以利用 $D$ 对相邻混合分布的区分能力，来区分 $G_1(U_n)$ 和 $U_{n+1}$。

此外，由于随机选择 $k$ 和 $\beta$ 可以在多项式时间内完成，$f_{\mathrm{poly}(n)-k}$ 的计算只需要调用 $G$ 和进行字符串操作。而 $G$ 本身由多项式次调用 $G_1$ 构成，$G_1$ 是多项式时间算法，且 $D$ 也是多项式时间算法。因此，$D’$ 是概率多项式时间算法。

区分器 $D’$ 的区分优势

断言

Claim：

（1）当 $D’$ 的输入来自 $G_1(U_n)$ 时，其接受概率为：

（2）当 $D’$ 的输入来自 $U_{n+1}$ 时，其接受概率为：

该断言说明：

  • 当 $D’$ 的输入来自 $G_1(U_n)$ 时，它随机选择 $k$，于是平均来看，$D$ 看到的是所有 $H_n^k$ 的平均效果
  • 当 $D’$ 的输入来自 $U_{n+1}$ 时，它随机选择 $k$，于是平均来看，$D$ 看到的是所有 $H_n^{k+1}$ 的平均效果

证明：

根据区分器 $D’$ 的构造，对于任意输入 $\alpha\in\{0,1\}^{n+1}$，算法 $D’$ 会先均匀随机选择 $k\in\{0,1,\ldots,\mathrm{poly}(n)-1\}$，再均匀随机选择 $U_k\in\{0,1\}^k$，最后输出：

因此，对任意 $\alpha$，有：

当 $\alpha=G_1(U_n)$ 时，由区分器 $D’$ 的构造断言可知：

所以：

当 $\alpha=U_{n+1}$ 时，由区分器 $D’$ 的构造断言可知：

所以：

区分优势计算

令 $d_k(n)$ 表示区分器 $D$ 在输入来自混合分布 $H_n^k$ 时输出 $1$ 的概率，即：

由混合分布端点可知 $H_n^0=G(U_n),H_n^{\mathrm{poly}(n)}=U_{\mathrm{poly}(n)}$，因此：

根据反证假设，区分器 $D$ 能够区分 $G(U_n)$ 和 $U_{\mathrm{poly}(n)}$​，其区分优势为：

根据区分器 $D’$​ 的接受概率断言，有：

因此，$D’$ 对 $G_1(U_n)$ 和 $U_{n+1}$ 的区分优势为：

注意到上式中的两个级数：

两式相减时，中间项抵消只剩下端点项：

故有：

即区分器 $D’$ 的区分优势等于原区分器 $D$ 的区分优势 $\Delta(n)$ 除以混合分布的个数 $\mathrm{poly}(n)$。

矛盾推出

根据反证假设，$G$ 不是伪随机生成器，因此存在概率多项式时间区分器 $D$，使得对某个多项式 $\mathrm{poly}’(n)$，与无穷多个 $n$，有：

根据区分优势计算可知：

因此，对无穷多个 $n$，有：

由于两个多项式的乘积仍然是多项式，所以 $\frac{1}{\mathrm{poly}(n)\cdot \mathrm{poly}’(n)}$ 仍然是一个不可忽略量，这说明 $D’$ 能够以不可忽略优势区分 $G_1(U_n)$ 和 $U_{n+1}$。

也就是说，$G_1(U_n)$ 和 $U_{n+1}$ 不是多项式时间不可区分的，但是这与 $G_1$ 是伪随机生成器的假设矛盾。因为如果 $G_1$ 是伪随机生成器，那么按照定义，输出分布 $G_1(U_n)$ 必须与真正的均匀分布 $U_{n+1}$ 在多项式时间内不可区分。

因此，反证假设不成立，$G$ 必须是伪随机生成器。

感谢您对我的支持，让我继续努力分享有用的技术与知识点！