伪随机函数

PRF 是由短密钥索引且可快速计算的函数族，从黑盒交互看，对高效、可自适应查询的观察者就像一张真正随机、按需生成又始终一致的巨大输入输出表。真正随机函数会为每个新输入独立抽取输出，并对重复输入保持一致，PRF 必须同时模拟这两点。它不是“输出统计上均匀”这么简单，攻击者能选择输入、比较相关输出并进行多次查询。

攻击者可以根据先前回答选择下一次查询，因此只验证固定非自适应样本不足。真正随机函数在同一输入上必须返回同一输出，而“每次调用独立随机返回”是另一种对象。

固定常数函数或简单线性函数即使单点输出均匀，也可通过两次查询识别关系。PRF 与 PRP 不同：随机函数可碰撞，分组密码理路分组密码Block cipher由密钥索引、作用于固定长度分组且可高效求逆的置换族；消息级保密与认证还取决于工作模式。模型中的随机置换不能；在查询远低于生日界时可通过 switching lemma 联系。

PRF 用于消息认证码理路消息认证码Message authentication code · MAC用共享密钥生成并验证消息完整性标签的机制。、对称加密、密钥派生和协议会话标签。例如，$tag=F_k(m)$ 可形成固定长度 MAC 的基础；可变长度消息还需明确编码，不同用途需作域分离。安全证明常通过把真实 PRF 逐步替换为随机函数来简化协议分析。

伪随机生成器理路伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。经GGM 树构造理路GGM 伪随机函数构造GGM construction沿长度倍增生成器的二叉树求值，以按需展开和逐层混合证明自适应查询安全，并核算触及节点而非指数全树的代价。得到长输入 PRF：每个输入位选择生成器输出的一半，沿树走到一个叶子。面对自适应查询，证明只替换首次访问的节点；$q$ 次长度为 $d$ 的查询至多触及 $qd$ 个相关节点，因而不必生成整棵指数大树。不可区分性理路不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。给出相应 oracle 游戏。