17250用于具有线性加性排名评分的多词前K个搜索的隐私和效率权衡0Daniel Agun，Jinjin Shao，Shiyu Ji，StefanoTessaro，TaoYang加利福尼亚大学圣塔芭芭拉分校计算机科学系0摘要0本文提出了一种具有线性加性评分的隐私排名方案，用于在规模适中的云数据集上进行高效的前K个关键字搜索。该方案通过提出单轮客户端-服务器协作，基于带有随机掩码的盲目特征权重进行服务器端部分排序，以在隐私和效率之间进行权衡。客户端预处理包括使用分块的帖子进行查询分解，以促进更早的范围交集和对服务器端键值存储的快速访问。服务器端查询处理通过可选的特征匹配处理特征向量的稀疏性，并使用查询相关的分块宽度随机掩码对产生太多匹配文档的查询进行结果过滤。本文详细介绍了索引和运行时连词查询处理，并通过五个不同大小的数据集评估了该方案的准确性、效率和隐私权衡。0ACM参考格式：Daniel Agun，Jinjin Shao，Shiyu Ji，StefanoTessaro，TaoYang加利福尼亚大学圣塔芭芭拉分校计算机科学系。2018年。用于具有线性加性排名评分的多词前K个搜索的隐私和效率权衡。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，10页。https://doi.org/10.1145/3178876.318610401 引言和相关工作0随着敏感信息越来越多地存储在云上，保护隐私成为用户采用基于云的信息服务（包括关键字搜索）的关键因素。云服务器通常被认为是“诚实但好奇”的：即这样的服务器在执行协议规范和托管程序时是诚实的，但在执行过程中或通过检查托管数据时可能观察和推断出客户端的私人信息。为了应对这样的服务器，可以使用可搜索加密[20,38]来进行保护隐私的服务器端查询匹配，包括使用单个关键字的[29,30]、使用OXT协议的连词多词[16-18]或使用分离多词[28]。包括OXT在内的研究不支持排序，而高效且安全的前K个排序是一个开放的研究问题，因为要同时实现这两个目标是具有挑战性的。进行服务器端保护隐私的前K个排序的主要挑战是高级排序涉及基于原始特征（在第2节中定义）的算术计算，并隐藏0本文根据知识共享署名4.0国际许可证（CC BY4.0）发表。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂。© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发表。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861040通过加密的特征信息，防止服务器进行有效的评分和结果比较。另一方面，未加密的特征值可能会导致隐私攻击[15, 26]。同态加密[22,33]是一种提供数据安全性的方法，同时允许服务器在不解密底层数据的情况下执行算术计算。例如，给定特征值f1和f2，使用同态加密E()的服务器可以使用E(f1)和E(f2)计算E(f1 +f2)，而不知道f1和f2。但是，当涉及到许多数字时，这种方案仍然不可行，因为每次加法或乘法都非常缓慢，更不用说使用同态加密计算得到的分数来比较两个结果的能力了。例如，同态加密不允许服务器有效地比较f1 + f2和f'1 + f'2，即使它可以安全地计算E(f1 +f2)和E(f'1 + f'2)。有序加密（例如[2, 9, 34,35]）允许服务器比较两个加密数字，而不知道实际数字，但它不支持加密数字的加法或乘法。另一个挑战是，高级排序考虑到各种特征（例如[1, 8, 12, 41, 42,49]），特征向量通常是稀疏的，有许多零值。如果明确存储零值，空间使用量可能会急剧增加。使用不恰当的防御措施的紧凑数据结构表示可能会泄漏有关索引的统计信息，从而可能导致泄漏滥用攻击[15, 26, 36]。之前关于基于相似性的安全排序的工作[13, 32,40]将每个基于TFIDF的特征向量转换为两个随机向量。索引构建在将特征向量与秘密矩阵相乘后构建正向索引。在线查询处理也使用矩阵乘法将给定的查询向量转换，并导出转换后的查询向量与所有加密文档向量的点相似度，这导致时间复杂度为O(T^2 +DT)，其中D是文档数，T是字典大小。将此模型扩展到考虑诸如词对之类的接近特征时，参数T变得非常大。倒排索引是不可行的，因为离线和在线矩阵变换与随机化产生密集的特征和查询向量，索引的空间成本变为O(DT)。[45,48]中的最新工作在考虑多用户数据所有权和动态文档更新的同时遵循上述矩阵变换。[13, 32,40]中测试的数据集只有数千个文档或术语，没有倒排索引支持的高搜索成本阻止了这种方法处理稍大一些的数据集。似乎不太可能开发一种完全安全的排序方案，而不依赖于重量级的密码学，如功能加密[22, 23,39]。在对快速响应时间有实际限制的情况下，服务器托管的算法必须使用受损的轻量级方案来计算排名分数并选择结果。我们的策略是解决这个私人排名开放问题0跟踪：Web Search and Mining WWW 2018，2018年4月23日至27日，法国里昂Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France17260问题是利用先前的可搜索加密研究，并在开发具有有限信息泄漏的高效方案中进行各种权衡。我们采用客户端-服务器协作方法，其中服务器进行高效匹配、加法评分和部分排名，而客户端进行查询预处理和最终的顶部结果选择。我们的设计仅使用一轮客户端-服务器通信，因为服务器和客户端之间的多轮主动通信（例如[25,31]）会产生更高的通信成本和响应延迟。我们假设客户端拥有一个数据集，并将相应的索引放置在云端，供客户端进行搜索。本文不考虑文档的多所有权[48]，并且假设云端的索引可以定期刷新，但不考虑动态索引更新[30, 45]。在[4,5]中关于查询混淆的工作保护了用户在进行私人网络搜索时发出的查询隐私，同时假设服务器拥有可搜索的数据，因此托管未加密的索引。我们的工作与不同的数据所有权假设相辅相成。我们的表述假设查询至少包含两个单词，因为通过在服务器上存储每个单词的加密预排名文档ID来处理单词查询相对容易。本文的贡献是针对这个开放的私人前K个搜索问题提出了一种具有线性加法评分的索引和在线搜索方案。它在处理适度大小的数据集时在部分服务器端结果过滤方面进行了权衡。它比以前的基准解决方案[13]快几个数量级，同时适应了四个先前开发的排名信号类别。由于页面限制，本文列出了正式属性，但没有提供详细的证明。02问题定义和设计考虑0问题定义：给定客户拥有的具有T个特征的D个文档特征向量，每个文档d都有许多特征值，表示为fdi，客户端构建了一个可搜索的索引并将其放置在服务器上。我们专注于开发一种索引和前K个搜索方案，以便服务器可以在不知道合理响应时间内的底层特征值的情况下访问加密的匹配文档特征并计算它们的排名。当特征不参与搜索时，服务器也不应该学习有意义的信息。我们假设每个搜索查询包含一个关键词的连接，并采用基于可搜索加密算法OXT [16,17]的查询词的帖子交集。不采用同时遍历两个或多个帖子的更快的传统交集算法[19]，因为这样的遍历会向服务器泄露更多信息。在搜索过程中，确保隐私的一种标准技术是使用确定性伪随机函数（称为PRF）隐藏信息，包括术语ID和文档ID。排名公式。我们选择了一种简单但流行的排名得分计算方案，即文档特征的线性组合。虽然这种评分[47]提供了不错的相关性性能，但是多个可加树（例如[44]）可以实现更好的相关性。然而，使这种非线性排名方法保密不仅涉及得分添加，还涉及值比较。0目前没有已知的加密方法可以在单个框架内解决这两个问题。线性组合公式计算排名得分，形式为αifdi，其中αi是文档d的特征值fdi的系数。我们假设所有系数都是静态的，并且可以在索引设置期间嵌入到特征值中。因此，在本文的其余部分，我们将忽略这些系数，并简化线性加法排名公式为fdi。原始排名特征。如果一个排名特征在索引中明确存储，并且一个排名特征是基于其他原始特征计算的，则我们将其称为原始排名特征和复合排名特征。我们的设计是将上述加法公式中的每个基本特征作为原始特征，并且服务器在不知道这些值的角色的情况下检索并简单地添加它们。这最大程度地减少了服务器理解它们对排名信号的语义贡献的机会。我们使用上述加法公式来支持信息检索文献中使用的四类排名特征：1）基于词频的复合特征，如TFIDF和BM25[27]。它们可以表示为加权原始词频的总和，因此上述加法方案支持此类特征。2）基于原始接近词特征之和的接近复合特征。这样的接近词可以是某个距离内的n-gram [8]或者是一个词对[21,49]。传统的带有位置信息的倒排索引明确存储单词位置[7]，在线排名根据每个文档中的单词位置计算复合接近特征。虽然这种方案在空间上是高效的，但计算复合接近特征需要从单词位置进行顺序比较和算术计算。如第1节所讨论的，缺乏同时支持安全计算和顺序比较的加密技术。泄漏每个文档的相对单词位置可能会启用统计攻击，揭示文档内容结构。因此，我们选择使用一个表达为直接建模接近术语的原始特征之和的接近公式。因此，以前的一些接近公式不受支持，例如最小聚合[42]和跨度覆盖[41]。3）文档查询特定特征，如文档-查询点击率。4）文档特定特征，如新鲜度和文档质量。第3）和第4）类别都是原始特征，并且可以自然地适应加法排名公式。处理原始排名特征的稀疏性。第2），第3）和第4）类别中的原始特征通常具有许多零值。如果所有加密的零值都明确存储，将大大简化隐私保护设计，但空间成本将急剧增加，这样的方案将变得不切实际。处理特征稀疏性的一个选择是将每个文档的非零特征值紧凑地存储为前向索引，一旦在查询处理期间确定了与查询匹配的文档，就可以使用哈希文档ID检索加密文档特征。另一个选择是将特征值嵌入到传统倒排索引的帖子条目中[7]。这些选项在没有适当防御的情况下存在隐私风险，服务器可以直接检查文档特征向量或帖子，并收集文档的统计信息，例如词频分布，而无需客户端授权并发起泄漏滥用攻击[15,36]。我们针对通常稀疏的可选特征的设计是使用在线键值存储。也就是说，每个匹配的文档d[F + M] = [q[f di + Rdi ] +[Odt + ROdt ]]R1+R2+R3Required: f1, f2, f3Optional: O1, O2, O3R1+R2+R3+RO2R1+R2+R3+RO1+RO3R1+R2+R3+RO1+RO2+RO3R1+R2+R3+RO1+RO2R1+R2+R3+RO2+RO3R1+R2+R3+RO1R1+R2+R3+RO317270涉及以下两种类型的权重。1）文档 d 的所需个别特征权重 f d i。当一个特征是必需的时，每个匹配的文档在索引中都有一个特征值。2）可选特征权重 O d t ，其中 1 ≤ t ≤ m。当一个特征是可选的时，当该文档的这个特征值在索引中不可用时，默认值为零。使用掩码混淆的特征加密。为了保护特征值的隐私，我们使用随机掩码对每个特征值进行混淆，通过模加法隐藏该值，使其对服务器不可见。这个掩码是使用PRF以确定性方式生成的，并且只有客户端知道。形式上，我们将每个特征值 f存储在索引中，表示为 [ f + R ] ，其定义为 f + R mod N，其中 R 是特征掩码，计算为术语ID和文档ID的PRF，范围从0到N − 1。对于我们的实现，N 设置为2的32次方。方括号表示 [ f + R ] ，也强调服务器看到的是计算值 f + R mod N，但服务器无法推导出单独的 f 或 R值。正如我们下面解释的那样，上述方案将允许服务器通过添加掩码特征值来计算排名分数，并在选择掩码时进行部分比较，以达到一种权衡。我们没有采用同态加密方案（例如[ 33]）进行特征混淆，因为它在效率上不具备明显优势，而且无法支持部分服务器端排序。具体而言，对于文档 d ，索引中特征 f d i的权重是一个整数，并存储为 [ f d i + R d i ]，其中包含一个随机噪声掩码 R d i ，可选权重 O d t 存储为 [ O dt + RO d t ] ，其中包含一个随机噪声掩码 RO d t 。给定一个具有q 个必需特征和 m 个可选权重的查询，文档 d 的总排名分数 F加上包括这些掩码在模 N 下的总分数掩码为：0其中 M = � 1 ≤ t ≤ m , O t ∈ X O d t + � 1 ≤ t ≤ m , O t ∈ XRO d t 和 O t ∈ X表示相应的可选特征可以在索引的键值存储中找到。虽然服务器可以计算上述加密和，但由于特征掩码是随机且独立于一个文档到另一个文档，服务器无法比较匹配文档之间的相对排名顺序。当匹配文档的数量适中时，服务器可以将这些结果发送给客户端，并附带每个文档使用的可选特征的位图，这有助于客户端移除每个排名分数中的掩码和。当服务器中有大量匹配的文档或客户端与服务器之间的带宽较低时，我们希望服务器进行部分排序，以便在发送回客户端之前首先过滤掉得分低的结果。这本质上成为一种两阶段排序，作为级联排序的一种类型[ 43]。在下一节中，我们将探讨这种可能性，并进行几个必要的权衡，以平衡隐私和查询响应时间效率。03 服务器端部分排序0使用均匀随机掩码的服务器端部分排序。为了允许服务器比较匹配文档的排名分数，一种选择是为相同特征的所有文档选择相同的随机掩码。通过这种放松，我们改变了掩码符号0将 R d i 作为 R i ，将 RO d i 作为 RO i，以便在第2节的排名分数公式中，所有匹配文档在相同的匹配可选项集合下的总掩码和是相同的，然后服务器可以对这些文档进行排序。为了支持上述策略，我们需要解决两个问题。1）由于每个随机特征掩码均从 0 到 N − 1均匀选择，掩码特征权重及其总和可能在模 N下环绕，这可能会误导服务器端的排名排序。为了让服务器处理这种环绕，而不知道实际的排名分数或进行额外的客户端-服务器交互，我们施加一个约束，即没有特征掩码的最终排名分数应小于 N02 。给定 q + m 个必需和可选特征，每个特征权重 w 应满足 max q , m ( q + m ) w02 ，即其上界为 N0max q , m ( 2 q + 2 m ) 。例如，当 q + m ≤ 32 且 N = 20每个特征权重的上界为 2 26 。当 q + m ≤ 1024 时，上界为 2 21。我们的评估结果表明，使用21位整数特征进行排名对于测试数据集已足够。我们将在本节末尾讨论 q + m 的可能值。0定理3.1. 给定 q + m 个必需和可选特征，每个特征权重 w 满足 max q , m ( q + m )02 。设 F 1 和 F 2 是在相同的和掩码 M 下的两个文档的排名分数，其中 0 ≤ M < N。• 如果 |[ F 1 + M ] − [ F 2 + M ]| < N02 ，则当且仅当 F 1 ≤ F 2 时，[ F 1 + M ] ≤ [ F 2 + M ] 。• 如果 |[ F 1 + M ] − [ F 2+ M ]| > N02 ，则当且仅当 F 1 ≥ F 2 时，[ F 1 + M ] ≤ [ F 2 + M ] 。0上述定理表明，当服务器获得两个带有可能发生环绕的掩码排名分数 [ F 1 + M ] 和 [ F2 + M ] 时，可以确定哪个分数 F 1 或 F 2 更大，而无需知道 F 1 和 F 2的实际值。这是通过检查 [ F 1 + M ] 和 [ F 2 + M ] 的差值是否在 N 内来实现的02 或不等于 N 。注意，差值不能等于 N0图1：当 q = 3 且 m = 3 时，可选特征匹配案例的格子关系02）在相同的查询下，不同的文档可能与不同的可选特征集匹配。有2 m 种可选特征匹配案例，代表匹配这些 m个可选项的不同组合。注意，得分掩码在不同的案例中是不同的，因此服务器不能直接在可选案例之间进行比较。图1展示了一个查询有3个必需项和3个可选项时，可选特征匹配案例之间得分掩码的格子关系。每条边表示包含关系，即父案例包含子案例中使用的项。与同一可选特征匹配案例对应的所有文档是可比较的，因为它们的得分掩码具有相同的值。因此，服务器可以对匹配同一案例的前 K个结果进行排序和选择。我们使用格子的以下属性来消除不必要的结果。0Track: Web Search and Mining WWW 2018，2018年4月23日至27日，法国里昂After the above lattice-based suppression, the server sends thetop results from different matching cases to the client where furtherscore deblinding and final top K result selection will take place.Query-dependent deblinding using chunk-wide runtimerandom masks. The above uniform masking strategy allows server-side partial ranking, but leads to the following leakage of informa-tion to the server.• Given two documents d and d′ from the same feature mask R, theserver can learn their relative weight difference [f d +R]−[f d′+R]to get f df d′.CD 6 7 81013 1516181920 2425272829 36404144rate 1 2 3 4 5 7 9 101213 2122232526 3031333639 4146484950CD-rate 725(a)Chunking examples05101520253035404550(b) Client-side range intersection for query decomposition17280在进行基于格子的抑制之后，服务器将不同匹配案例的前结果发送给客户端，进一步进行得分解盲和最终的前 K个结果选择。使用基于运行时随机掩码的块级别查询相关的解盲。上述均匀掩码策略允许服务器端进行部分排序，但会导致以下信息泄漏给服务器。• 给定来自相同特征掩码 R 的两个文档 d 和d'，服务器可以学习它们的相对权重差异 [ f d + R ]−[ f d' + R ] 以得到 f d − f d' 。0定理3.2. 设 U 和 V 是可选特征匹配案例的格子中的两个顶点，V 是U 的父节点（在图1中，V 指向 U）。设 topK(U) 是在案例 U下匹配的前 K 个文档。对于在 U 中匹配的文档 d，且 d 不属于topK(U)，在案例 V 下排名低于或等于 d 的文档可以安全地从 V中删除。0• 服务器还可以使用 [ f d + R ]−[ f s + R ] [ f d ′ + R ]−[ f s + R ] 来近似 f d0f d'，其中 f s 是最小的特征值。如果 f s很小（例如0），这样的近似是合理的。为了将上述泄漏限制在较小的范围内，我们提出了一种基于运行时查询选择的动态块级随机掩码策略。每个特征都有一个包含非零特征值的文档ID的倒排列表。索引构建将此列表分成块，并且每个特征的随机掩码是文档特定掩码和块特定掩码的总和。对于某些触发服务器端部分排序的查询，运行时查询处理会移除所有涉及特征的文档特定掩码。在这种情况下，同一块中匹配的文档共享相同的特征掩码，然后服务器能够对在同一块中匹配的文档进行排序。只有当匹配结果可能超过阈值时，客户端才会在服务器端触发部分排序。为了检测上述条件，我们将一个特征称为“热门特征”，当具有非零值的此特征的文档总数大于一个流行度阈值时。否则，将此特征称为“不受欢迎特征”。当查询中的必需特征之一是不受欢迎特征时，匹配结果的数量不能超过上述阈值。查询分解。根据上述设计和给定一个特征的排序文档列表，我们将此列表分解为一组不重叠的文档ID范围的块。从概念上讲，我们将每个特征ID视为一个项，将每个块视为原始项的子项。图2(a)给出了特征分块和查询分解的示例，查询为“CDrate”。添加的可选词对特征是“CD-rate”。“CD”的posting被分解为4个块，对应于4个子项 a 1 ，a 2 ，a 3和 a 4 ，而“rate”的posting被分解为5个块，对应于 b 1 ，b 2，b 3 ，b 4 和 b 5 。类似地，“CDrate”的可选特征的文档列表基于文档ID范围分区进行分解，只有一个块 c 1。知道posting块的ID范围后，客户端可以执行早期的范围交集，并将原始查询分解为0CD0CD利率0图2：分块和查询分解0一组子查询。与任何子查询匹配的文档都满足原始查询。对于图2(b)，客户端可以了解到只有ID范围(6,13)，(24,26)和(36,44)的文档可能包含所有所需的关键字，因此，原始查询“CD利率”被转换为4个子查询的析取：a1b2与可选c1，a3b3与可选c1，a4b4和a4b5。注意，提议的客户端查询分解除了服务器端部分排序之外，还带来了以下两个额外的好处。1）如我们在下一节中讨论的那样，特征访问被实现为哈希表查找。查询分解有助于利用局部感知数据分区，从而在加载哈希表的相关部分时减少交集和特征查找的内存占用。我们还考虑了避免在数据分区中过度利用局部性，因为对于被阻塞的数据访问操作存在隐私权衡[18]。2）交集算法选择一个必需的特征来开始枚举可能的文档候选项，通常是具有最小倒排列表长度的特征[19]。这在OXT[17]中称为s项，服务器在交集期间学习到每个查询的s项倒排列表的长度。由于服务器在处理多个查询后累积了这些信息，这可能会打开一个泄漏滥用攻击的大门，而一种对策是通过添加虚假ID来填充倒排列表，以掩盖真实的计数[15]。在我们的设置中，由于查询被分解为一系列子查询，客户端可以从一个子查询到另一个子查询选择一个起始特征（本质上是s项），这大大降低了泄漏单词倒排列表长度的机会。通过限制可选特征的数量进行权衡。如下一节所示，服务器使用位图记录记忆每个文档匹配了哪些可选特征。有大量可选特征会导致两个缺点：1）维护长位图的空间开销。2）根据上述格讨论，在服务器端基于匹配的结果较少。这两个因素导致在发送部分排序结果时产生更多的服务器-客户端通信开销。当使用单词对作为原始文本接近度特征时，为了减少单词对的总数，我们将出现在文档不同部分的单词对权重进行合并。按照之前的工作[8]，索引可以强加一个约束，即仅当这样的单词对的单词距离在限制范围内时，才将单词对包含在索引中。我们的评估在处理三个测试数据集时使用了限制为9。在运行时，给定查询中的q个单词，有�q2�个单词对，如果我们让m =�q2�，则使用这些单词对特征的格大小有2(q2)种情况。例如，当q =5时，已经有210种情况。当q =7时，格大小爆炸到221。我们强加一个约束，即客户端仅要求查询中距离限制L内的可选单词对。例如，对于一个5个单词的查询w1，...，w5和L =2，只有距离为2的单词对(w1,w2)，(w1,w3)，(w2,w3)，(w2,w4)，(w3,w4)，(w3,w5)和(w4,w5)被视为可选特征。通常情况下，基于单词对的可选特征的数量m相对于�q2�减少到�L2�+L(q−L)（如果q≥L），否则为�q2�。当我们选择L = 2时，m = 2q−3。如第5节所示，L =2的相关性在测试数据集中是可接受的。在实践中，我们可以假设q<10，因为通常修剪长度超过此长度的查询不会影响相关性。因此，当可选特征仅基于单词对时，m ≤15。在某些应用中，可能需要额外的可选术语来提高排名相关性，例如文档的新鲜度或权威性，因此m通常在24以下，我们在评估中使用3字节来存储可选位图。0会议：Web搜索和挖掘WWW 2018，2018年4月23日至27日，法国里昂pairs (w1,w2), (w1,w3), (w2,w3), (w2,w4), (w3,w4), (w3,w5), and(w4,w5) are taken as optional features. In general, the number ofoptional featuresm to consider based on word pairs is reduced from�q2� to �L2� +L(q −L) if q ≥ L, otherwise �q2�. When we choose L = 2,then m = 2q − 3. As shown in Section 5 the relevance with L = 2 isacceptable in the tested datasets. In practice, we can assume q < 10because typically trimming a query longer than such a length doesnot affect the relevance. Thus m ≤ 15 when optional features areonly based on word pairs. In some applications, additional optionalterms may be needed to improve ranking relevance such as fresh-ness or authoritativeness of a document, thus m is typically under24 and we use 3 bytes for the optional bit map in our evaluation.172904 索引和查询处理0在本节中，我们采用 OXT 可搜索加密[16,17]进行文档匹配，并将其扩展为排序。我们提出了一种索引和查询处理方案，以支持具有动态块范围随机掩码的特征屏蔽，并使客户端能够安全地触发服务器端对涉及热门特征的选定查询进行部分排序。该设计防止服务器从特征和加密单词的发布中学习到任何信息，如果从未搜索过这样的单词。数据结构和高级搜索流程。我们的搜索流程涉及3个键值存储：1）R存储在特征发布块中保存元信息，例如块的文档 ID范围。这有助于客户端进行查询分解。2）S存储包含所需的特征值，并由搜索算法用于识别候选文档。3）X存储包含使用文档 ID 和特征 ID一对访问的特征值。给定一个查询，客户端使用 R存储将其转换为一系列子查询。对于每个子查询，客户端为服务器生成 n 个所需和可选的特征 ID，如w1，w2，...，wn，以便服务器匹配文档并获取其特征。设 d是出现在起始特征 w1 的发布列表中的候选文档 ID。要获取 d的另一个特征 wi（其中 2 ≤ i ≤ n），在线算法将两个 ID wi 和 d配对作为访问 X 存储的键。为了保护隐私，所有 ID和中间值都使用表1中总结的运算符进行哈希或加密，以便对于任何特征名称和文档ID，服务器无法在未经客户端授权的情况下访问托管的 X 存储和 R存储中的发布列表或特征值。服务器不应该了解在线搜索期间使用的查询项的身份。加密倒排索引设置。将具有特征向量的输入数据集转换为倒排索引格式。由客户端控制的索引器构建加密索引，并让服务器托管 S 存储和 X 存储。对于文档 d 的特征 w，其值为f，该索引器构建了 X 存储的键值对，如下所示。定义 p 为 d在发布中的位置计数，c 是块 ID，其中 c = � p / csize �，csize是块大小。0• 密钥为 xtaд = д PRF ( k5 , w ) PRF ( k2 , d )，其中 k5 和 k2是秘密哈希密钥。基础 д 是伪随机映射的迪菲-赫尔曼常数[10]。•通过上述密钥访问的值为：S ( xtaд ) = f + Rc + Rx mod N，其中Rx = PRF ( ku , д PRF ( k1 , w ) PRF ( k2 , d ) )，Rc = PRF ( k0 , w∥ c ) 分别表示块特定和文档特定的掩码。0∥ 两个值的按位连接。0PRF ( k , a ) 使用密钥 k 对“a”进行确定性伪随机函数（例如，a ∥ k 的SHA256）。在使用的 PRF 密钥中，k0，...，k9 仅由客户端知道。ku对于生成特征权重掩码 Rx 是公开的。0E ( k , a ) 使用密钥 k 对明文 a进行非确定性对称加密（例如，使用随机初始化向量的 AES）。0D ( k , b ) 使用密钥 k 对 b 进行对称解密，使得对于任何明文 a 和密钥k，D ( k , E ( k , a )) = a。0S ( stag ) 使用键 stag 查找 S 存储，并返回一块加密的特征发布。0X ( xtag ) 使用键 xtag 查找 X 存储，并返回加密的特征值（如果存在）。0( xi ) ni = 1 从 i = 1 到 n 的元素 xi 的列表。0表1：功能和运算符符号0当需要上述特征时，d 和 f 值也保存在 S 存储中文档 w 的发布块 c中。相应的 S 存储键为 staд = PRF ( k7 , w ∥ c)。相应的值是发布条目的块列表，每个发布条目定义如下：( e , y ,fs )。0(1) e = E ( k e , d ) 代表加密的文档ID d 。加密的 e是语义安全的，因此服务器除了原始文档ID的长度外无法获取任何信息。(2) y = PRF ( k 4 , w ∥ p ) − 1 PRF ( k 2 , d )是一个盲化的桥接数，用于在交集中选择 w作为起始特征来派生访问 X-store 的密钥，该方法在 [ 17 ]中提出。我们扩展了它的用途以进行特征提取，并将在下面的示例中详细说明。(3) 盲化特征 f s = u d + f + R c + R s mod N，其中 u d 是第2节中讨论的特定于文档的类别4特征权重的总和。R s 是文档特定的掩码，计算方式为 PRF ( k 3 , w || p ) 。0在线搜索过程。图3显示了查询处理的三个阶段。第1阶段在客户端进行，为给定的查询形成所需和可选的特征，并在R-store查找后执行早期范围交集以派生子查询。假设每个子查询具有 n 个特征，对应的块ID为 ( w i ,c i ) n i = 1 。所有所需特征都放在可选特征之前，其中 w 1 被选为起始所需特征。然后，用于访问 S-store的密钥是 stag = PRF ( k 7 , w 1 || c 1 ) ，服务器用于解密 posting S ( staд ) 条目的密钥是 skey = PRF( k 6 , w 1 || c 1 ) 。此外，客户端为服务器构建了一个特殊的二维令牌数组，每个数组元素 tokens [ i ][ j ]定义为： xtoken i = д PRF ( k 5 , w i ) PRF ( k 4 , w 1 || p ) ，以及 mtoken i = д PRF ( k 1 , w i ) PRF (k 4 , w 1 || p ) ，其中 2 ≤ i ≤ n ，1 ≤ j ≤ csize ，csize 是块大小，posting 位置 p = c 1 � csize +j 。起始特征的相应文档特定掩码为 R s = PRF ( k 3 , w 1 || p )。如果预测的结果长度不超过阈值，则客户端不会打开服务器端结果过滤，在这种情况下，每个令牌数组元素的第二个条目 mtoken i 和 R s 信息将被作废。最后，客户端将 staд 和 skey 以及令牌数组和相关掩码R s （如果需要）发送给服务器以进行上述子查询。在第2阶段，收到每个子查询的控制信息后，服务器从S-store 中获取 w 1 的 posting，基于函数调用 S ( staд ) 。对于每个 posting 条目（假设为第 j个条目）的 w 1 以及第 i 个其他特征，它使用接收到的令牌数组 tokens [ i ][ j ] 计算 xtaд 以访问X-store，以及在需要时计算文档特定掩码 R x。服务器在需要时通过掩码减法累积排名分数（例如，图3的第21行）。当打开部分排名时，将比较和过滤每个可选特征格的文档分数，并为每种情况返回最多前 K个结果。对于从服务器发送回客户端的每个匹配文档，结果元组的格式为 ( e , F , O , j )，表示加密的文档ID、加密的分数、使用的可选特征的位图以及该文档在 w 1 的 posting块中出现的位置。第3阶段的客户端后处理去除分数掩码，并比较所有接收到的文档以选择最终的前 K个结果。示例。图4给出了查询“CDrate”和可选术语“CD-rate”的运行时处理示例。在查询分解和生成子查询后，假设“CD”是此子查询的起始特征。用于访问 S-store 的密钥是 staд = PRF ( k , “ CD ” ∥ c ) ，其中 c 是该特征的 posting的块。在访问 S-store 后，假设从“CD”的 posting 中找到了一个候选文档 d ，对应的元组为 ( e , y , f s )。为了进一步访问 X-store 中的“rate”特征，服务器计算访问密钥为 xtaд = xtoken y 2 ，以及 R x =PRF ( k u , mtoken 2 y ) 。由于 y = PRF ( k 4 , “ CD ” ∥ p ) − 1 PRF ( k 2 , d )，根据索引设置算法，我们可以验证服务器实际上获得了相同的值 xtaд = д PRF ( k 5 ,“ rate ” ) PRF ( k2 , d ) 和 R x = PRF ( k u , д PRF ( k 1 ,“ rate ” ) PRF ( k 2 , d ) ) ，这与构建 X-store的索引设置算法相匹配。这意味着在不知道值 k 1 ， k 2 和 k 5的情况下，服务器可以在由客户端发出的查询特定授权信息（例如令牌数组）之后成功获取和添加单词“rate”的特征权重。搜索复杂度。加密后的索引空间成本与所有非零可选特征值的总和以及所需特征ID的数量乘以文档数成正比。由于随机化，加密的数字无法很好地压缩。对于具有 n 个特征的查询，令 � ( Postinд ( w 1 ))表示每个子查询的起始特征 w 1 的 posting 长度之和。此查询的时间成本为 O (( n − 1 ) � | Postinд ( w 1)|) 。它比 [ 19 ]的时间成本慢，后者不需要考虑隐私保护，这代表了隐私搜索的一种权衡。查询处理的属性和泄露讨论。我们在附录A中对最坏情况泄露配置文件进行了更正式的分析。以下是我们方案的两个隐私属性。0会议: Web Search and Mining WWW 2018, 2018年4月23日至27日, 法国里昂17300根据函数调用 S ( staд ) ，对于每个 w 1
我的内容管理
展开
