【引入】
在标准伪随机生成器中所定义的伪随机生成器是固定输出长度的，一旦生成器 $G$ 被确定，并且输入种子 $s$ 也被确定，那么该生成器输出的伪随机序列长度也就确定了。
换句话说，标准伪随机生成器具有一个预先给定的扩展因子 $l(n)$，当输入种子的长度为 $n$ 时，输出长度就是 $l(n)$。
但是，在很多应用中，我们希望生成器更加灵活：不是一开始就固定输出长度，而是可以根据需要即时生成任意长度的伪随机序列，这就需要可变输出伪随机生成器（Variable-Output Pseudorandom Generator）。
【基本思想】
可变输出伪随机生成器的目标是：对于任意固定种子 $s$，定义一个无限长的比特序列，并且可以按需输出这个无限序列的任意有限前缀。
也就是说，给定种子 $s$ 后，生成器实际上隐含地确定了一个无限序列 $b_1b_2b_3\cdots$，当输入长度参数 $t$ 时，生成器输出该无限序列的前 $t$ 个比特 $b_1b_2\cdots b_t$。
这个需要满足两个要求：
- 可高效生成任意前缀：对于任意给定的种子 $s$ 和长度 $t$，都可以在关于种子长度和前缀长度的多项式时间内生成长度为 $t$ 的输出
- 任意多项式长度前缀都是伪随机的：如果种子是均匀随机选取的 $n$ 比特串，那么对任意多项式长度 $p(n)$，输出序列的前 $p(n)$ 个比特都应该是伪随机的
也就是说，虽然生成器可以定义无限长的输出序列，但密码学意义上只要求它的任意多项式长度前缀与真正均匀随机串不可区分。
【可变输出伪随机生成器】
定义
一个可变输出伪随机生成器是一个确定性的多项式时间算法 $G$，并且满足以下两个条件：
- 可变输出性：对于任意 $s\in\{0,1\}^{*}$ 和任意 $t\in\mathbb{N}$，都有 $|G(s,1^t)|=t$ 且 $G(s,1^t)$ 是 $G(s,1^{t+1})$ 的前缀，其中 $1^t$ 是长度为 $t$ 的一元表示，用来告诉生成器需要输出多少个比特
- 伪随机性：对于任意多项式 $\mathrm{poly}(\cdot)$，系综 $\{G(U_n,1^{\mathrm{poly}(n)})\}_{n\in\mathbb{N}}$ 都是伪随机的，其中 $U_n$ 表示均匀随机选择的 $n$ 比特种子
对于可变输出性来说，包含两层意思：
- 当输入 $(s,1^t)$ 时，生成器输出长度恰好为 $t$ 的字符串
- 当输出长度从 $t$ 增加到 $t+1$ 时，前 $t$ 个比特不会改变
因此，对于同一个种子 $s$，不同长度的输出必须彼此兼容，长度为 $t$ 的输出应该是长度为 $t+1$ 的输出的前缀。这保证了 $G$ 真正定义了一条由种子 $s$ 决定的无限比特序列。
对于伪随机性来说，其含义是：当种子 $s$ 从 $\{0,1\}^n$ 中均匀随机选取时，生成器输出的前 $\mathrm{poly}(n)$ 个比特 $G(U_n,1^{\mathrm{poly}(n)})$ 应该与真正的均匀随机分布 $U_{\mathrm{poly}(n)}$ 在多项式时间内不可区分。
也就是说，对任意多项式长度的前缀，都要求它是伪随机的。
与标准伪随机生成器的区别
标准伪随机生成器与可变输出伪随机生成器的区别在于输出长度是否固定。
标准伪随机生成器通常写作 $G(s)$，如果输入种子长度为 $n$，那么输出长度由扩展因子 $l(n)$ 预先决定：
因此，一旦 $G$ 和 $s$ 确定，输出长度也确定。
可变输出伪随机生成器通常写作 $G(s,1^t)$，其中 $t$ 是预先指定的输出长度。对于同一个种子 $s$，可以根据需要生成：
并且这些输出之间满足前缀一致性：
其中，$\preceq$ 表示偏序关系，在这里表示前者是后者的前缀。
因此，可变输出伪随机生成器可以看作是用一个短种子定义了一条无限长的伪随机序列，然后根据需要输出任意长度的前缀。
前缀一致性
可变输出伪随机生成器的定义中要求：$G(s,1^t)$ 是 $G(s,1^{t+1})$ 的前缀。
如果没有这个条件，那么 $G(s,1^t)$ 和 $G(s,1^{t+1})$ 可能是两段完全不一致的输出，这样就不能说生成器定义了一条可延长的伪随机序列。
因此，这种前缀一致性保证了先生成 $t$ 个比特，之后如果需要更多比特，可以继续延长，而不是重新生成一条完全不同的序列。
因此，可变输出伪随机生成器更像一个可以不断往外输出比特的伪随机流。
【存在性定理】
定理
Theorem：如果标准伪随机生成器存在，那么可变输出伪随机生成器也存在。
这个定理说明，可变输出伪随机生成器并不是比标准伪随机生成器更强的额外假设，只要存在普通的伪随机生成器，就可以构造出可变输出伪随机生成器。
证明
证明思路
该定理的证明思路与伪随机生成器的扩展因子中扩展因子的构造基本相同，其核心证明思想是：先从任意标准伪随机生成器得到一个只扩展 $1$ 比特的伪随机生成器 $G_1$，然后不断迭代调用 $G_1$，每次输出一个额外比特，并把剩下的 $n$ 比特作为新的内部状态继续生成。
构造
由于假设标准伪随机生成器存在，可以不失一般性地取一个扩展因子为 $l(n)=n+1$ 的伪随机生成器 $G_1:\{0,1\}^n\to \{0,1\}^{n+1}$。也就是说，对于任意长度为 $n$ 的输入 $s$，有：
现在构造可变输出伪随机生成器 $G$，给定输入 $(s,1^t)$，其中 $s\in\{0,1\}^{*},t\in\mathbb{N}$。令 $s_0=s, n=|s|$，然后迭代调用 $G_1$，对于每个 $i=1,2,\ldots,t$，计算：
其中，$\sigma_i\in\{0,1\}$ 是 $G_1(s_{i-1})$ 的第一个比特，$s_i$ 是 $G_1(s_{i-1})$ 的后 $n$ 个比特。
最后定义：
也就是说，$G(s,1^t)$ 输出由前 $t$ 次迭代得到的额外比特。
那么，只需要证明 $G$ 满足可变输出性与伪随机性即可证明定理。
可变输出性
根据构造，$G(s,1^t)$ 正好由 $\sigma_1,\sigma_2,\ldots,\sigma_t$ 这 $t$ 个比特组成，因此：
同时，如果输入变为 $(s,1^{t+1})$，那么生成器会继续多运行一轮，得到：
显然，$G(s,1^t)=\sigma_1\sigma_2\cdots\sigma_t$ 是 $G(s,1^{t+1})=\sigma_1\sigma_2\cdots\sigma_t\sigma_{t+1}$ 的前缀，因此 $G$ 满足定义中的可变输出性。
此外，计算 $G(s,1^t)$ 只需要调用 $G_1$ 共 $t$ 次，由于 $G_1$ 是多项式时间算法，所以 $G(s,1^t)$ 可以在关于 $|s|$ 和 $t$ 的多项式时间内计算。因此，$G$ 是确定性的多项式时间算法。
伪随机性
按照可变输出伪随机生成器的定义，需要证明：对于任意多项式 $\mathrm{poly}(\cdot)$，系综 $\{G(U_n,1^{\mathrm{poly}(n)})\}_{n\in\mathbb{N}}$ 是伪随机的。
根据 $G$ 的构造，$G(U_n,1^{\mathrm{poly}(n)})$ 是从随机种子 $U_n$ 出发，反复调用 $G_1$ 共 $\mathrm{poly}(n)$ 次，并输出每次得到的额外比特：
这与伪随机生成器的扩展因子中扩展因子的构造完全相同，只不过那里的输出长度固定为某个多项式 $\mathrm{poly}(n)$。
根据扩展因子正确性定理可知，如果 $G_1$ 是伪随机生成器，那么由这种迭代方式构造出的长度为 $\mathrm{poly}(n)$ 的输出分布 $G(U_n,1^{\mathrm{poly}(n)})$ 与真正均匀分布 $U_{\mathrm{poly}(n)}$ 在多项式时间内不可区分。
因此，$\{G(U_n,1^{\mathrm{poly}(n)})\}_{n\in\mathbb{N}}$ 是伪随机系综。
同时，由于 $\mathrm{poly}(\cdot)$ 是任意多项式，所以 $G$ 的任意多项式长度前缀都是伪随机的。
结论推出
综上，构造出的算法 $G$ 同时满足：
- 对任意 $s$ 和 $t$，输出 $G(s,1^t)$ 的长度为 $t$，且 $G(s,1^t)$ 是 $G(s,1^{t+1})$ 的前缀
- 对任意多项式 $p(\cdot)$，系综 $\{G(U_n,1^{\mathrm{poly}(n)})\}_{n\in\mathbb{N}}$ 都是伪随机的
因此，$G$ 是一个可变输出伪随机生成器。
所以，如果标准伪随机生成器存在，那么可变输出伪随机生成器也存在。
