形式陈述

伪随机函数族 $F=\{F_k:D_n\to R_n{\}}_{k\in \{0,1{\}}^n}$ 要求可高效求值，并且对任意概率多项式时间、可自适应查询的预言机区分器 $A$，

$$|\text{Pr}[A^{F_{U_n}}=1]-\text{Pr}[A^{\mathcal{R}}=1]|$$

可忽略，其中 $\mathcal{R}$ 从全部函数 $D_n\to R_n$ 中均匀选择并对重复查询保持一致。攻击者知道族和算法，只不知道均匀密钥。若每个 $F_k$ 还是置换，则相应概念是伪随机置换。

直觉

一个短密钥索引出可快速计算的函数，但从黑盒交互看，它像一张真正随机、按需生成且始终一致的巨大输入输出表。

例子与边界

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

推论与应用

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

参考资料

• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，Ch. 3, pseudorandom functions and oracle indistinguishability。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Chs. 3–4, PRFs, PRPs, and applications。