GGM 伪随机函数构造

把密钥看成二叉树根上的状态。向左走就取 $G_0$，向右走就取 $G_1$；一个长度 $d$ 的输入是一条根到叶的路线，叶上 $n$ 位标签就是函数值。

整棵树确有 $2^d$ 个叶子，但求一个函数值无需生成它们。对手提出少量问题时，也只接触到少量路线。安全证明必须保留路线共享：输入相同、甚至只有前缀相同，都不能被误当成完全重新采样的独立执行。

用一棵小树核对求值顺序 ​

以下二位状态只演示执行，不作为安全生成器。把状态视为 $0,1,2,3$，取

根密钥取 $k=1$。输入 $001$ 的路径为

故输出二进制 $01$。输入 $011$ 的路径为

故输出 $10$。再次查询 $001$ 仍返回 $01$。两条路线共享状态 $G_0(k)$，不是每遇到同一个前缀就换一份独立种子。

这种小型代数规则很容易被区分；GGM 的安全结论依赖输入的 $G$ 真正满足 PRG 定义，不是任何能输出两倍长度的程序都可以。

逐层混合如何连接到随机函数 ​

构造 ${\mathcal{H}}_j$，$j=0,\dots ,d$：把深度 $j$ 的各个前缀节点赋予彼此独立的均匀 $n$ 位标签，其下仍按式 (1) 使用真实 $G$ 延伸。对同一个节点，标签只采样一次。

${\mathcal{H}}_0$ 只有一个均匀根，恰是真实 GGM。${\mathcal{H}}_d$ 给每个不同长度 $d$ 的输入一个独立均匀标签，并缓存重复查询，恰为随机函数。

从第 $j$ 层移到第 $j+1$ 层时，每个被访问父节点的两个子标签从 $G(U_n)$ 改成独立的 $U_{2n}$。父标签本身没有作为函数回答交给对手；它处在当前混合中均匀、隐藏的那一层。因而可把一个 PRG 挑战嵌在该节点，其他节点自行模拟，子树继续使用已知标签按需求值。

最多 $q$ 个不同查询，所以在任何固定深度，最多首次触及 $q$ 个父节点。按首次触及的次序替换它们，而不是按最终查询列表预先猜好节点；这样即使对手后一个输入依赖前一答案，模拟仍能在线进行。若不足 $q$ 个节点，剩余替换步骤为空，不影响预算。

每层至多 $q$ 次单步替换、共 $d$ 层。由混合优势累加公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。，在每一步都受同一具体资源界 ${\epsilon }_G$ 控制时，端点优势至多为 $qd{\epsilon }_G$。对单个长度，也存在某一步至少承接端点优势的 $1/(qd)$。

统一 PPT 的渐近证明不能免费硬连一个随 $n$ 变化的最佳步骤。令 $T=2^{\lceil {\log }_2(qd)\rceil }$，用恰好 ${\log }_{2}T$ 个公平位选择替换序号；前 $qd$ 个序号对应上述按层、按首次访问次序的模拟，剩余序号忽略 PRG 挑战并模拟已经全随机的函数。若实际访问次数不足，相关步骤同样为空。设最终判别器对展开后的相邻混合接受率为 $p_0,\dots ,p_{qd}$，该单台统一区分器两个挑战世界的带符号差为

因此其绝对优势为端点优势除以 $T<2qd$。这保证同一个有界时间算法即可传递不可忽略性，无须无上限拒绝采样或逐长度选择最佳节点。

为什么不能展开整棵树作为归约 ​

直接把每一个潜在节点都替换，表面上也能从真树走到随机树，但会出现 $2^d$ 个步骤与指数模拟时间。它无法从多项式 PRF 攻击构造多项式 PRG 攻击。

按需展开改变的是证明与模拟的工作量，不是函数本身。对于所有可能输入，$F_k$ 早已由同一密钥确定；模拟器只在对手实际问到相应前缀时补上必须保存的信息。理想随机函数同样可用懒采样表回答，而无需存储指数大的全表。

一条求值路径的外层状态占 $O(n+d)$ 位，另计 $G$ 本身的工作空间；缓存多条查询路径可减少共同前缀的重复计算，连同根最多保存 $O((1+qd)n)$ 位节点标签，另计索引开销。没有缓存仍可从根重新求值，确定性保证回答一致。

GGM 输出是任意函数，不保证置换或可逆。要构造分组密码公理库分组密码Block cipher由密钥索引、作用于固定长度分组且可高效求逆的置换族；消息级保密与认证还取决于工作模式。模型中的可逆置换，还需例如Feistel/Luby–Rackoff 构造公理库Feistel 网络与 Luby–Rackoff 定理Feistel network · Luby–Rackoff theorem用Feistel的可逆结构从PRF构造PRP，给出两轮与三轮的区分攻击，解释三轮正向安全和四轮双向安全的不同接口及生日项。。相反，用 PRF 作为固定长度消息的认证标签，也还需把消息编码、密钥复用与完整安全实验说明白。