从这一节开始，我们介绍一个比分组密码更简单的概念：伪随机函数（PRF）。在后续的课程中，大家会看到，PRF 有着广泛的应用。
PRF 与分组密码有着紧密的联系。由于两者在概念上十分接近，当我们设计了一个以PRF 为基本模块的密码体制后，我们可以在理论上使用 PRF 的安全模型证明其安全性，而在实际应用时，可以用安全的分组密码代替 PRF 而不失安全性。
一、PRF的定义
PRF 是一个确定性的函数，记为 F。
我们称 F 是定义在（K, X, Y）上的 PRF，其中 K 是密钥空间，X 是输入空间，Y 是输出空间。
它有两个输入，一个是密钥 k，另一个是数据块 x∈X（称作输入数据块）。它的输出y=F(k, x) ∈Y 也是一个数据块（称作输出数据块）。
对于 PRF，其安全性要求：给定一个随机产生的密钥 k，函数 F (k,.) 应该看上去“像”是一个定义在 X 到 Y 上的随机函数。
那么问题来了，什么叫随机函数呢？
二、随机函数
给定集合 X 和 Y，考虑定义在 X 到 Y 上的函数 f：X→Y。
首先把所有定义在 X 到 Y 上的函数集中起来，形成一个集合。这个集合里的每个元素都是一个类似 f 这样的函数，它们的定义域都是 X，值域是 Y。
这个集合记为 Funs[X, Y]，它就是定义在 X 到 Y 上的所有函数的集合。
很明显，这个集合里一共有 |Y|^|X| 个函数，非常大！
现在，从 Funs[X, Y] 中随机选择一个函数。这个函数就是“随机函数”。
需要注意的是，所谓的“随机函数”强调的是这个函数是随机地被选择出来的。因此，“随机函数”这个概念和函数的输出是否是随机的没有关系。即使一个函数的输出不是随机的，但只要它被选出的时候是随机选择的，那么它就是“随机函数”。理解这一点非常重要！（这和前面章节介绍过的“随机置换”的概念类似）
三、PRF的安全模型
有了随机函数的概念，定义 PRF 的安全性就很容易了。
我们仍然定义一个安全模型。在 PRF 的安全模型中，同样考虑两个挑战者，每个挑战者都控制着一个函数 f，只不过不同的挑战者选择f时候的方法不同：
一个挑战者随机选择一个密钥 k，令 f := F (k, .)；
另一个挑战者控制的f则是一个随机函数 (从 Funs[X, Y] 中随机选择一个函数并令之为 f)。
攻击者 A 不知道自己面对的挑战者到底是哪一个，但他可以通过“探测”的方法来帮助判断。A 的最终目标就是要猜出自己面对的到底是哪一个挑战者。
探测的方法是这样的：A 可以向挑战者发送一个元素 x_i∈X，挑战者将相应的 y_i:= f(x_i) 返回给 A。
A 可以进行这样的探测很多次。
当然，A 可以根据前一次探测得到的y_i来产生下一次探测时使用的x_{i+1}，以根据它们之间的关系来判断到底挑战者是哪一个，也即面前的挑战者控制的函数到底是哪一种类型：使用随机密钥的 PRF，还是随机函数。
PRF 的安全性要求，攻击者不能区分开二者。也即，一个安全的 PRF 应该和随机函数是计算上不可区分的。
设 W0 和 W1 分别表示 A 在实验 EXP(0) 和 EXP(1) 中输出 1 的事件。
攻击者 A 的优势定义为 Adv := |Pr[W0] – Pr[W1]|。
定义 (安全的 PRF)：如果所有高效的攻击者的优势都是可忽略的，那么该 PRF 是安全的。
四、伪随机置换（PRP）
一个分组密码其实也可以被称之为伪随机置换（PRP），因为分组密码和PRF的定义及安全模型是非常类似的，分组密码的安全性要求其与随机置换在计算上不可区分。
通过定义可以知道，PRF 和 PRP（分组密码）之间最主要的区别就是，PRP 是有逆函数的，而 PRF 未必有逆函数。
在后面的课程里，我们会时常用到 PRP 这个概念。不过一提到 PRP，大家头脑里应该马上就反应过来，其实说的就是分组密码。