《动态可搜索对称加密》文章阅读

        可搜索对称加密（SSE）允许客户端以仍然可以被搜索的方式加密其数据。SSE最直接的应用是云存储，它使客户能够安全地将其数据外包给不受信任的云提供商，而不牺牲搜索数据的能力。
        SSE已经成为活跃研究的焦点，并且已经提出了许多实现各种级别的安全性和效率的方案。然而，任何实际的SSE方案都应该（至少）满足以下特性：次线性搜索时间、抵御自适应选择关键字攻击的安全性、紧凑索引以及高效添加和删除文件的能力。不幸的是，以前已知的SSE结构没有一种能同时实现所有这些特性。这严重限制了SSE的实用价值，并降低了它在现实世界云存储系统中的部署机会。
        为了解决这个问题，我们提出了第一个SSE方案来满足上述所有属性。我们的构建以几种重要的方式扩展了倒排索引方法，并为SSE的设计引入了新技术。此外，我们实现了我们的方案，并进行了性能评估，表明我们的方法是高效的，并准备部署。

引言

        可搜索对称加密(SSE)允许客户端加密数据，以便以后生成搜索令牌作为查询发送到存储服务器。给定一个令牌，服务器可以搜索加密数据并返回适当的加密文件。非正式地说，SSE方案是安全的，如果：（1）仅密文不揭示关于数据的任何信息；（2）密文与搜索令牌一起最多揭示了搜索的结果；（3）只能使用秘密密钥生成搜索令牌。
        SSE最直接的应用是设计可搜索的加密云存储系统，该系统可以在不牺牲实用性的情况下为云存储系统提供端到端的安全性。其他应用包括图形加密方案和受控披露机制的设计。

        在基于索引的SSE方案中，加密算法将索引δ和n个文件的序列，并输出加密的索引和n 个密文的序列。所有已知的构造可以使用任何对称加密方案加密文件f，即文件加密不依赖于加密方案的任何异常属性。

        为了搜索关键字，客户端生成搜索令牌，给定、和，服务器可以找到包含的文件的标识符。从这些标识符中，它可以恢复适当的密文。请注意，提供者了解到一些关于客户端查询的有限信息。特别是，它知道正在搜索的任何关键字都包含在加密为的文件中。有很多方法可以隐藏这些信息，最著名的是利用Goldreich和Ostrovsky 在不经意RAMs上的工作，但是这种方法导致了低效的方案。
        以前的工作。使用Goldreich 和Ostrovsky在oblivious RAMs上的工作，可以解决在对称加密数据上搜索的问题。不幸的是，这种方法需要交互并且开销很大。宋、瓦格纳和佩里格在2004年首次明确考虑了可搜索加密，其中他们给出了一种非交互式的解决方案，实现了与文件集合的长度成线性的搜索时间。SSE的正式安全概念随着时间的推移而发展。第一个概念，抵抗选择关键字攻击的安全性（CKA1），保证了：

        （1）加密的索引和密文除了文件的数量n和它们的长度之外，不泄露关于的任何信息；以及

        （2）加密的索引和令牌至多揭示了搜索的结果。然而，在中观察到，只有当搜索查询独立于和先前的搜索结果时，才提供安全性。为了解决这个问题，提出了更强的抗选择关键字攻击的自适应安全概念。最近，Kurosawa和Ohtaki提出了更强的通用可组合（UC）SSE概念。粗略地说，即使在任意环境中使用该方案时（例如，当与自身和/或其他密码协议和原语组成时），也能保证安全性。

        虽然有几种的SSE方案，但从实用的角度来看，它们都有局限性。特别地，构造需要时间来搜索，其中表示集合中文件的数量。虽然有的构造在实践中是渐近最优和有效的，但加密的索引可能非常大。此外，这三个方案都不是显式动态的；也就是说，如果不对整个数据集合进行重新索引，或者不使用类似于文献中所使用的通用且相对昂贵的动态化技术，就无法添加或删除文件。据我们所知，唯一一个且（显式）动态的SSE构造是由van Liesdonk、Sedghi、Doumen、Hartel 和Jonker提出的。在他们的方案中，搜索在关键词的数量上是对数的，这对于实际的目的来说可能是足够有效的。然而，该方案的主要限制是加密索引的大小相对较大（与[6]中的方案大致相同）。

另一项工作使用确定性加密来支持使用现有数据库和搜索技术搜索加密数据。这种方法不同于SSE，因为它只为具有高熵的数据和查询提供安全性。从Boneh、Di Crescenzo、Ostrovsky 和Persiano的工作开始，可搜索加密也被考虑在公钥设置中。
        表1总结了我们的方案和文献中出现的其他方案之间的差异。

方案名	动态性	安全性	搜索时间	索引大小
SWPOO	静态	CPA
Z-IDX	动态	CKA1
CM05	静态	CKA1
SSE-1	静态	CKA1
SSE-2	静态	CKA2
vSDHJ10	动态	CKA2
CK10	静态	CKA2
KO12	静态	UC
本论文	动态	CKA2

        表1：几种SSE方案的比较。搜索时间是每个关键字，更新时间是每个文件。是文件集合，是其位长，是中文件的数量，是包含关键字的文件的数量，是关键字空间的大小，是关键字出现在其中的文件的最大（超过关键字）数量。

        我们的贡献。在这项工作中，我们着眼于构建实用的SSE方案的问题，目的是设计实用的可搜索加密云存储系统。我们做出以下贡献：
        1. 我们提出了动态SSE的形式化安全定义。特别是，我们的定义抓住了SSE安全的一个强有力的概念，即针对选择关键字攻击的适应性安全（CKA2）。
        2. 我们构造了第一个SSE方案，它是动态的，的，并且实现了最优的搜索时间。我们注意到，与以前已知的方案不同，我们的构造在随机预言模型中是安全的。
        3. 我们描述了基于[8]的倒排索引方法的SSE方案的第一个实现和评估。我们的实现表明，这种类型的SSE方案非常有效。
        4. 我们对我们的方案进行了性能评估，显示了为（可搜索的）云存储系统增加机密性的增量成本。

预备的知识和注释

        长度为n的所有二进制字符串的集合表示为，以及所有有限二进制字符串的集合为。符号表示整数。我们写来表示被采样的元素。
        从分布，和来表示一个元素概率算法A的输出x由表示，确定性算法B的输出x由表示。给定一个元素序列，我们将其第i个元素称为或，将其元素总数称为。如果S是一个集合，则#S表示其基数。W表示所有的单词。如果是一个文件，那么表示它的总字数，是它的位长。
        此外，是从删除所有重复项后得到的文件（即，仅包含中排序的唯一单词根据它们第一次出现的顺序）。如果是一个字符串，那么是指它的位长。我们用表示n个字符串。

        我们使用各种数据结构，包括链表、数组和字典。如果是一个列表，那么表示它的节点总数。如果是一个数组，那么是它的总单元数，是存储在位置的值，表示在A中存储v所在的位置i的操作。字典（也称为键值存储或关联数组）是存储键值对的数据结构。如果对在T中，则是与s相关联的值v。表示在搜索属于T的关键字s下存储值v的操作，而#T是T中键值对的数量。我们有时将写成表示T中存在一些与搜索关键字s相关联的对。
        自始至终，将表示安全参数，我们将假设所有算法都隐式地将作为输入。函数在中是可忽略的，如果对于每个正多项式和所有足够大的k， 。我们写表示存在一个多项式使得对于所有足够大的；类似地，我们写表示存在一个可忽略的函数，使得对于所有足够大的，满足。如果对于所有的概率多项式时间（PPT）微分器D，，则两个分布系综和在计算上是不可分辨的。

        基本密码原语。私钥加密方案是一组三个多项式时间算法，使得是一种概率算法，它取安全参数并返回密钥；是一种概率算法，取一个密钥和一个消息，返回一个密文；是一种确定性算法，采用密钥K和密文，如果是生成的密钥，则返回。非正式地说，如果一个私钥加密方案输出的密文不泄露任何关于明文的部分信息，即使对于能够自适应地查询加密预言的对手，该方案也是的。
        除了加密方案，我们还利用伪随机函数（PRF）和置换（PRP），它们是多项式时间可计算的函数，不能被任何可能的多项式时间对手从随机函数中区分出来。我们请读者参考关于、PRFs和PRPs的正式定义。

        回想一下1中的内容，可搜索加密允许客户端以这样一种方式加密数据，即它可以在以后生成搜索令牌作为查询发送到存储服务器。给定一个搜索令牌，服务器可以搜索加密数据并返回适当的加密文件。

        该数据可以被视为一系列的n个文件，其中文件是一个来自所有的单词序列。我们假设每个文件都有一个唯一的标识符。数据是动态的，因此文件随时可能被添加或删除。我们注意到，文件不必是文本文件，而是可以是任何类型的数据，只要存在将每个文档映射到来自W的关键字文件的有效算法。给定关键字，我们用表示中包含的文件集是文件中的一组加密，那么指的是中文件的加密的密文。
        所有已知的SSE构造（包括我们的）的一个局限是，它们生成的令牌是确定性的，也就是说，总是为同一个关键词。这意味着搜索会泄露用户搜索模式的统计信息。目前，还不知道如何设计具有概率陷门的高效SSE方案。

        回想一下，我们考虑动态SSE，因此该方案必须允许添加和删除文件。这两种操作都是使用令牌来处理的。为了添加文件，客户端生成添加令牌，给定和，提供者可以更新加密的索引。类似地，为了删除文件，客户机生成一个删除令牌，提供者用它来更新。

        定义3.1（动态SSE），基于动态索引的SSE方案是九个多项式时间算法的元组，使得：

        ：是一种概率算法，以安全参数k作为输入，输出密钥K。

        ：是一种概率算法，以一个密钥和一个文件序列作为输入。它输出一个加密的索引和一个密文序列。

        ：是一个（可能是概率的）算法，将密钥和关键字作为输入。它输出一个搜索令牌。

        ：是一个（可能是概率的）算法，它以密钥和文件作为输入。它输出一个添加令牌和一个密文。

        ：是一个（可能是概率的）算法，将密钥和文件作为输入。它输出一个删除令牌。

        ：是一种确定性算法，将一个加密索引、一个密文序列和一个搜索令牌作为输入。它输出一个标识符序列。

        ：是一种确定性算法，它以一个加密索引、一个密文序列、一个添加令牌和一个密文c作为输入。它输出一个新的加密索引和一个密文序列。

        ：是一种确定性算法，将一个加密索引、一个密文序列和一个删除令牌作为输入。它输出一个新的加密索引和新的密文序列。

        ：是一种确定性算法，以密钥和密文作为输入，输出文件。

        如果对于所有，对于生成的所有键，对于所有的，对于输出的所有，以及对于上的所有添加、删除或搜索操作序列，搜索总是返回正确的索引集，则动态SSE方案是正确的。

        直观地说，我们从动态SSE方案中要求的安全保证是：

        （1）给定一个加密的索引和一个密文序列，任何对手都无法获知关于文件的部分信息；并且

        （2）另外给定了记号序列。对于自适应生成的查询序列（它可以用于搜索、添加或删除操作），任何对手都无法获知关于或的任何部分信息。
        这种准确的直觉可能难以实现，并且大多数已知的高效和非交互式SSE方案揭示了访问和搜索模式。因此，我们需要通过允许向对手透露一些有关消息和查询的有限信息来适当地削弱定义。为了捕捉这一点，我们采用[8]和[6]的方法，用一组泄漏函数来参数化我们的定义，这些函数精确地捕捉了密文和令牌所泄漏的内容。
        如在[8]中所观察到的，关于SSE安全性的另一个问题是该方案是抵抗自适应选择关键字攻击（CKA2）还是仅抵抗非自适应选择关键字攻击（CKA1）。即使客户端的查询是基于加密的索引和先前查询的结果，前者也能保证安全性。只有当客户的查询独立于索引和先前的结果时，后者才能保证安全性。
        在下面的定义中，我们将的概念从[8]扩展到动态设置。
        定义3.2（动态）。
        让是一个基于动态索引的SSE方案，并考虑下面的概率实验，其中A为有状态对手，S为有状态模拟器，L1、L2、L3和L4为有状态泄漏算法：
        ：挑战者运行生成密钥K。输出，接收，使来自挑战者的。对手让一个多项式的自适应查询，为每个查询问，收到从挑战者号搜索令牌这样，一对添加标记和密文,或删除令牌这样。最后，A返回实验输出的位b，这是实验的结果。

        ：输出。给定，生成并发送一对给。对手进行多项自适应查询，并且对于每个查询q，模拟器被给予，或。模拟器返回一个适当的令牌，如果是加法运算，则返回一个密文。最后，返回一个由实验输出的位b。
        我们说SSE是的，可以抵御自适应动态选择关键字攻击，如果对于所有ppt对手，存在这样的满足以下PPT的模拟器：
          
注意，除了包含动态操作，我们的定义和[8]的定义之间的差异是风格上的:我们在[6]的风格中使用泄漏函数，而不是在[8]的风格中使用历史。

我们的构建

        我们的方案是基于倒排索引数据结构的的SSE-1结构的扩展。尽管SSE-1是实用的（它对于小常数是渐近最优的），但它确实有一些限制，使得它不适合直接用于加密云存储系统中：

        （1）它只能抵抗非自适应选择关键字攻击（CKA1），这直观地意味着它只能为批量执行搜索的客户端提供安全性；以及

        （2）它不是显式动态的，即，它只能支持使用通用和低效技术的动态操作。

        在讨论如何解决这些问题之前，我们首先回忆一下SSE-1结构的一个高级变体。其结构基本上与SSE-1相同，只是间接寻址管理的查找表被字典所取代。该方案利用了私钥加密方案，两个伪随机函数F和G，我们称之为搜索阵列的阵列和我们称之为搜索表的字典。这里我们假设SKE是匿名的，因为给定两个密文，人们不能确定它们是否是用同一个密钥加密的。

        SSE-1的构建

        为了加密文件集合，该方案为每个关键字构造一个列表，每个列表由节点，它们被存储在搜索阵列中的随机位置。节点被定义为，其中id是包含w的文件的唯一文件标识符，表示在范围中的节点N的位置。为了防止的大小泄露有关f的统计信息，建议的大小至少为，和使用长度适当的随机字符串填充未使用的单元格。对于每个关键字，将指向头部的指针插入到搜索键下的搜索表中，其中是PRF F的密钥，然后在生成的密钥下使用SKE对每个列表进行加密，其中是PRF G的密钥。

        如果要搜索关键字，客户端发送和就足够了。然后，服务器可以使用和来恢复指向头部的指针，并使用来解密列表并恢复包含的文件的标识符。只要T支持O(1)时间复杂度查找（可以使用哈希表实现），服务器的总搜索时间在中是线性的，这是最优的。

        使SSE-1动态。如上所述，SSE-1的限制有两方面：

        （1）它只是的，（2）它不是显式动态的。

        正如在[6]中观察到的那样，第一个限制可以通过需求相对容易地解决SKE是不提交的（实际上是的该工作中提出的SSE结构采用简单的基于PRF非承诺加密方案）。
        然而，第二个限制就不那么容易克服了。难点在于文件的添加、删除或修改需要服务器在存储在中的加密列表中添加、删除或修改节点。
        这对于服务器来说很难做到，因为：

        （1）当删除文件时，它不知道（在a中）与f对应的节点存储在哪里；

        （2）当从列表中插入或删除一个节点时，它不能修改前一个节点的指针，因为它是加密的；

        （3）添加一个节点后，它不知道中哪些位置是空闲的。
        在高层次上，我们处理这些限制如下：

        1. （文件删除）我们添加了一个额外的（加密的）数据结构，称为删除数组，服务器可以查询（通过客户端提供的令牌），以恢复指向被删除文件对应节点的指针。更准确地说，删除数组为每个文件存储一个指向中的节点的节点列表，如果文件被删除，这些节点应该被删除。
所以搜索数组中的每个节点在删除数组中都有一个对应的节点删除数组中的每个节点都指向搜索数组中的一个节点。在整个过程中，我们将把这样的节点称为对偶，并编写来指代节点的对偶。

        2. （指针修改）我们使用同态加密方案对存储在节点中的指针进行加密。这类似于[23]中van Liesdonk等人用来修改他们构造的加密搜索结构的方法。通过向服务器提供适当值的加密，它就可以修改指针，而不需要解密节点。我们使用“标准”私钥加密方案，该方案包括将消息与PRF输出XORing。这个简单的构造还有一个优点，即不提交（在私有密钥设置中），我们可以利用这个优点来实现CKA2安全性。
        3. （内存管理）来跟踪中的哪些位置是空闲的，我们添加并管理由空闲列表组成的额外空间，服务器使用空闲列表来添加新节点。

图2和图3详细描述了我们的构造，图1（我们将在下一节中讨论）演示了包含3个文件和3个惟一单词的玩具索引上的动态SSE数据结构。

        在图1 中，我们展示了针对特定索引的全动态SSE 方案的数据结构。该索引基于三个文档，即、、，基于三个关键词，即、、。所有文档都包含关键字，关键字仅包含在文档中，而包含在文档和中。图1中还示出了相应的搜索表、删除表、搜索数组和删除数组。注意，在真实的DSSE索引中，会有填充来隐藏文件-单词对的数量；在这个例子中，为了简单起见，我们省略了这个填充。

        搜索中。搜索是我们方案中最简单的操作。假设客户希望搜索包含关键字的所有文档。他准备搜索令牌，其中包含和。第一值将使服务器能够在搜索表中定位对应于关键字的条目。在我们的例子中，这个值是。服务器现在使用第二个值来计算。这将允许服务器在搜索数组中定位正确的条目（在我们的例子中是4个），并开始“暴露”存储指向包含的文档的指针的位置。这种去屏蔽是通过搜索令牌中包含的第三个值来执行的。

        添加文档。假设现在客户希望添加包含关键字和的文档。请注意，搜索表根本没有改变，因为正在进行成为关键字和列表中的最后一个条目，并且搜索表仅存储前几个条目。然而，所有其他数据结构必须以下列方式更新。首先，服务器使用无需快速检索搜索数组中“空闲”位置的索引，新条目将存储在这些位置。在我们的例子中，这些位置是2和6。服务器在这些条目中存储新信息和。现在，服务器需要将这个新条目连接到相应的关键字列表：使用add令牌，它在搜索数组中检索元素x和y的索引和，使得x和y对应于关键字列表和的最后条目。这样，服务器同态地将和的“下一个”指针设置为指向新添加的节点，这些节点已经存储在搜索数组的位置2和6。

        注意，访问搜索数组中的空闲条目也提供了对删除数组Ad的相应空闲位置的访问。在我们的例子中，删除数组中空闲位置的索引是3和7。服务器将在删除数组中的这些位置存储新的条目和,并将它们用指针连接起来。最后，服务器将通过将条目设置为指向删除数组中的位置3来更新删除表，以便稍后可以容易地检索文件f4进行删除。
        删除文档。假设现在客户想要删除一个已经存储在我们的索引中的文档，比如说文档，它包含关键字和。删除是添加的“双重操作”。首先，服务器使用删除令牌的值在删除表中定位正确的值。这将允许服务器访问剩余数据结构中需要用加法算法以类似方式更新的部分。即它将“释放”删除数组中的位置4和6以及搜索数组中的位置1和3。当“释放”搜索数组中的位置时，它还将同态更新指向新条目的关键字列表和（在我们的例子中，指向列表的末尾——通常在已删除条目的下一个指针中）。注意，删除数组不需要这样的指针更新。

安全性

        正如3中所讨论的，所有实际的SSE方案都会泄漏一些信息。不幸的是，SSE的实际安全性在多大程度上受到这种泄漏的影响还不清楚，这在很大程度上取决于SSE的使用环境。我们知道只有一个具体的攻击利用这种泄漏，它强烈依赖于以前的查询知识和有关文件收集的统计数据。然而，我们注意到，我们的方案比大多数先前已知的构造泄漏得更多，因为它是动态的，并且在其各种操作泄漏的信息之间存在相关性。下面，我们提供一个描述和比较SSE方案泄漏的框架。基于这个框架，我们将我们的方案的泄漏与SSE-1的泄漏进行了比较，后者是静态的；以及[23]中提出的方案的泄漏，这是动态的。

        描述渗漏特征的框架。我们的方法是根据包含两个字和文件标识符的表的数据库来描述泄漏：SSE操作将匿名化的行写入数据库的表中，而一个对话试图对结果数据进行去匿名化。表格中的列包含文件和单词的标识符:每个文件由一个确切的标识符表示，每个单词由一个确切的标识符表示，但是这些标识符是相对于文件和单词随机选择的。为了便于说明，我们假设有一个为文件和单词生成标识符的函数id。
        我们的方案将文件字信息写入两个表中：
        1. 文件字表（FW），其中每一行将一个字标识符与一个文件标识符相关联。

        2. 邻接表，其中每一行都与用阿迪方向“下一个”或“上一个”和下列值之一表示一个字标识符和一个文件标识符：

        （1）另一个文件标识符，或（2）一个值。

        每一行还包含它被写入的时间的时间戳；为了简单起见，我们在下面的描述中不写时间戳。直观上，FW表记录了文件和字标识符之间的关联；Adj表记录给定单词列表中文件的邻接信息。

        注意，我们的具体构造对于给定文件有两个不同的标识符：文件的密文存储在搜索操作期间显示的文件指针下，但是索引中的文件信息存储在文件的伪随机函数输出下的中。然而，该方案的操作立即向对手揭示了这些值之间的相关性，因此在我们的泄漏描述中，我们不区分这两种类型的文件标识符。我们结构中的操作编写了以下值：

        Search将单词w的标识符作为输入，并将一组文件标识符返回给客户端。所以，对于每个文件f通过搜索返回，我们的方案将行写入FW表。注意，服务器然后为每个文件-单词对写一行。

        Add将包含文件f的标识符的add标记作为输入，并为与该文件相关联的一组单词添加单词信息。像Search一样，Add为与Add标记中的文件相关联的每个单词w写入元组。

        然而，附加地，Add操作向服务器揭示f是否是包含w的唯一文件。如果服务器先前已经执行了揭示与列表forw 的头部相关联的文件的操作，则Add将元组写入Adj表。在任一情况下， Add 将元组写入Adj表，以指示f是w的列表的头节点。如果该单词还没有在索引中，则Add将写入Adj表

        Delete将包含文件f的标识符的删除令牌作为输入；这个令牌不包含任何特定于单词的信息。然而，在执行删除操作的过程中，服务器在索引中发现与文件相关联的每个单词的单词标识符（的搜索关键字）。因此，像搜索和添加一样，删除为与f相关联的每个单词w写入元组。

        当中的每个单词被删除时，它揭示了它的邻居在搜索数组中的位置。为了证明的目的，我们说这种情况下的泄漏由列表中前一个和下一个节点的文件标识符组成。设与这些节点相关的文件分别为和。然后，服务器将 和写入Adj表(在每种情况下，如果没有前一个或下一个邻居，它将写入)。我们可以使用这个框架来比较我们的方案的泄漏和以前方案的泄漏。SSE-1不提供添加或删除操作，但它写入的值与我们的方案在搜索中写入FW表的值相同。另一个表（以及Add和Delete中对FW的额外写入）弥补了我们方案中的额外泄漏。

        Sedghi等人[23]的方案是动态的，但泄漏的信息比我们的构造少。在他们的方案中搜索显示搜索的单词，但不显示返回文件的标识符，因为该信息被隐藏在一个位数组中，每个文件一位。这可以通过向FW表写入一个字标识符来表示，该字标识符的值为文件标识符的。他们的方案为添加和删除对FW表执行相同的写入，因为每个添加或删除操作揭示了文件的标识符，并且通过它在它们的索引中修改的位置揭示了字标识符。然而，他们的方案从不将邻接信息写入Adj表：它隐藏了所有邻接信息，代价是需要每个字的存储和通信复杂性，这与可以存储在它们的索引中的文件的最大数量成线性关系。

        定理和证明。在陈述我们的安全理论之前，我们对我们的方案的泄漏提供一个更正式和简洁的描述：

        泄漏的定义为：，其中id是上面描述的标识符函数。

        泄漏的定义为：，其中是访问模式，它本身被定义为序列。

        泄漏的定义为：，其中如果出现在中的至少一个文件中，被设为1，否则为0。

        泄漏的定义为：，其中，和是之前和之后第一个包含的文件（在文件的自然排序中）的身份。如果之前和之后没有包含这个词的文件，那么和分别返回。这里我们假设标识符/指针三元组的顺序是根据单词在f中出现的顺序。

        在下面的定理中，由于篇幅不足，其证明被省略，我们表明我们的构造在随机预言机模型中对于上述泄漏是的。

        定理5.1。如果SKE是，而且如果、和是伪随机，然后如上所述的SSE是的，可以抵御随机预言机模型中的自适应选择关键字攻击。

        在一个非常高的水平上，我们的构建工程的安全证明如下：模拟器根据从接收到的信息，生成一个模拟加密索引和一个模拟密文序列，其中包括搜索数组中的元素个数、文件个数、关键字个数和每个文件的长度。模拟索引的构造方法与实际加密索引类似，不同之处是加密被零字符串（长度适当）的加密所取代，的输出被随机值所取代。加密方案的和的伪随机性将保证产生的与真实的加密索引不可区分。模拟的文件加密以相同的方式进行模拟（即，用全零字符串的加密替换密文），加密方案的保证了不可区分性。

        模拟搜索、添加和删除令牌更加复杂，需要模拟器跟踪这些操作显示的信息之间的各种依赖关系。这是因为模拟器创建的令牌必须彼此一致，否则模拟可能会被对手检测到。为此，我们的证明利用了一组重要的技术，以便模拟器能够跟踪依赖关系。由于篇幅不足，本作品的完整版中会出现完整的证明。

        关于我们对随机预言机的使用。正如在[8]中观察到的，设计的SSE方案的主要困难之一是可以选择关键字作为加密索引和以前搜索结果的函数。这使得验证安全性变得困难，因为模拟器在接收任何搜索结果之前必须能够模拟加密索引。[8]展示了如何克服这个障碍，后来[6]给出了一种基于简单的私有密钥非提交加密方案的更有效的方法。在较高的层次上，这两种构造方案都允许模糊性，也就是说，模拟器可以生成一个“假的”加密索引，然后，当给出一个搜索结果时，可以生成一个适当的令牌（即，当与假索引一起使用时，将产生正确的搜索结果的令牌）。不幸的是，[8]和[6]的技术在我们的环境中不起作用。主要的问题是，在动态环境中，有些情况下，前面描述的含混程度不够。

        特别是，考虑这样一个对手，它首先搜索关键字，然后添加包含的文件，最后再次搜索。要了解为什么前面的含混级别还不够，请注意，在第一次搜索之后，模拟器被提交给的令牌。现在，在对手添加带有的文件之后，模拟器需要模拟该文件的添加令牌。然而，模拟器不知道文件是什么，甚至不知道它包含，所以它不能产生一个正常工作的令牌，即，它模拟的添加令牌不能对加密索引做出任何有意义的更改。问题是，在对手对执行第二次搜索之后，他希望这次新的搜索至少比上一次搜索显示一个新的结果。特别是，搜索现在还应该显示新文件的标识符。但是，如果添加令牌在第二阶段不能正确地修改加密索引，如果模拟器在第三阶段不能发送新令牌（因为它已提交），那么模拟器如何保证对手将获得更新的搜索结果?

        我们通过构造一个方案来克服这个问题，该方案允许模拟器在对手执行搜索算法期间修改搜索的结果。注意，这与[8]和[6]的方法不同，[8]和[6]通过创建特殊设计的令牌来操纵对手的搜索结果。我们通过使用随机预言模型来做到这一点。在非常高的级别上，我们设计加密索引的方式要求对手在搜索算法的各个步骤中查询一个随机的预言机。然后，模拟器能够以适合它的方式对随机预言的响应进行编程，并能够确保搜索的执行产生它想要的结果。

        为了证明算法的可行性，我们在微软加密API：下一代（CNG）上用c++实现了SSE。我们的实现使用§4中描述的算法。我们的协议的加密原语使用CNG。加密是128位AES-CBC的CNG实现，哈希函数是SHA-256的CNG实现。SSE采用了两个随机的预言机，使用CNG的HMACSHA256实现（使用了Bellare、Canetti和Krawczyk首先描述的HMAC结构）。传递给随机预言机的第一个参数被用作HMAC的密钥，第二个参数被用作HMAC的输入。

        实现SSE的系统执行两类时间密集型操作：加密计算和系统操作（例如，网络传输和文件系统访问）。分离的加密系统的成本费用（底层系统之间会有所不同），我们构建了一个测试框架，对一组文件执行加密计算但不跨网络传输这些文件或招致的成本从磁盘存储和检索索引信息；所有操作都在内存中执行。我们还忽略了为文件生成纯文本索引的成本，因为索引算法的选择和实现与SSE是正交的。

        SSE中的加密操作需要大量不同的时间来执行。因此，为了评估SSE，我们在系统上执行了微基准测试和完整的性能测试，并将每个测试分解为其组件算法。微基准测试用于解释整个系统的性能。

        这些实验是在运行windows Server 2008 R2的Intel Xeon 2.26 GHz（L5520）CPU上进行的。所有的实验都在处理器上单线程运行。实验中给出的每个数据点是10次执行的平均值，误差条提供了样本标准差。

        在所有微基准测试中，测量单位都是文件/单词对：对于给定的文件，文件/单词对的集合由所有唯一的对组成，使得是索引中与相关联的单词。跨文件集合中所有文件的所有此类元组的集合正是该集合的关键字索引中的条目集合。

        我们为实验选择了三组真实世界的数据。第一组选自安然邮件；我们提取了电子邮件的一个子集，并使用这个原始子集中逐渐减少的子集作为文件集合，具有不同数量的文件/单词对。第二套包括Microsoft Office文档（使用Word、PowerPoint和Excel文件类型），由Microsoft的一个业务小组用于内部规划和开发。与电子邮件类似，我们选择这个集合中逐渐减少的子集作为更小的文件集合。第三个数据集由媒体文件组成，这些文件几乎没有可索引的单词，但文件大小很大。该集合由MP3、视频、WMA和JPG文件组成，它们生成的数据集大小与文档集合中的数据集相同。为了索引电子邮件、文档和媒体，我们使用了一个索引器，它利用Windows中的filter插件从每个文件中提取唯一的单词。索引器还从NTFS文件系统中提取文件的属性，例如Microsoft Word文档的作者，或MP3文件的艺术家或流派。

        为了确定SSE的性能，我们生成了综合指数，并对它们执行搜索和更新操作。对于搜索，我们选择了在大多数文件中都存在的单词。我们删除并添加回一个索引中唯一单词数量最多的文件。对于我们的微基准，我们只与电子邮件和文档数据集进行比较，因为媒体数据集索引大小对于有用的比较来说太小了。

        我们从一对Zipf分布中生成合成索引，参数= 1.1；一个分布包含随机生成的文件，另一个分布包含单词（在我们的例子中，单词是简单的用字符串表示的数字：“0”、“1”、“2”等）。生成的合成文件集合如下所示。首先，测试代码从Zipf文件分发中绘制了一个文件（我们的抽样采用了Horman和Derflinger的算法ZRI)。第二，测试代码了单词词分布，直到发现一个词并没有在指数。然后这个词添加到索引信息为和画了另一个文件重复这个过程，直到给定的文件/词对生成。这个过程对应于编写一组Zipf-distributed大小的文件，并包含Zipf-distributed单词，这样整个文件集合就包含给定数量的文件/单词对。

        图4显示了SSE生成索引的成本，表示为每个文件/单词对的成本；这些是索引一组文件后执行的操作的时间（索引这些文件所需的总时间，见§6中的图5）。它们的数量在1.4万到150万之间。合成数据用“Zipf”标记，安然数据用“Email”标记，文档数据用“Docs”标记。每个文件/单词对的成本是一个平摊值：它是由每次实验的完整执行时间除以文件/单词对的数量确定的。

        图4中每个文件/字对的成本很小：每对降低到大约35μs。较低的成对数量会导致较高的每对成本，因为向索引添加新单词和新文件的开销是恒定的，而且在这种情况下，成本不会分摊到相同数量的成对上。

        电子邮件和文档数据验证了我们的合成模型，并且对于具有大致相同数量的文件/单词对的数据点，它们与该模型密切对应（在10%以内）。这表明，至少对于大量的对，Zipf模型导致了与电子邮件和文档中包含的英文文本相同的SSE性能。综合数据测试了SSE算法对文件/字分布细节的敏感性；对文件集合的实验仅限于始终对文件的相同唯一单词赋值进行操作，但对合成数据的不同实验包含不同的文件/单词对集，尽管它们来自相同的分布。由于我们的合成结果与来自真实数据集的结果非常接近，因此正如预期的那样，这种灵敏度很低。

        SSE算法的微基准测试执行时间不依赖于索引中文件/单词对的数量。而且它们每个唯一单词的成本本质上是独立于每次操作中唯一单词（或文件）的总数量的（对一个非常小的常量成本取模）。因此，我们只给出这些操作的每个字（或每个文件）时间。表2显示了每个操作的成本。为了便于说明，我们只显示在文档数据集上执行SSE算法的数字；电子邮件数据集的数字与合成数据相似。搜索令牌生成需要恒定的时间（平均35μs），与搜索返回的文件数量无关。结果表明，客户端搜索和文件添加和删除是高效实用的，即使是常见的单词，或包含许多独特的单词的文件。

        为了评估SSE的整体性能，我们在邮件、文档和媒体数据集上运行§4中指定的SSE算法。请注意，图上显示的所有算法都有非零成本，但在某些情况下，与操作的其他部分的成本相比，成本非常小，以至于在图上看不到这个成本。

        图5显示了加密操作的结果，该操作在所有算法中花费的时间最长。请注意，除了客户端在存储数据之前必须执行的索引之外，整个加密协议都是执行的。

        图5显示了电子邮件数据和文档数据之间的差异。安然电子邮件是纯文本文件的集合，包括电子邮件头，因此文件的几乎每个字节都是将被索引的单词的一部分。因此，每个小文件包含很多单词，文件/单词对占数据集大小的比例很高。相比之下，Microsoft Office文档可能包含大量没有索引的格式化和可视化组件（如图像）。因此，文件/单词对与文件大小的比率要低得多。这两个数据集都代表了办公使用的一种常见情况:我们的结果表明，SSE索引生成对于大型文本集合比对于常见的办公文档格式需要更多的时间。最后，对于媒体文件，可索引字与文件大小的比率几乎为零。

        图4的微基准测试结果显示，对于大型数据集，SSE索引生成性能在文件/单词对的数量上呈线性变化。因此，对于大小为16GB的电子邮件数据集（完全由基于文本的电子邮件组成：即，不包含附件的电子邮件），初始索引成本大约为15个小时（这可以在计算机空闲期间在一天中执行）。在这个初始的索引之后，添加和删除电子邮件将会很快。

        为了评估剩余SSE算法的代价，我们进行了实验，给出了任何操作代价的上界。SSE的上界。搜索是对包含在大多数文件中的单词进行搜索。我们的更新操作使用磁盘上字节最多的文件。

        由于搜索是针对大多数文件索引的单词执行的，搜索所需的总时间取决于单词在文件中的流行程度：媒体文件几乎没有单词，甚至在500MB的内容中，而有些单词出现在每封电子邮件中。图6给出了服务器执行搜索所需的时间，给定一个搜索令牌（我们忽略了生成一个搜索令牌的成本，因为它是一个以微秒为单位的小常数）。SSE的搜索成本很小，即使是电子邮件索引。然而，即使是最长的搜索也只需要大约50毫秒来完成。而对于大型媒体收藏，搜索时间几乎可以忽略不计。

        图7显示了添加文件的执行时间。操作的成本被分为几个部分：“Enc”指的是加密新文件“SSE”所需的时间。“AddToken”指的是文件中索引的单词的添加令牌的客户端生成，以及“SSE”。指的是使用Add令牌更新索引的服务器。添加文件的成本主要落在客户机上：主要的成本是SSE添加令牌生成和文件加密，两者都在客户机上执行。在添加操作占主导地位的用例中（例如索引加密的电子邮件），这允许服务器轻松地支持许多客户机，因为执行添加的客户机也执行大多数计算。

        图8中删除文件时出现了类似的情况。上交所的标签”。DelToken”指的是客户端生成的删除令牌，以及“SSE”。“Del”指的是使用删除令牌更新索引的服务器。对于添加，删除操作高效实用;对最大文件的每次操作大约需要半秒。

        可搜索加密是一种重要的加密原词，它受到了云存储服务（如Dropbox、Microsoft Skydrive和Apple iCloud）以及公共云存储基础设施（如Amazon S3和Microsoft Azure storage）的流行的推动。然而，任何实际的SSE方案都应该满足某些特性，如亚线性（最好是最优）搜索、自适应安全性、紧凑性以及支持文件添加和删除的能力。

        在这项工作中，我们给出了第一个SSE结构来实现所有这些特性。此外，我们实施了我们的方案并对其进行了性能评估。我们的实验表明，我们的构建是高效的，并准备部署。

感谢

作者非常感谢Jason Mackay编写了用于实验的索引器。第二作者得到了布朗大学Kanellakis奖学金和英特尔的安全计算STC的部分支持。