伪随机函数

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

攻击者可以根据先前回答选择下一次查询，因此只验证固定非自适应样本不足。真正随机函数在同一输入上必须返回同一输出，而“每次调用独立随机返回”是另一种对象。分组密码通常建模为 PRP，不是任意函数；在适当查询规模下可借 PRP/PRF switching 论证把它当作 PRF 使用。

令 oracle 要么是 $F_k(\cdot )$，要么是随机函数 $R(\cdot )$；区分器可自适应查询 $x_1,x_2,\dots$。安全要求其优势可忽略。用 PRF 计算 $tag=F_k(m)$ 可形成固定长度 MAC 的基础，但需处理可变长度编码与域分离。

固定常数函数或简单线性函数即使单点输出均匀，也可通过两次查询识别关系。PRF 与 PRP 不同：随机函数可碰撞，分组密码模型中的随机置换不能；在查询远低于生日界时可通过 switching lemma 联系。

PRF 构造消息认证码、对称加密、密钥派生和域分离，也可由 PRG 在标准假设下构造。安全证明常通过把真实 PRF 逐步替换为随机函数来简化协议分析。

伪随机生成器公理库伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。 可经 GGM 构造 PRF，不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。 给出 oracle 游戏。MAC公理库消息认证码Message authentication code · MAC用共享密钥生成并验证消息完整性标签的机制。、对称加密、密钥派生和协议会话标签都使用 PRF；分组密码公理库分组密码Block cipher由密钥索引固定长度消息空间上的可逆置换族。 则常被建模为伪随机置换。