伪随机生成器的伸长放大

每轮把内部状态换成一个新状态，同时释放一位。单步安全保证告诉我们：从外部看来，这对“新状态、释放位”可以替换成独立均匀随机量。按时间从第一轮开始依次替换，就把所有释放位和最后状态都变成了独立公平随机量。

关键是每次替换前，目标轮所用的状态在当前混合中已经是新的均匀状态，而过去释放位与它独立。不能在一个未经分析的相关状态上，直接说“PRG 对任何输入都安全”。

三轮执行和四个混合 ​

运行三轮得到

输出 $z_1{z}_2{z}_3{s}_3$。定义混合 ${\mathcal{H}}_j$：前 $j$ 轮不运行 $G$，直接各抽独立均匀的新状态和释放位；后面 $3-j$ 轮照常运行。

${\mathcal{H}}_0$ 是真实构造。${\mathcal{H}}_3$ 则输出三个独立公平位和一个独立均匀状态，恰为 $U_{n+3}$。

比较 ${\mathcal{H}}_{j-1}$ 与 ${\mathcal{H}}_j$ 时，前 $j-1$ 轮已随机化，目标轮输入状态均匀且与已有释放位独立。一个收到 $n+1$ 位挑战 $w$ 的单步区分器，可把它拆成 $(s_j,z_j)$，自行生成前面的 $z_1,\dots ,z_{j-1}$，再从 $s_j$ 开始执行剩余真实轮次。挑战来自 $G(U_n)$ 时模拟前一混合，来自 $U_{n+1}$ 时模拟后一混合。

因此每步差异受单步 PRG 优势控制，相邻优势求和公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。给三轮最多 $3\epsilon$，一般 $t$ 轮最多 $t\epsilon$。多项式乘可忽略量仍可忽略。

在 uniform PPT 的渐近定义下，还要避免按每个 $n$ 非均匀地挑选一个“最容易区分”的轮次。固定最终输出判别器 $D$，令 $T=2^{\lceil {\log }_{2}t\rceil }<2t$，把混合补成 $T$ 步：超过 $t$ 的各步都保持全均匀世界不变。一个统一单步判别器用恰好 ${\log }_{2}T$ 个公平位均匀选取索引 $j$；若 $j\le t$，执行上一段的第 $j$ 步模拟；否则忽略挑战并生成全均匀输出交给 $D$。记 $p_j=\text{Pr}[D({\mathcal{H}}_j)=1]$，其两个挑战世界的接受概率之差为

因此若端点优势不可忽略，这一个统一 PPT 判别器的优势也不可忽略。该归约只需为固定 $D$ 取得其对应的可忽略界，无须假设存在一个同时支配所有判别器的全局可忽略函数。补成二的幂还避免了把无上限拒绝采样默认为严格有界的多项式时间步骤。

最终状态可以输出，为何内部状态不能一路公开 ​

式 (1) 把 $s_t$ 输出没有矛盾，因为其后没有再给出由 $s_t$ 决定的位。整体混合已经证明 $(z_1,\dots ,z_t,s_t)$ 不可区分于独立均匀串。

如果又继续公开下一位 $z_{t+1}=b(s_t)$，观察者便能从已经公开的 $s_t$ 自行计算 $G(s_t)$，检查它是否一致。真实分布总通过，独立均匀尾位仅以概率 $1/2$ 通过。公开状态与公开其未来输出的组合不是同一个保证。

同理，若每次都重复运行同一个初始种子 $s_0$ 并拼接 $G(s_0)$，前后块完全相同，很容易被区分。安全伸长依赖按证明规定更新状态，不是任意重复调用都安全。

成本如何增长 ​

假设单次 $G$ 时间为 $T_G(n)$，输出 $t$ 位释放串需要 $t{T}_G(n)$ 时间；流式实现的外层状态与计数共占 $O(n+\log (t+1))$ 位，另计 $G$ 本身的工作空间；若要一次性存全部输出，还需相应的输出缓存。

若想要长度 $m>n$，可以取 $t=m-n$ 使用式 (1)，得到恰好 $m$ 位。若接口不能把最终状态作为普通输出，则取 $t=m$ 并丢弃状态；两者都安全，却具有不同调用次数。选定哪一个接口后，证明和实现应使用同一个输出顺序。

把 $n\to n+1$ 生成器放大为 $n\to 2n$ 后，可以作为GGM 树构造公理库GGM 伪随机函数构造GGM construction沿长度倍增生成器的二叉树求值，以按需展开和逐层混合证明自适应查询安全，并核算触及节点而非指数全树的代价。的分支器，从短密钥得到可自适应查询的函数。伸长证明本身只讨论一个输出串，没有自动证明指数多次查询安全。

这个状态链也解释了流密码公理库流密码Stream cipher以密钥、nonce 与流位置解释异或加密，区分计算伪随机性、密钥流复用、同步和认证。为何必须区分密钥、nonce、流位置和内部状态泄漏。式 (1) 的单次均匀种子安全，并不附带多会话 nonce 规则、认证或泄露后恢复保证；那些属于更完整的协议接口。