2.3 伪随机函数

伪随机函数（Pseudo Random Function，简写为PRF）是设计前沿密码学协议的核心工具。在隐私计算领域，PRF是构成不经意传输（Oblivious Transfer，简写为OT）、隐私集合求交（Private Set Intersection，简写为PSI）等密码学算子和协议的重要基础算法。在本节中，首先给出构造伪随机函数所需要的背景知识，即函数簇和随机函数；然后给出伪随机函数的定义与分析；最后给出伪随机函数的两个具体应用实例。

2.3.1 函数簇与随机函数

1.函数簇

一个函数簇是一类映射 F ： K × D R ，其中 K 是 F 的密钥集合， D 是 F 的定义域， R 是 F 的值域。密钥集合的范围都是有限的，而且所有的集合都是非空的。双输入函数 F 取一个密钥 k 和一个输入 x ∈ X ，返回一个值 y ∈ Y ，用 y F （ k ， x ）表示。对于任何密钥 k ∈ K ，定义映射 F k ： D R ，其中 F k （ X ）= F （ K ， Y ）。函数 F k 被称为函数簇 F 的一个实例。因此， F 指定了一类与每个密钥所对应映射的集合。

2.随机函数

假设存在两个有限非空集合 D ， R ⊆｛0，1｝ ^* ，ℓ、 L 同为大于或等于1的两个整数，存在从 D 映射到 R 的函数Rand（ D ， R ）。为了简化，使用Rand（ℓ， L ）表示Rand（ D ， R ），其中 D =｛0，1｝ ^ℓ ， R =｛0，1｝ ^L 。可以观察到，Rand（ℓ， L ）的输入和输出分别是长度为ℓ和 L 的二进制串，密钥空间为 。下面结合实例，说明密钥空间如何计算得来：

假设随机函数为Rand（3，2），即ℓ=3， L =2，函数定义域为｛0，1｝ ³ ，值域为｛0，1｝ ² 。如图2-13所示，函数的输出为（11，01，00，10，10，00，01，11）。这里的输出可能性为2 ¹⁶ = ，即密钥空间为2 ¹⁶ = （随机函数为确定性算法，输出和密钥是一一对应的）。

2.3.2 伪随机函数定义与分析

伪随机函数（Pseudo Random Function，简写为PRF）是一类函数簇，其性质是该函数簇的随机实例的输入/输出行为与随机函数的输入/输出行为“在计算上无法区分”。现假设一个函数簇 F ： R K × D ，其中 K =｛0，1｝ ^k 、 D =｛0，1｝ ^ℓ 、 R =｛0，1｝ ^L ，且 k 、ℓ、 L 同为大于或等于1的整数。

想象一下，某天Alice在路边捡到一个微型计算机，发现这个计算机能够打开一个终端。Alice好奇地打开终端，屏幕提示：“难题挑战游戏：该计算机连接两个不同的‘计算世界’——World 0和World 1，两个世界各自拥有独特的计算函数。在输入一个定义域 D =｛0，1｝ ^ℓ 内的数值后，会得到一个值域 R =｛0，1｝ ^L 内的返回值。请根据以上有限信息，判断返回值来自哪个‘计算世界’，请问你是否接受挑战？”

下面分析Alice是否能够成功应对难题挑战。

首先，将两个“计算世界”形式化表示。

World 0： 定义函数 g ，且 g 属于随机函数簇Rand（ D ， R ），即 Rand（ D ， R ）。其中，$表示随机选取。

World 1： 定义函数 g ，且 g 属于伪随机函数簇 F k （ D ， R ），即 。其中，$表示随机选取， k 表示在 K 中随机选取的密钥， K 表示密钥空间。

我们试图告诉Alice计算发生在哪个世界的行为，可以通过区分器（distinguisher）的概念正式确定。区分器是一种算法，它被赋予对函数 g 的神谕（Oracle）访问权，并试图确定 g 是随机的，还是伪随机的。（也就是说，计算是发生在World 0的，还是在World 1的。）区分器只能通过给函数 g 提供输入并检查这些输入的输出来与之互动；它不能以任何方式直接检查函数 g 。定义 A ^g 为区分器 A 被赋予对函数 g 的神谕访问权。如图2-14所示，如果区分器返回 b= 1的概率无论在哪个世界都大致相同，即二者的概率差值小于或等于 ε （可忽略值），那么这个函数簇就是伪随机的。

区分器 A 模拟了Alice，试图通过计算机向函数 g 输入查询来确定计算机背后是哪个世界。将查询 g 的能力形式化为给 A 一个神谕，它接收输入的任何字符串 x ∈ D 并返回 g （ x ）。区分器 A 可以确定查询的内容，而且这些查询内容可以基于之前的查询结果构建。最终，它输出一个比特 b ，这显示了它对计算机背后是哪个世界的决定。输出单比特值1，意味着 A 认为计算机背后是World 1；输出单比特值0，意味着 A 认为计算机背后是World 0。应该注意的是，函数簇 F 是公开的。敌手和其他任何人都知道这个函数簇的描述，并且能够在给定值 k、x 的情况下计算出 F （ k ， x ）。

图2-14中的每个实验都有一定的概率返回1。这个概率是在实验中所做的随机选择上取得的。因此，对于第一个实验，概率是关于 k 的选择和 A 可能做出的任何随机选择的组合，因为 A 被允许是一个随机算法。在第二个实验中，概率是关于随机选择 g 和 A 做出的任何随机选择的组合。这两个概率应该分开评估。观察一下两个实验返回1的概率的差值。如果 A 在判断它所处的世界方面做得很好，那么它在第一个实验中返回1的次数就会多于第二个实验。所以，这个差值是衡量 A 做得如何的一个标准。我们把这一措施称为 A 的优势（advantage）。不同的区分器会有不同的优势。有以下两个原因导致一个区分器可能比另一个区分器取得更大的优势：一个原因是，它提出的问题更“聪明”；另一个原因是它问的问题更多，或者花了更多的时间来处理回答的问题。事实上，随着区分器看到越来越多的 g 的输入和输出例子，或者花更多的计算时间，区分器分辨计算发生在哪个世界的能力应该上升。因此，函数簇 F 的“安全性”必须被认为取决于允许攻击者的计算资源和时间限定。

2.3.3 伪随机函数应用

为了更容易地理解伪随机函数，下面通过两个实例来介绍如何结合随机函数和伪随机函数构造对称加密算法和消息身份验证算法。

1.对称加密算法

假设Alice和Bob已共享一个随机密钥 s 。如图2-15所示，Alice可以通过以下方式给Bob传递一个秘密消息 m 。

步骤1： Alice选择随机数（随机整数） r ∈ ，其中 p 为大素数。

步骤2： Alice计算 c =Enc s （ r ， m ）= F s （ r ）⊕ m ，其中 F s （·）表示某一伪随机函数。

步骤3： Alice将〈 r ， c 〉发送至Bob。

步骤4： Bob输入密钥 s 和 r ，执行解密计算 m =Dec s （ r ， c ）= F s （ r ）⊕ c 。

假设存在秘密消息 m 1 和 m 2 ，根据随机函数的性质可知，区分Rand（ r ）⊕ m 1 和Rand（ r ）⊕ m 2 在信息论上是不可能的。使用 F s （·）对Rand（·）进行替换，得到 F s （ r ）⊕ m 1 和 F s （ r ）⊕ m 2 。由图2-15可知， F s （ r ）⊕ m 1 和 F s （ r ）⊕ m 2 之间的任何有效区分的优势不会明显改变，因此保证使用伪随机函数构造的对称加密算法具有可证安全性。

2.消息身份验证算法

该算法的目标是，让Bob验证一个消息 m 源自Alice。为此，Alice和Bob共享了一个只有他们知道的随机密钥 s 。如图2-16所示，当Alice希望Bob能够验证 m 时，她会附加一个可以通过 m 和 s 计算出来的标记 σ （ σ = F s （ m ））。Bob在接收到Alice发送来的（ m ， σ ）信息后，结合共享密钥 s 来计算标记 σ '= F s （ m ），通过判定 σ' 与 σ 是否相同来确定验证是否通过。（ m ， σ ）的可验证性源于Bob也知道 m 和 s ，因此可以有效地计算 σ 。

3.不经意伪随机函数

通过伪随机函数能够构造不经意伪随机函数（Oblivious Pseudo Random Function，简写为OPRF），进而构造一些复杂的多方安全计算协议，例如隐私求交协议、联合计算协议等。下面结合一个具体的例子来描述不经意伪随机函数的用途。

假设Alice和Bob是两个互不信任的计算参与方，Alice掌握输入数据 m ，Bob掌握随机密钥 k ，其中密钥 k 和数据 m 同为他们各自的机密信息。如果Alice和Bob希望共同执行一个加密任务，即使用密钥 k ，通过AES算法（这里将AES看作一个伪随机函数，并且只考虑加密算法，不考虑解密算法）将数据 m 加密为密文 c ，他们该如何做呢？根据观察发现，他们各自在本地执行计算是无法完成任务的，根本原因在于AES算法的两个输入，即密钥 k 和数据 m 分处在两方本地存储域。为了任务的正常执行，Alice和Bob可将自己掌握的信息与对方共享，如此AES算法便能正常运行。遗憾的是，他们并不能这样做，因为Alice和Bob是两个互不信任的参与方，一旦他们共享自己的机密信息，将面临信息泄露的风险。那么，他们如何在不泄露自己机密信息的前提下，完成计算任务呢？这似乎是一个不可能完成的任务。但随着不经意伪随机函数的出现，如图2-17所示，这个任务又变得很容易解决了。不经意伪随机函数是一个特别复杂的计算协议，这里不进行详细介绍，具体细节可参考4.2.3节的内容。