《基于加密云数据的隐私保护多关键词排序搜索》文章阅读

随着云计算的出现，数据所有者开始将复杂的数据管理系统从本地站点外包到商业公共云，以获得更大的灵活性和经济节约。但是为了保护数据隐私，敏感数据在外包前必须加密，这就淘汰了传统的基于明文关键字搜索的数据利用。因此，启用加密的云数据搜索服务至关重要。考虑到云中的大量数据用户和文档，有必要允许搜索请求中有多个关键字，并按照与这些关键字的相关性顺序返回文档。可搜索加密的相关工作主要集中在单个关键字搜索或布尔关键字搜索，很少对搜索结果进行排序。在本文中，我们首次定义并解决了云计算（MRSE）中加密数据的隐私保护多关键字排序搜索的挑战性问题。我们为这样一个安全的云数据利用系统建立了一套严格的隐私要求。在各种多关键字语义中，我们选择“坐标匹配”的有效相似性度量，即尽可能多的匹配，来捕获数据文档与搜索查询的相关性。我们进一步使用“内积相似性”来定量评估这种相似性度量。我们首先提出了一个基于安全内积计算的MRSE的基本思想，然后给出了两个显著改进的MRSE方案，在两种不同的威胁模型下实现了各种严格的隐私要求。为了改善数据搜索服务的搜索体验，我们进一步扩展了这两个方案，以支持更多的搜索语义。对所提方案的保密性和效率保证进行了深入的分析。在真实数据集上的实验进一步表明，所提出的方案确实引入了较低的计算和通信开销。

云计算是将计算作为一种工具的长期梦想愿景，云客户可以将他们的数据远程存储到云中，以便从可配置计算资源的共享池中享受按需高质量的应用程序和服务[2]，[3]。其巨大的灵活性和经济节约促使个人和企业将其本地复杂的数据管理系统外包到云中。为了保护数据隐私和防止云中及云外未经请求的访问，敏感数据，例如电子邮件、个人健康记录、相册、税务文档、金融交易等，在外包给商业公共云之前可能必须由数据所有者进行加密[4]；然而，这淘汰了传统的数据利用基于明文关键字搜索的服务。下载所有数据并在本地解密的简单解决方案显然是不切实际的，因为在云规模的系统中有巨大的带宽成本。此外，除了消除本地存储管理之外，将数据存储到云中没有任何意义，除非它们可以被轻松地搜索和利用。因此，探索基于加密云数据的隐私保护和有效搜索服务至关重要。考虑到云中潜在的大量按需数据用户和大量外包数据文档，这个问题尤其具有挑战性，因为同时满足性能、系统可用性和可伸缩性的要求也是极其困难的。
一方面，为了满足有效的数据检索需求，大量的文档要求云服务器进行结果相关性排序，而不是返回无差别的结果。这种分级搜索系统使数据用户能够快速找到最相关的信息，而不是费力地在内容集合中对每个匹配进行分类[5]。排名搜索还可以通过只发回最相关的数据来优雅地消除不必要的网络流量，这在“按使用付费”的云计算中是非常可取的。然而，为了保护隐私，这种排序操作不应该泄漏任何与关键词相关的信息。另一方面，为了提高搜索结果的准确性以及增强用户的搜索体验，这种排名系统也有必要支持多关键词搜索，因为单关键词搜索往往会产生过于粗糙的结果。作为当今网络搜索引擎（例如，谷歌搜索）所表明的一种普遍做法，数据用户可能倾向于提供一组关键字而不是仅仅一个关键字作为他们检索最相关数据的搜索兴趣的指示符。并且搜索请求中的每个关键词能够帮助进一步缩小搜索结果的范围。“坐标匹配”[6]，即尽可能多的匹配，是这种多关键字语义之间的有效相似性度量，以精炼结果相关性，并且已经在明文信息检索(IR)社区中广泛使用。然而，由于固有的安全和隐私障碍，包括各种严格的要求，如数据隐私、索引隐私、关键字隐私等，如何在加密云数据搜索系统中应用它仍然是一项非常具有挑战性的任务（参见3.2节）。
在文献中，可搜索加密[7]、[8]、[9]、[10]、[11]，[12]，[13]，[14]，[15]是一种有用的技术，它将加密数据视为文档，并允许用户安全地搜索单个关键字并检索感兴趣的文档。然而，将这些方法直接应用于安全的大规模云数据利用系统不一定合适，因为它们是作为密码原语开发的，并且不能适应如此高的服务级别要求，如系统可用性、用户搜索体验和轻松的信息发现。尽管最近提出了一些设计来支持布尔关键字搜索[16]、[17]、[18]、[19]、[20]，[21] ，[22]，[23]，[24]作为丰富搜索灵活性的尝试，它们仍然不足以为用户提供可接受的结果排序功能（参见第7节）。我们早期的工作[25]，[26]已经意识到了这个问题，并且提供了对加密数据的安全排序搜索问题的解决方案，但是只针对由单个关键字组成的查询。如何设计一个有效的加密数据搜索机制，支持多关键字语义而不破坏隐私，仍然是一个具有挑战性的公开问题。
在本文中，我们首次定义并解决了加密云数据（MRSE）上的多关键字排序搜索问题，同时在云计算范式中保持严格的系统级隐私。在各种多关键字语义中，我们选择“坐标匹配”的有效相似性度量，即尽可能多的匹配，来捕获数据文档与搜索查询的相关性。具体来说，我们使用“内积相似性”[6]，即在文档中出现的查询关键词的数量，来定量评估该文档与搜索查询的相似性度量。在索引构建期间，每个文档与作为子索引的二进制向量相关联，其中每个比特代表相应的关键词是否包含在文档中。搜索查询也被描述为一个二进制向量，其中每一位表示相应的关键字是否出现在该搜索请求中，因此相似性可以通过查询向量与数据向量的内积来精确地测量。然而，直接外包数据向量或查询向量会侵犯索引隐私或搜索隐私。为了应对在不破坏隐私的情况下支持这种多关键字语义的挑战，我们提出了使用安全内积计算的MRSE的基本思想，该思想改编自安全的k-最近邻（KNN）技术[27]，然后以逐步的方式给出了两个显著改进的MRSE方案，以实现各种严格的隐私要求在两种攻击能力增强的威胁模型中。我们的贡献总结如下：

1. 我们首次探索了加密云数据上的多关键字排序搜索问题，并为这样一个安全的云数据利用系统。
2. 我们提出了两个基于“坐标匹配”相似性度量的MRSE方案，同时满足两个方案不同的隐私要求不同的威胁模式。
3. 我们研究了我们的排序搜索机制的一些进一步增强，以支持更多的搜索语义和动态数据操作。
4. 对所提出方案的隐私和效率保证进行了深入的分析，在真实数据集上的实验进一步表明，所提出的方案确实引入了较低的计算和通信开销。

与本文的初步版本[1]相比，这个期刊版本提出了两个新的机制来支持更多的搜索语义。该版本还研究了机制设计中对数据/索引动态的支持。此外，我们还增加了对两个新方案的分析和评价，对实验工作进行了改进。除了这些改进，我们还增加了对安全内积和隐私部分的分析。

本文的其余部分组织如下：在第2节，我们介绍了系统模型、威胁模型、我们的设计目标和初步的。第3节描述了MRSE框架和隐私要求，随后的第4节描述了提议的方案。第5节给出了模拟结果。我们在第6节讨论了单个和布尔关键字可搜索加密的相关工作，并在第7节总结了论文。

问题定式化

系统模型

考虑涉及三个不同实体的云数据托管服务，如图1所示：数据所有者、数据用户和云服务器。数据所有者有一组数据文档以加密的形式外包给云服务器。为了启用搜索功能以有效利用数据，数据所有者在外包之前，将首先从构建加密的可搜索索引，然后将索引和加密的文档集合都外包给云服务器。为了在文档集合中搜索给定的关键字，授权用户通过搜索控制机制获取相应的陷门例如，广播加密[10]。当从数据用户接收到T时，云服务器负责搜索索引并返回相应的加密文档集。为了提高文档检索的准确性，搜索结果应该由云服务器根据一些排序标准（例如，坐标匹配，稍后将介绍）进行排序。此外，为了降低通信成本，数据用户可以连同陷门T一起发送可选的数字k，使得云服务器仅发送回与搜索查询最相关的top-k个文档。最后，使用访问控制机制[28]来管理给予用户的解密能力，并且可以根据插入新文档、更新现有文档和删除现有文档来更新数据集合。

威胁模型

在我们的模型中，云服务器被认为是“诚实但好奇的”，这与云安全的相关工作一致[28]，[29]。具体来说，云服务器以“诚实”的方式运行，并正确地遵循指定的协议规范。然而，推断和分析其存储中的数据（包括索引）以及在协议期间接收的消息流以了解附加信息是“令人好奇的”。基于云服务器所知道的信息，我们考虑如下两种具有不同攻击能力的威胁模型。
已知密文模型。在这个模型中，云服务器应该只知道加密的数据集C和可搜索的索引，这两者都是从数据所有者那里外包的。已知背景模型。在这个更强大的模型中，云服务器应该拥有比已知密文模型中可访问的更多的知识。这种信息可以包括给定搜索请求（陷门）的相关关系，以及数据集相关的统计信息。作为这种情况下可能攻击的一个实例，云服务器可以使用已知的陷门信息结合文档/关键词频率[30]来推断/识别查询中的某些关键词。

为了在上述模型下实现有效利用外包云数据的分级搜索，我们的系统设计应该同时实现如下安全性和性能保证。

• 多关键字排序搜索。设计允许多关键字查询的搜索方案，并为有效的数据检索提供结果相似性排序，而不是返回无差别的结果。
• 保护隐私。以防止云服务器从数据集和索引中获知额外的信息，并满足隐私要求。
• 效率。上述关于功能和隐私的目标应该以低的通信和计算开销来实现。
  

记号

• ——明文文档集合，表示为m个数据文档的集合。
• ——存储在云服务器中的加密文档集合，记为。
• ——字典，即由n个关键字组成的关键字集，记为。
• ——与相关的可搜索索引，记作，每个子索引是为建立的。
• ——的子集，表示搜索请求中的关键词，记为。
• ——搜索请求的陷门。
• ——所有文件根据与的相关度的排序id列表。
  

坐标匹配的初步研究

作为合取搜索和析取搜索的混合，“坐标匹配”[6]是一种中间相似性度量，它使用在文档中出现的查询关键词的数量来量化该文档与查询的相关性。当用户知道要检索的数据集的确切子集时，布尔查询可以很好地满足用户指定的精确搜索要求。然而，在云计算中，考虑到大量的外包数据，实际情况并非如此。因此，用户可以更灵活地指定表明其兴趣的关键字列表，并按照排名顺序检索最相关的文档。

MRSE的框架和隐私要求

在本节中，我们定义了加密云数据上的多关键字排序搜索（MRSE）的框架，并为这种安全的云数据利用系统建立了各种严格的系统级隐私要求。

MRSE框架

为了便于表示，对数据文档的操作没有在框架中示出，因为数据所有者可以容易地采用传统的对称密钥加密来加密数据，然后外包数据。以索引和查询为重点，MRSE系统由以下四种算法组成：

• 。以安全参数作为输入，数据所有者输出一个对称密钥作为。
• 。数据所有者根据数据集建立一个可搜索的索引，该索引I使用对称密钥SK加密后外包给云服务器。索引构建之后，文档集合可以独立加密和外包。
• 。该算法以中t个感兴趣的关键字作为输入，生成一个对应的活板门。
• 。当云服务器接收到一个的查询请求时，它在陷门的帮助下对索引进行排序搜索，最后返回，即top-k文档按照与的相似度排序的排序id列表。

搜索控制和访问控制都不在本文的讨论范围之内。前者是为了规范授权用户如何获取陷门，而后者是为了管理用户对外包文档的访问。

隐私要求

相关文献（如可搜索加密）中代表性的隐私保证是，服务器应该只知道搜索结果。有了这个一般的隐私描述，我们探索并建立了一套专门针对MRSE框架的严格的隐私要求。

在数据隐私方面，数据所有者可以在外包之前借助传统的对称密钥加密技术对数据进行加密，并成功防止云服务器窥探外包数据。关于索引隐私，如果云服务器从索引中推断出关键字和加密文档之间的任何关联，则它可以了解文档的主要主题，甚至是短文档的内容[30]。因此，应该构建可搜索的索引来防止云服务器执行这种关联攻击。虽然在相关文献中默认要求数据和索引隐私保证，但是查询过程中涉及的各种搜索隐私要求更加复杂并且难以处理，如下所述。
关键词隐私。由于用户通常更喜欢保持他们的搜索不被暴露给其他人，如云服务器，最重要的考虑是隐藏他们正在搜索的内容，即由相应的陷门指示的关键字。虽然陷门可以以加密的方式生成以保护查询关键词，但是云服务器可以对搜索结果进行一些统计分析以做出估计。作为一种统计信息，文档频率（即包含关键字的文档数量）足以以高概率识别关键字[31]。当云服务器知道数据集的一些背景信息时，该特定于关键词的信息可被用来对关键词进行逆向工程。

陷门不可链接性。陷门生成函数应该是随机化的，而不是确定性的。特别地，云服务器不应该能够推断任何给定陷门的关系，例如，确定两个陷门是否由相同的搜索请求形成。否则，确定性陷门生成将使云服务器有利于累积关于不同关键字的不同搜索请求的频率，这可能进一步违反上述关键字隐私要求。因此，对陷门不可链接性的基本保护是在陷门生成过程中引入足够的不确定性。
访问模式。在分级搜索中，访问模式是搜索结果的序列，其中每个搜索结果是一组具有等级顺序的文档。具体而言，查询关键词集合的搜索结果被表示为，包括按照与的相关性排序的所有文档的id列表。然后，访问模式被表示为是顺序搜索的结果。
尽管有一些可搜索的加密技术可以工作，例如，[19]已经提出利用私人信息检索（PIR）技术[32]来隐藏访问模式，出于效率考虑，我们提出的方案没有被设计成保护访问模式。这是因为任何基于PIR的技术都必须“接触”服务器上的整个数据集，这在大规模云系统中是低效的。

为了有效地实现多关键字排序搜索，我们提出使用“内积相似性”[6]来定量评估有效的相似性度量“坐标匹配”具体地，是文档的二进制数据向量，其中每个比特表示相应关键字的存在，并且Q是指示感兴趣的关键词的二进制查询向量，其中每个比特表示查询中存在相应的关键字。因此，文档Fi与查询的相似性得分被表示为它们的二进制列向量的内积，即用于此目的的对于排序，云服务器必须能够比较不同文档与查询的相似性。但是，为了保持严格的系统隐私，数据向量、查询向量和它们的内积不应该暴露给云服务器。在本节中，我们首先提出了一个使用安全内积计算的MRSE的基本思想，它改编自安全的kNN技术，然后展示了如何在MRSE框架中以一步一步的方式对其进行显著改进，以针对不同的威胁模型保护隐私。我们进一步讨论支持更多的搜索语义和动态操作。

安全内积计算

在安全kNN方案[27]中，数据记录和查询向量之间的欧几里德距离用于选择k个最近的数据库记录。密钥由一个比特的向量和两个组成可逆矩阵为，其中是的数量每个记录的字段。首先，将每个数据向量和查询向量扩展为维向量和，其中第维分别设置为和1。此外，查询向量由随机数缩放为。然后将拆分成两个随机向量为，并且也被分成两个随机向量，如。请注意，向量的功能是作为分割指示器。即，如果的第j位为0，和被设置为与相同，而和被设置为两个随机数，使得它们的和等于；如果S的第j位为1，除了和对调外，分裂过程类似。分裂的数据向量对加密为，以及分裂查询向量对加密为。在接下来的步骤中，数据向量对和查询向量对的乘积，即作为欧几里德距离的指示器来选择k个最近邻。
因为MRSE使用了内积相似性代替欧几里德距离，我们需要在数据结构上做一些修改以适应MRSE框架。一种方法是通过消除维度扩展，最终结果变为作为的内积。而数据记录或查询向量的加密涉及复杂的矩阵和d维向量的两次乘法，最终的内积计算涉及到二维向量的两次乘法，具有复杂性为的两个d维向量的乘法。在已知的密文模型中，分裂向量S未知，所以和被认为是两个随机的d维向量。为了求解由数据向量加密产生的线性方程，我们在个数据向量中有个未知数，在。因为我们只有个方程小于未知数的数量，没有足够的信息来求解数据向量或。
类似地，和也被认为是两个随机的d维向量。为了求解由查询向量加密产生的线性方程，我们在两个查询向量中有个未知数，在。因为我们这里只有个方程小于未知数的数量，没有足够的信息来求解查询向量或。因此，我们认为，在没有密钥先验知识的情况下，无论是数据向量还是查询向量，在经过分裂和相乘等一系列过程后，都无法通过分析它们对应的密文来恢复。

MRSE I：已知密文模型下的隐私保护方案

适应的安全内积计算方案对于我们的MRSE设计来说不够好。主要原因是，所涉及的唯一随机性是陷门生成中的比例因子，它没有提供陷门不可链接性要求以及关键字隐私要求所要求的整个方案中的足够的不确定性。为了给MRSE提供更先进的设计，我们现在提供我们的MRSE_I方案如下

MRSE_I方案

在我们更高级的设计中，我们不是简单地删除查询向量中的扩展维度，而是保留这个维度扩展操作，但是为每个查询向量中的扩展维度。这种新增加的随机性预计会增加云服务器学习接收到的陷门之间的关系的难度。此外，如关键字隐私要求中所述，还应在搜索结果中仔细校准随机性，以混淆文档频率并减少关键字重新识别的机会。在最终的相似性得分中引入一些随机性是实现我们这里所期望的一种有效方式。更具体地说，与查询向量中包含的随机性不同，我们在每个数据向量中插入一个伪关键字，并为其分配一个随机值。

每个单独的向量被扩展到维，而不是，其中随机变量表示伪关键字存储在扩展维度中。实现对加密数据的多关键字排序搜索的整个方案如下：

• 。数据所有者随机生成一个位向量作为和两个可逆矩阵。秘密密钥是三元组的形式，如。
• 。数据所有者生成一个每个文档的二进制数据向量，其中每个二进制位表示相应的关键字是否出现在文档中。随后，通过在上应用维度扩展和分裂过程来生成每个明文子索引。这些过程类似于安全kNN计算中的过程除了中的第个条目被设置为一个随机数，并且在维度扩展期间，中的第个条目被设置为1。我是因此等于。最后，子索引是为每个加密的文档。
• 。以中感兴趣的t个关键词作为输入，生成一个二进制向量，其中每个比特指示是真还是假。首先将Q扩展到设置为1的n+1维，然后通过随机数进行缩放，最后扩展到作为的维向量，其中最后一个维设置为另一个随机数t。因此，等于。在应用上述相同的分裂和加密过程后，陷门生成为。
• 。利用陷门，云服务器如在（1）中那样计算每个文档的相似度分数。WLOG，我们假设。对所有分数排序后，云服务器返回top-k排名id列表。

将t引入查询向量，将引入每个数据向量，最终的相似性得分将是

请注意，在最初的情况下，最终的分数只是，它保留了对相同关键字的两个查询的比例关系。但是由于和的随机性，这样的问题在我们改进的方案中不再有效，这清楚地表明了我们的MSRE_I机制的有效性和改进的安全强度。

分析

我们从第二节描述的设计目标的三个方面来分析这个MRSE_I方案。功能和效率。假设查询的数量出现在文档中的关键词是。从（1），最终的相似性得分为是的线性函数，其中系数设置为正随机数。然而，由于随机因子被引入作为相似性得分的一部分，基于排序相似性得分的最终搜索结果可能不如原始方案中的结果准确。为了考虑到搜索精度，我们可以让遵循正态分布，其中标准差用作搜索准确性和安全性之间的灵活折衷参数。从有效性的考虑，期望更小，以获得更高的精度，表明检索到的文档纯度好。为了定量地评估搜索精度，我们将一个度量值设置为精度，以捕获返回的top-k文档中包含在真实top-k列表中的部分。对真实世界数据集的详细准确度评估将在第5节中给出。
至于效率，我们基于内积的MRSE方案从性能的角度来看是一个优秀的方法。在像BuildIndex或Trapdoor这样的步骤中，每个子索引或陷门的生成过程包括一个矩阵和一个维向量的两次乘法。在查询中，通过两个维向量的两次乘法来计算最终的相似性得分。
隐私。在数据保密方面，传统的对称密钥这里可以适当地使用加密技术，但这不在本文的讨论范围之内。如果秘密密钥被保密，则索引隐私被很好地保护，因为这种向量加密方法已经在已知密文模型中被证明是安全的[27]。尽管相比之下，我们给向量增加了两个维度适应的安全内积计算，作为的等式的数量仍然小于作为m个数据中个未知数的和的未知数的数量的向量和未知数。利用分裂过程引入的随机性和随机数r、t，我们的基本方案可以为同一个查询生成两个完全不同的陷门。这种非决定性的陷门生成可以保证陷门不可链接性，这是相关的基于对称密钥的可搜索加密方案中未解决的隐私泄漏问题，因为陷门生成的确定性[10]。此外，通过为随机因子适当选择参数σ，甚至最终得分结果也可以被很好地混淆，从而防止云服务器了解给定陷门和对应的关键词。请注意，虽然从有效性的角度来看，σ应该很小，但小的σ会在最终的相似性得分中引入小的混淆，这可能会削弱对关键字隐私和陷门不可链接性的保护。如图2所示，具有较小σ的最终相似性得分的分布将使得云服务器能够了解更多关于原始相似性得分的统计信息，因此从隐私的考虑，σ应该设置得足够大。

Model：已知背景模型下的隐私保护方案

当云服务器知道一些关于外包数据集的背景信息时，例如，两个给定陷门的相关关系，某些关键字隐私可能不再由MRSE_I方案保证。这在已知的背景模型中是可能的，因为云服务器可以使用如下的尺度分析来推导关键字特定信息，例如文档频率，其可以进一步与背景信息相结合，以高概率识别查询中的关键字。在介绍了云服务器如何利用规模分析攻击来破坏关键字隐私之后，我们提出了一个更先进的在已知背景模型下保护隐私的MRSE方案。

规模分析攻击

给定分别用于查询关键字和的两个相关陷门和，当搜索任何三个时，将有两种特殊情况表1和表2中列出的文件。在这两种情况中的任何一种情况下，的最终相似性得分和的之间存在一个方程组，如下所示：

为此，虽然的确切值被加密为，但云服务器可以通过检查两个查询中所有最终相似度得分之间的如下等价关系，推断出这三个文档是否都包含或都不包含。

通过将三个文档扩展到整个数据集，云服务器可以进一步推导出关键字的两个可能的文档频率值。在已知的后台模型中，服务器可以通过参考关于数据集的关键字特定文档频率信息的方式识别关键字。

MRSE II计划

上面显示的隐私泄露是由数据向量中的随机变量oi的固定值引起的。为了消除任何特定文档中的这种固定属性，应该在每一个数据向量。所有向量被扩展到维，而不是，其中U是插入的伪关键字的数量。改进了中的细节，MRSE II方案介绍如下：

• 。数据所有者随机生成一个位向量为和两个位向量的可逆矩阵。
• 。中的第个条目，其中被设置为随机数在维度扩展期间。
• 。通过从中随机选择伪关键字，Q中的相应条目被设置为1。
• 。云服务器计算出的最终相似度得分等于，其中第v个虚拟关键字包含在V个被选中的关键字中。

分析

此外，假定每个遵循相同的均匀分布，其中均值为，方差为是。根据中心极限定理，个独立随机变量的和服从正态分布，均值是，方差是。让服从上面的正态分布，的值设置为和的值被设为以使和。通过该参数的设置，搜索精度在统计上与MRSE_I方案相同。

MRSE_I_TF

在“坐标匹配”排序原则中，文档或查询中关键字的存在在数据向量或查询向量中显示为1。事实上，有更多的因素会影响搜索的可用性。例如，当一个关键词出现在数据集中的大多数文档中时，该关键词在查询中的重要性小于出现在较少文档中的其他关键词。
类似地，如果一个文档在多个位置包含查询关键词，则用户可能更喜欢这个文档而不是只在一个位置包含查询关键词的另一个文档。为了在搜索过程中捕获这些信息，我们使用向量空间模型中的加权规则来计算相似性，其中TF（或术语频率）是给定术语或关键字（我们将在下文中互换使用它们）在文件中出现的次数（以测量该术语在特定文件中的重要性），IDF（或逆文档频率）是通过将整个集合中的文件数量除以包含该术语的文件数量（以测量该术语在整个集合中的整体重要性）来获得的。在加权方案的数百种变体中，没有一种组合的效果优于其他任何一种[33]。因此，没有失去一般性，我们选择一个例子公式是通常使用并广泛见于文献中（参见[5，第4章]），用于相关性分数计算

这里F表示文件F中关键字W的TF；f表示包含称为文档频率的关键字的文件的数量；m表示集合中文件的总数；并且是文件的欧几里得长度，通过下式获得，起标准化作用的。

为了在服务器端计算如（4）所示的相关性分数，我们提出如下新的搜索机制MRSE_I_TF，其修改了先前方案MRSE_I中的相关数据结构。至于字典，文档频率fj被附加到每个关键字，其将被用于生成查询向量。在BuildIndex中，对于出现在文档中的每个关键字，数据向量中相应的元组从二进制值1变为归一化的项频率，即。同样查询向量Q将相应的条目从1更改为。最后，相似性得分如下：

因此，文档和查询在可以通过计算子索引和陷门的内积来评估文档向量和查询向量之间的夹角的余弦项t。尽管这种相似性度量在索引构建期间引入了更多的计算成本和陷门生成技术，它能捕获更多与文档内容相关的信息，并返回更好的用户感兴趣的结果。正如我们将在第5节中看到的，在BuildIndex和与整体成本相比，陷门相对较小。此外，BuildIndex是整个方案的一次性计算。

MRSE_II_TF

这里，尽管中的一些条目已经从二进制值1改变为归一化的术语频率，但是4.3节中呈现的尺度分析攻击仍然在已知的背景模型中部分地起作用。与上一节中的设置类似，第一个查询包含两个关键字而第二个查询包含三个关键字。以三个文档为例，第一个关键字出现在两个文档和中，第二个关键字出现在文档中。请注意，这次攻击和以前的攻击有一些不同。如果第三个关键字出现在如表1所示的这三个文档的每一个中，则这样的等价这里，这些文档之间不存在（3）所示的长度关系。这里我们只考虑第三个关键字没有出现在这三个文档中的情况。最终的相似性得分如（6）所示。
回想一下4.3节中介绍的规模分析攻击，它是由每个数据向量中的随机变量的固定值引起的，该固定值在这里保持不变。从（6）中，云服务器仍然可以推导出（3）中呈现的等价关系。因此，文档频率可以暴露给云服务器，并进一步用于在已知的背景模型中识别该关键字。为此，我们可以采用与MRSE_II中提出的解决方案相同的解决方案来建立新的机制，如MRSE_II_TF，其中将更多的伪关键字而不是仅仅一个插入到数据向量中。

支持数据动态

数据集外包给云服务器后，除了检索之外还可以更新[34]。随着对数据文档的更新操作，支持可搜索索引中的分数动态因此具有实际重要性。虽然我们考虑了插入新文档、修改现有文档和删除现有文档这三种动态数据操作，但是对可搜索索引的相应操作包括生成新索引、更新现有索引和删除现有索引。由于动态数据操作也会影响对应关键词的文档频率，所以我们也需要更新字典。
对于在数据集中插入新文档的操作，新文档中可能会有一些新的关键字需要插入到字典中。请记住，在我们的方案中，每个子索引都具有与旧字典中的关键字数量相同的固定维度，因此直接的解决方案是从云服务器中检索所有子索引，然后在外包给云服务器之前解密、重建和加密它们。然而，这种方法为双方带来了大量的计算和通信成本，这在“按使用付费”的云模式中是不切实际的。为了减少这样巨大的开销，我们在字典中保留了一些空白条目，并将每个数据向量中相应的条目设置为0。如果在插入新文档的情况下字典需要索引新的关键词，我们只需用新的关键词替换字典中的空白条目，并基于更新的字典为新文档生成子索引。存储在云服务器上的其他文档及其子索引不受影响，因此与以前一样。保留条目的数量用作平衡存储成本和系统可扩展性的折衷参数。
当修改现有文档时，还会从云服务器中检索相应的子索引，然后根据外包前的词频进行更新。如果在修改操作过程中引入了新的关键字，我们将使用在之前的插入操作中提出的相同方法。作为修改的特殊情况，删除现有文档的操作引入较少的计算和通信成本，因为它只需要更新这些文档包含的所有关键词的文档频率。

技术性能分析

在这一节中，我们演示了一个彻底的实验在真实世界数据上评估所提出的技术设置：安然电子邮件数据集[35]。我们随机选择不同数量的电子邮件来建立数据集。整个实验系统用C语言在一台搭载Intel Xeon处理器2.93 GHz的Linux服务器上实现。这采用了由数字配方构成的公用程序计算矩阵的逆矩阵。我们的性能技术是根据四个效率来评估的提出的MRSE方案，以及之间的权衡搜索精度和隐私。

精确和隐私

索引结构