可搜索加密的开山之作：《搜索加密数据的实用技术》

摘要

希望以加密的形式将数据存储在诸如邮件服务器和文件服务器之类的数据存储服务器上，以降低安全和隐私风险。但这通常意味着为了安全而牺牲功能。例如，如果客户端希望仅检索包含某些词的文档，则先前不知道如何让数据存储服务器在不损失数据机密性的情况下执行搜索并回答查询。

在本文中，我们描述了加密数据搜索问题的密码方案，并为由此产生的密码系统提供了安全性证明。我们的技术有许多重要的优势。它们是可证明安全的： 它们为加密提供了可证明的保密性，在某种意义上，当只给出密文时，不受信任的服务器不能了解关于明文的任何信息；它们为搜索提供查询隔离，这意味着不受信任的服务器除了搜索结果之外，无法了解有关明文的更多信息。它们提供受控搜索，因此未经用户授权，不受信任的服务器无法搜索任意单词。它们还支持隐藏查询，以便用户可以要求不受信任的服务器搜索秘密单词，而不会将该单词泄露给服务器。我们提出的算法简单、快速（对于长度为N的文档， 加密和搜索算法只需要O（n）（流密码和分组密码运算），并且几乎不引入空间和通信开销，因此在今天是实用的。

引言

当今的邮件服务器（如IMAP服务器、文件服务器和其他数据存储服务器）通常必须完全可信——它们可以访问数据，因此必须信任它们不会在未经授权的情况下泄露数据——这会在应用程序中引入不良的安全和隐私风险。以前的工作展示了如何构建加密文件系统和安全邮件服务器，但通常必须牺牲功能来确保安全性。根本问题在于，当数据被加密时，将计算移动到数据存储似乎非常困难，并且加密数据上的许多计算问题以前没有实际的解决方案。

在本文中，我们展示了如何在不损失任何数据机密性的情况下支持搜索功能。例如，带宽有限的移动用户希望从基础架构中的不受信任的邮件存储服务器检索包含“紧急”一词的所有电子邮件。当服务器知道数据的内容时，这是微不足道的，但是如果我们不希望向服务器透露我们的所有电子邮件，我们如何支持搜索查询？

我们的答案是提出一种加密方案，该方案能够在不向不受信任的服务器泄漏任何信息的情况下搜索加密数据。

• 我们的技术可以证明是安全的。这些技术为加密提供了可证明的保密性，也就是说，如果只给出密文，不受信任的服务器就不能了解关于明文的任何信息。该技术提供受控的搜索，使得不可信服务器在没有用户授权的情况下不能搜索单词。该技术支持隐藏查询，使得用户可以要求不可信服务器搜索秘密单词，而不向服务器泄露该单词。这些技术还支持查询隔离，这意味着不受信任的服务器只了解关于明文的搜索结果。

• 我们的方案是有效和实用的。我们提出的算法简单而快速。更具体实际上，对于长度为N的文档，加密和搜索算法仅需要O（N）次流密码和分组密码运算。我们的方案基本上不引入空间和通信开销。它们也很灵活，可以轻松扩展以支持更高级的搜索。

我们的方案都采用概率搜索的形式：对单词w的搜索返回w在明文中出现的所有位置，以及可能的一些其他错误位置。我们可以通过调整加密算法中的参数m来控制错误的数量；每个错误的位置将以大约1/2m的概率返回，因此对于一个l-word文档，我们期望看到l/2m错误匹配。用户将能够消除所有错误匹配（通过解密），因此在远程搜索应用程序中，只要错误匹配不是太常见以至于淹没用户和服务器之间的通信信道，错误匹配就不会成为问题。

本文结构如下。我们首先在第2节中介绍加密数据的搜索问题，并在第3节中简要回顾一些重要的背景知识。然后，我们在第4节中描述了使用顺序扫描进行搜索的解决方案。我们将在第5节中进一步讨论高级搜索和索引搜索等问题。我们在第6节中讨论了相关工作，最后在第7节中结束。附录A给出了这些方案的所有安全性证明。

对加密数据进行搜索

我们首先定义了加密数据的搜索问题。

假设Alice有一组文档，并将它们存储在不受信任的服务器Bob上。例如，Alice可以是将其电子邮件消息存储在不受信任的邮件服务器上的移动用户。因为Bob是不受信任的，所以Alice希望加密她的文档，并且只将密文存储在Bob上。每个文档都可以划分为“单词”。每个“单词”可以是任何标记；根据感兴趣的应用领域，它可以是64位块、英语单词、句子或一些其他原子量。为简单起见，我们通常假设这些“单词”具有相同的长度（否则，我们可以填充较短的“单词”或拆分较长的“单词”，以使所有的“词”具有相同的长度，或者对可变长度的“词”使用一些简单的扩展；另见第5.3节）因为Alice可能只有低带宽网络连接到服务器鲍勃，她希望只检索包含单词w的文档。

为了实现这个目标，我们需要设计一种方案，以便在对密文执行某些计算之后，Bob可以以某种概率确定每个文档是否包含单词w，而不需要学习任何其他内容。似乎有两种方法。一种可能性是建立索引，对于每个感兴趣的单词w，该索引列出包含w的文档。另一种方法是在没有索引情况下执行顺序扫描。使用索引的 优点是，当文档较大时，它可能比顺序扫描更快。使用索引的缺点是存储和更新索引的开销很大。因此，使用索引的方法更适合大多数只读数据。

我们首先描述在没有索引的情况下对加密数据进行搜索的方案。由于基于索引的方案似乎需要不太复杂的构造，我们将推迟讨论使用索引进行搜索，直到本文结束（见第5.4节）。

背景和定义

我们的方案需要几个来自经典对称密钥密码学的基本原语。因为我们将证明我们的方案是安全的，所以我们只使用具有明确定义的安全概念的原语。我们将在这里列出所需的原语，并回顾其安全性的标准定义。对于那些对我们的安全理论证明不感兴趣的人，可以在第一次阅读时跳过这些定义。

我们采用了可证明安全文献中安全性的标准定义，并根据破解密码原语所需的资源来衡量密码原语的强度。如果攻击算法成功地用R指定的资源破坏了原语，我们将说攻击R-破坏了密码原语，并且如果没有可以R-破坏它的算法，我们将说密码原语是R-secure的。设是任意算法，X和Y是分布在{0,1}ⁿ上的随机变量。对于X和Y，A的区别概率（有时称为A的优势）为：，在此背景下，我们所需的原语列表如下：

1. 伪随机生成器G，即流密码。我们说G: K_G→S是一个的伪随机生成器，如果每一个运行时间不超过T的算法A都有优势。对手A的优势定义为： .其中，，是均匀分布在，上的随机变量。

2. 伪随机函数F。我们说是一个(t, q, e)-secure的伪随机函数，如果每个预言机算法A至多产生q个预言机运行时间最多为T的查询具有优势。优点被定义为，其中R表示从从X到Y的所有映射的集合中均匀选择的随机函数，并且其中在K和R的选择上采用概率。

3. 伪随机置换E，即分组密码。我们说是一个的伪随机函数，如果每一个最多进行q次预言机查询且运行时间最多为t的预言机算法A都有优势。定义了优势如，当然，加密可以在线进行。其中，表示从上所有双射集合中均匀选取的随机排列，并且其中概率取自和的选择。注意，敌手被给予了一个用于加密和解密的神谕；这对应于自适应选择明文/密文攻击模型。

通常，直觉是表示对使用最多t个离线工作和最多q个自适应选择文本查询的攻击的抵抗。

当然，根本不需要三个单独的原语，因为在实践中，所有三个原语都可以由一个现成的原语构建。例如，给定任何分组密码，我们可以使用计数器模式构建伪随机生成器，或者使用CBC-MAC构建伪随机函数。

我们依靠下面的符号。如果表示伪随机函数或置换。对于密钥为的输入x应用f的结果，我们写为。我们用表示X和Y的连接，我们用表示X和Y的逐位XOR。对于本文的其余部分，我们设是某个l的伪随机生成器，是伪随机函数，是伪随机置换。通常，我们将有，和。

我们的顺序扫描解决方案

在本节中，我们将介绍使用顺序扫描进行搜索的解决方案。我们首先从一个基本方案开始，并说明其加密算法提供了可证明的保密性。然后，我们将展示如何扩展第一个方案以处理受控搜索和隐藏搜索。我们描述了我们的最终方案，它满足我们前面提到的所有属性，包括最后的查询隔离。

方案一：基本方案

Alice想要加密包含单词序列的文档。直觉上，该计划通过使用具有特殊结构的伪随机位序列计算明文的按位异或（XOR）来工作。此结构将允许在数据上进行搜索，而不会泄露有关明文的任何其他内容。

更具体地说，基本方案如下。Alice使用某种流密码（即伪随机生成器G）生成伪随机值序列，其中每个的长度为n-m位。为了加密出现在位置i的n位字，Alice采用伪随机位，设置，并输出密文。请注意，只有Alice可以生成伪随机流，当然，加密也可以在网上进行，这样我们就可以在每个可用的字都进行加密。

在如何选择密钥方面存在一些灵活性。一种可能性是在文档中的每个位置使用相同的密钥k。另一替代方案是独立于所有其它密钥为每一位置选择新密钥。更一般地，在每个位置，Alice可以（a）选择与某个先前的相同，或者（b）独立于所有先前的密钥来选择。稍后我们将看到这种灵活性如何使我们能够支持各种有趣的功能。

如果伪随机函数P和伪随机生成器G是安全的，则基本方案提供可证明的保密性。通过这一点，我们的意思是，在未知的每个位置，对于任何计算上有界的对手，值与真正的随机比特是不可区分的。我们将定理形式化如下。

如果F是一个伪随机函数，G是一个伪随机生成器，并且如果密钥材料是如上所述选择的，则上述用于生成序列的算法是随机生成器，其中，与t相比，常数可忽略不计。

换句话说，如果伪随机函数和伪随机生成器足够安全，则我们期望基本方案适合于加密高达大约个字。有关该定理的更精确的陈述和完整的证明，请参见附录A。

基本方案以如下方式支持对密文的搜索： 如果Alice想要搜索单词w，她可以告诉Bob w和对应于单词w可能出现的每个位置i的。然后，Bob可以通过检查对于某个s是否具有的形式来搜索密文中的W。这样的搜索可以在线性时间内执行。在Bob做的位置不知道，Bob对明文一无所知。因此，该方案允许有限形式的控制：如果Alice仅希望Bob能够搜索密文的前半部分，则Alice应仅揭示对应于这些位置以及在密文的后半部分中没有使用的。

如到目前为止所描述的，基本方案并不十分令人满意：如果Alice想要帮助Bob搜索单词w，则Alice必须揭示所有的（从而可能揭示整个文档），或者Alice必须预先知道w可能出现在哪些位置（这似乎违背了远程搜索的目的）。然而，我们接下来将看到如何解决这一困难。

方案二：控制搜索

设是一个额外的伪随机函数，它将独立于F进行键控。

主要思想是选择我们的密钥为。我们要求Alice在K中均匀随机地选择，并且永远不会被揭示。然后，如果Alice希望允许Bob搜索单词W，则她向他揭示和W。这允许Bob识别W可能出现的所有位置，但是在的位置i上绝对不显示任何内容。这实现了我们所期望的受控搜索的目标。我们证明了这种方法的正确性。在下面的定理中。

假设F是一个伪随机函数，f是一个伪随机函数，G是一个伪随机生成器。如果如上所述选择密钥资料，则上述用于生成序列的算法将是一个伪随机生成器，其中。

这表明，如果底层原语是安全的，则我们的受控搜索方案与基本方案一样好。见附录A的证明以及更精确的公式。

这个想法的各种扩展是可能的。如果要加密的文档由一系列章节组成，则另一种方法是为单词生成密钥，C章中的W表示为。这允许Alice控制Bob可以搜索哪些章节以及控制Bob可以搜索哪些词。

我们可以通过使用分层密钥管理方案来进一步实现这一想法。Alice设置和。然后她可以透露任何一个感兴趣的每个章节的或本身，如果她希望简洁地授权Bob在所有章节中搜索W。

该方案仍然不支持隐藏搜索查询：为了让Bob搜索单词w出现的位置，Alice必须将w透露给Bob。我们将看到下一个这个问题很容易解决。

方案三：支持隐藏搜索

假设Alice现在想让Bob搜索单词W，但她不愿意向Bob透露W。我们建议对上述方案进行简单的扩展，以支持这一目标。

Alice应当仅使用确定性加密算法分别对明文的每个字W进行预加密。注意，不允许E使用任何随机性，并且的计算可以仅依赖于x，并且必须不依赖于文档中找到x的位置i。因此，我们可以将此预加密步骤视为使用某种块密码对文档中的单词进行ECB加密。（当然，如果单词很长，则在内部映射可以通过使用常数IV或类似的值对进行CBC加密来实现，但关键是该过程在文档的每个位置都必须相同。）设。

经过预加密阶段之后，Alice具有E加密的字序列。现在，她使用上述流密码构造对该序列进行后加密，以获得，其中和。

为了搜索单词W，Alice计算并且，并且将发送给Bob。注意这个允许Bob在不显示W本身的情况下搜索W。很容易看出，只要预加密E是安全的，该方案就满足隐藏搜索性质。

方案四：最终方案

细心的读者可能已经注意到方案III实际上有一个小的不足之处：如果Alice生成密钥为，则Alice不再能够仅从密文中恢复明文，因为她需要在她可以解密之前知道的最后m位。这违背了加密方案的目的，因为即使是有权访问解密密钥的合法主体也无法解密。（方案II也有类似的不足之处，但正如我们将在下面展示的那样，修复它的最佳方法是像方案III那样引入预加密。）

我们现在展示这个问题的一个简单修复。在固定方案中，我们将预加密字拆分为两部分，，其中（分别为）表示前n-m位（分别为最后m位）。Alice应该生成，而不是生成。为了解密，Alice可以使用伪随机生成器来生成（因为Alice知道种子），并且对于，她可以通过将与的前n-m个比特进行异或来恢复。最后，的知识允许Alice计算，从而完成解密。

如果未加密，则此修复不安全，因为在某些情况下，不同的字很可能具有相同的前n-m位。预加密将消除这个问题，因为所有的很可能都是不同的。（假设预加密E是伪随机置换，则由于生日悖论，在加密l words后至少发生一次冲突的概率最大为。

通过此修复，所得到的方案是可证明安全的，并且事实上我们还可以证明它提供了查询隔离，这意味着即使当单个密钥被泄露时，除了识别相应单词出现的位置的能力之外，没有额外的信息被泄露。

假设E是一个伪随机置换，F是一个伪随机函数，f是一个伪随机函数，G是一种伪随机生成器，并且我们如上所述选择密钥材料。则上述用于生成序列的算法将是一个伪随机生成器，其中。

此外，如果我们公开一个并且考虑通过丢弃在其中的位置处的所有值而获得的简化序列，则我们获得一个伪随机生成器， 其中。

严格地说，该定理的证明实际上并不要求E是伪随机置换：如果表示将W发送到的前n-m位的（键控）映射，那么我们可以采用弱得多的假设，即中的碰撞应该很少。作为特殊情况，如果的前b位可以被证明为伪随机函数，则E将必然具有所需的性质，并且我们将能够证明类似于定理3的结果。这表明对于预加密、对于长块，可以方便地将取为在密钥下W的CBC加密的比特反转（使用常数IV）。

在逐字加密之后，Alice还可以根据某种伪随机排列（只有Alice知道）对密文进行重新排序。在这种情况下，当Bob执行单词的搜索时，他将不能说出单词在真实明文中出现的位置。

讨论

其它实际考虑

我们可以看到这个方案中的更新很容易。例如，如果Alice想要将新文档添加到Bob的数据存储中，她可以简单地以适当的方式对其进行加密，并指示Bob将其附加到已经存储的密文中。此外，由于密钥可以从主密钥分层生成，因此密钥存储和管理也非常方便：Alice只需要记住一个密码，即主密钥。

在伪随机比特流中嵌入信息的基本技术也可能具有独立的意义：我们推测，这个简单的技巧可能对其他应用也有用。

支持更高级的搜索查询

我们之前提出的方案只解决了搜索单个单词的问题。我们展示了几个前示例来说明使用我们的方案作为基本构建块来实现更高级的搜索功能相对容易。

显然，我们可以容易地支持使用布尔运算符的高级搜索查询（例如，W和W'）、邻近查询（例如，W在W'附近）、以及短语搜索（例如W紧接在W'之前）。

如果查询以正则表达式的形式给出，例如使用有限形式的通配符，我们也可以支持搜索。例如，如果Alice希望搜索单词，那么她实际上可以生成26个以下形式的搜索查询。然而，随着搜索词变得更加通用，所需的查询数量（以及泄露到服务器的信息）显然会急剧增加。

对于许多应用程序，搜索的目的是查找包含特定单词的文档，其中出现的位置或次数是不相关的。例如，搜索电子邮件就是这样一个应用程序，其中查询采用“查找来自Joe的所有电子邮件”的形式。对于该应用，先前的搜索方案泄露了信息，因为服务器将知道单词在文档中的位置，或者在单词顺序被打乱的情况下至少知道单词在文档中的频率。因为我们只需要知道一个给定的文档是否包含一个单词，我们可以使用下面的技巧。我们为每个单词添加一个计数，它计算该单词以前在该文档中出现的次数。例如，单词“urgent”的第一次出现被存储为，第二次出现被存储为等。这允许Alice搜索仅第一次出现，如果她只想识别该词出现的文档；并且Bob没有获得关于搜索词在文档中的其他位置的任何信息。作为附加特征，该编码允许Alice通过搜索来搜索包含单词W的n次或更多次出现的文档。

处理可变长度字

在我们的方案中，我们可以搜索的最小单位是单个单词。到目前为止，我们假设明文可以很容易地分解为固定长度的单词序列。但在普通文本文档中可能不是这样。例如，如果搜索兴趣的最小单位是一个英语单词，那么我们必须处理英语单词长度不同的事实。

一种可能性是选择一个长度足以包含大多数单词的固定大小的块。太短或太长的字可以用某种预定的填充格式填充到块大小的倍数。（注意，填充不能是随机的，因为Alice需要知道填充才能执行搜索。）然而，这样的填充方案将引入空间低效率。此外，出于安全原因，我们不能将字长减少到某个限制以下。

另一种解决方案是使用可变长度的字。在这种情况下，为了支持随机访问解密，每个字的长度也需要与字一起存储。一种自然的方法是将长度字段存储在文件中的每个单词之前，并将长度字段和单词粘合在一起作为一个单词，以使用我们的标准方案执行加密和搜索。

当单词长度可能不同时，对服务器隐藏长度信息非常重要，因为泄露每个单词的长度可能会导致统计攻击。幸运的是，在这种情况下，服务器不需要知道执行搜索的长度：他可能只是扫描文件并在每个可能的位边界检查匹配。在这种情况下，每次扫描的成本会增加，因为操作的数量是由文档的位长决定的，而不是由文档中的块数决定的。然而，这种方法可以提供比面向块的方案更好的空间效率。

使用加密索引进行搜索

当数据大小较大时，顺序扫描可能不够有效。对于某些应用程序，即大型数据库，加速搜索的常用技术是使用预先计算的索引。在这里，我们展示了如何在不牺牲安全性的情况下，借助加密索引来回答搜索查询。

索引包含关键词列表；每个关键字都有一个指向该关键字出现的文档的指针列表。关键字是Alice以后可能想要搜索的感兴趣的字。Alice当然可以建立她的明文文档的索引，然后加密明文和索引，并将密文存储在Bob上。有趣的问题是如何加密索引。

一种简单的方法是只对索引中的关键字进行加密，并将位置列表保持清晰。这使得Bob很容易代表Alice执行搜索查询，但也会向Bob泄露大量信息，因此可能允许他应用各种统计攻击。因此，我们拒绝这种幼稚的做法。

一种简单的方法是加密索引中每个列表中的文档指针。因此，当Bob搜索并找到匹配时，他从索引中返回Alice匹配位置的加密列表。Alice可以对加密的条目进行解密，并向Bob发送另一个请求以检索相关文档。该方案的一个可能的优点是，请求可以嵌入在其他检索中，使得Bob可能对搜索请求和密文检索请求 的相关性具有不确定性。缺点是Alice必须花费额外的往返时间来检索文档。

如果Alice不想等待额外的往返时间，或者如果Alice希望Bob为她合并多个搜索查询的结果，其他技术也是可用的。例如，她可以使用与相关的密钥来加密索引中的文档指针列表，即。因此，当Alice想要搜索单词w时，她将向Bob揭示。为了防止Bob对索引进行统计分析，最好将指针列表保存在固定大小的列表中。对于不经常出现的单词，Alice可以将列表填充到固定大小。对于更常见的单词，Alice可以将长列表拆分为多个固定大小的列表；然后，为了搜索这样的词，Alice将需要要求Bob并行地执行并合并几个搜索查询。注意通过将指针列表保持在固定大小的列表中， 我们主要是防止Bob学习他没有搜索的关键字的统计信息。对于Bob搜索的关键词，他可能仍然能够从Alice的访问模式中了解到一些统计信息。从我们的观点来看，这是可以接受的，因为Alice首先只想检索相关文档。

请注意，索引搜索的一个常见缺点是，无论何时Alice更改其文档，她都必须更新索引。在Alice更新多少索引和Bob能够学习多少信息之间存在权衡。例如，如果Alice在将新文档添加到Bob的数据存储中时没有改变一个关键字条目的文档指针列表，则Bob将能够知道该关键字没有出现在新文档中。

因此，Alice需要更新索引的重要部分以隐藏真正的更新，这可能相当昂贵。开发支持更有效更新的方案是一个有趣的研究问题。

更多安全问题

在我们所有的方案中，通过允许Bob搜索单词w，我们有效地向他揭示了w可能出现的潜在位置的列表。如果我们允许Bob搜索太多的单词，他可以使用统计技术来开始了解有关文档的重要信息。一种可能的防御是减少M（使得错误匹配更普遍，因此Bob关于明文的信息是“有噪声的”），但是我们没有详细分析这种折衷的成本效益。

对于Alice来说，更好的防御方法是定期更改密钥，在新密钥下重新加密所有文档，并根据某种伪随机排列（Alice知道但Bob不知道）对密文进行重新排序。这将有助于防止Bob随着时间的推移学习相关性或其他统计信息。如果Alice想要对Bob隐藏所搜索的词在感兴趣的文档中出现的位置，则该技术也可能是有帮助的。

到目前为止，在我们讨论的所有方案中，我们必须信任Bob返回所有搜索结果。如果Bob拒绝我们，并且只返回部分（但不是全部）搜索结果，Alice将无法检测到这一点。在我们感兴趣的范围内，我们假设鲍勃不会以这种方式胡作非为。即使存在这种类型的攻击，也可以将我们的方案与哈希树技术相结合，以确保数据的完整性并检测这种攻击，尽管这种对策的完整描述超出了本文的范围。

相关工作

许多研究人员已经研究了在使用不可信文件服务器或外部不可信存储器时提供保密性和完整性的问题。但据我们所知，以前的工作还没有提供对加密数据进行搜索的解决方案。安全多方计算和不经意函数也被深入研究。我们相信，对于使用多方计算搜索加密数据的问题，可能有一种解决方案，但它需要很高的开销，例如多个服务器。我们的解决方案只需要一台服务器来搜索加密数据，因此是一个更实用的解决方案。

一些研究人员已经研究了私有信息检索（PIR）问题，以便客户端可以访问分布式表中的条目，而不会泄露他们感兴趣的条目。PIR文献通常旨在非常强的信息论安全界限，这使得更难找到实用的方案：PIR方案通常需要多个非共谋服务器，消耗大量带宽，不保证数据的机密性，不支持私有关键字搜索，并且不支持受控搜索或查询隔离允许取消部分（但不是全部）限制的重要例外情况）。相比之下，虽然我们的方案没有解决PIR问题，但它只需要一个服务器（没有不切实际的信任假设），具有较低的计算复杂度，并且支持具有非常强的安全属性的私有关键字搜索。

结论

我们已经描述了使用不可信服务器对加密数据进行远程搜索的新技术，并为所得到的密码系统提供了安全性证明。我们的技术有许多关键的优势：它们是可证明安全的；它们支持受控和隐藏的搜索和查询隔离；它们简单且快速（更具体地，对于长度为N的文档，加密和搜索算法仅需要O（N）的流密码和块密码操作）；且它们几乎不引入空间和通信开销。我们的方案也非常灵活，可以很容易地扩展以支持更高级的搜索查询。

我们得出的结论是，这为在不可信的基础设施中构建安全服务提供了一个强大的新构建块。

致谢

我们要感谢Doug Tygar提出的宝贵建议和意见。我们还要感谢John Kubiatowicz对加密数据搜索问题的鼓励。我们还要感谢Bob Briscoe对该文件的有益评论。