不经意关键词检索技术综述

摘要：
随着数据成为新型生产要素，数据隐私保护在数据流通中的重要性日益凸显。然而，在实际应用中，数据中的隐私信息可能会因流通过程而面临泄露风险。隐私计算可以在满足隐私保护约束的同时促进数据价值的释放，并为数据流通与隐私保护之间搭建桥梁。不经意关键词检索（Oblivious Keyword Search, OKS）作为隐私计算的基础任务之一，在满足隐私保护约束的同时促进信息检索是其主要作用。
关键词：不经意检索; 信息检索; 隐私计算
本文通过分析现有文献总结出三种典型的Oks技术路线：基于Oblivious Polynomial Evaluation（OPE）、Oblivious Pseudo Random Function（OPRF）和Key-Value Store技术路线，并对它们的技术特点及优劣势进行了比较分析与探讨。
基于OPE的技术路线具有较高的通信复杂度优势（为对数复杂度），但计算开销较高；基于OPRF的技术路线虽然通信复杂度较低（线性复杂度），但计算开销较高；而基于Key-Value Store的技术路线则在通信与计算开销上取得了一定平衡。
目前研究工作主要集中在大批量检索场景下，而实时检索协议的优化仍需进一步探索；数据库动态变化场景下的高效检索协议尚未得到充分关注；多条件检索协议及隐藏检索结果的后处理技术仍需进一步研究以提升其实用性与安全性。
随着《网络安全法》《数据安全法》《个人信息保护法》等法律法规的实施以及隐私计算在各领域的广泛应用，“不可信基础设施”正在成为推动社会进步的重要力量。

摘要

在当前背景下，在大数据时代背景下，在数据作为新型生产要素得到广泛应用的情况下，在数字经济发展进程中，在人工智能技术推动下，在区块链技术支撑下，在云计算技术普及的大环境下，在全球数字经济转型浪潮中，在数字经济高质量发展的推动下

关键词： 不经意检索; 信息检索; 隐私计算

0 引言

随着信息技术的高速发展以及数字经济时代的全面推进，在推动经济和社会生活方面发挥重要作用的数据有效利用得到了广泛重视。中共中央以及国务院发布的《关于构建更加完善的要素市场化配置体制机制的意见》明确规定，在现有基础之上引入新元素——即把存在于生产过程中的各种资源进行重新整合，并将这些资源包括但不限于土地资源以及劳动力资源等传统的生产要素之外的新增因素视为一种全新的生产要素——即所谓的"新时代生产要素"。然而，在当前大数据环境下由于存在一定的隐私性信息限制导致的数据价值未能得到充分释放这一现象仍然存在。因此如何能够在确保满足相关法律法规前提下实现有效的资源共享已成为当下亟需解决的关键问题

面对数据流通与隐私保护之间的关键问题,隐私计算 emerged as a primary solution to address these challenges effectively. It enables multiple parties to conduct collaborative computations while safeguarding sensitive information from exposure, thereby achieving "data accessibility while maintaining privacy". The concept of oblivious keyword retrieval (Oblivious Keyword Search, OKS) stands out as a crucial mechanism within the realm of privacy-preserving information management. As a fundamental task in privacy computation, it serves as a building block for more advanced privacy protection techniques. This task represents a pivotal step in the workflow of privacy-protected data processing, providing substantial support for maintaining data security at every stage. This paper presents a comprehensive overview of the task definition and related functions associated with oblivious keyword retrieval. By conducting an in-depth review of existing research findings, this study identifies three predominant technical approaches employed in the field of OKS and offers a detailed analysis of their respective advantages and limitations. Furthermore, this paper explores and evaluates the primary technical obstacles encountered in oblivious keyword retrieval as well as forecasts potential future trends in this evolving domain.

1 不经意关键词检索

然而，在传统关键词检索机制中，为了实现查询功能，系统必须将用户的搜索关键词直接传递给数据库。这种直接暴露的方式不仅存在安全隐患，并且可能引发用户的隐私信息泄露问题。对此，在随后的研究中逐渐出现了新的解决方案框架。其中最著名的开创性工作是由Ogata和Kurosawa[1]于2002年提出的“不经意关键词检索”框架。该任务涉及两个关键实体：一个用于存储键-值对的数据库端（记为D），其形式为D={(_x₁,v₁), (_x₂,v₂),…, (_xₙ,vₙ)}；另一个是执行搜索操作的用户端（记为U）。在这一协议下，“不经意”概念被严格定义并得以实现：即数据提供方无法得知用户的真正需求；而用户仅能获取对应的目标信息而不了解其他潜在的内容。

2 相关任务及其关系

2.1 相关任务

隐私信息检索（Private Information Retrieval, PIR）是一种密码学原语，在不泄露查询目标相关任何信息的前提下允许用户访问所需数据库数据。具体而言，在该领域的研究起源于Chor及其合著者的开创性工作[13]。现有研究主要围绕使用同态加密技术展开[14-26]. 该领域的研究起源于Chor及其合著者的开创性工作[13]. 现有研究主要围绕使用同态加密技术展开[14-26]. 在现有技术路线中,核心思想是构造密文二值向量w∈{0, 1}^n ,其中若某个特定索引存在,则对应位置取值为1,其余位置取值为0. 这种技术路线虽然在通信复杂度上能够降至对数值水平,但在实际应用中仍面临较高的计算开销问题. 对此,[22-26]另有研究表明通过编码理论优化PIR协议中的计算与通信权衡关系.

OT被视为安全多方计算的核心机制，在实际应用中被广泛采用，例如用于生成乘法三元组[47]以及构建混淆电路[48]等技术。OT机制使得接收方可以从发送方提供的 n 个数据中获取其中任意 k 个数据。在整个过程中，发送方必须保证接收方无法推断出其查询的具体目标；同时接收方仅能获得预期的结果而不具备其他任何信息。传统的OT方案通常依赖于公钥密码学框架，例如基于RSA加密算法[45]。为了降低在线计算开销，在此基础上研究者们相继提出了多种优化方案：一方面提出了OTE（Oblivious Transfer Extension）[40⇓-42]和SimplestOT[43,44]算法；另一方面则发展出了Random OT技术，并将大量计算与通信转移到离线阶段进行管理以提高线上处理效率

在PSI场景中，默认情况下参与者持有各自的互斥数据集合_X_和_Y_ ，他们旨在计算双方数据集合的交集_X_∩Y ，但必须避免泄露除交集之外的数据细节。该技术最初应用于解决两个公司寻找共同客户的问题，在当前应用中已扩展到密码泄露检测、隐私数据对齐等多个领域。现有研究主要围绕基于不同技术路线展开：采用公钥密码学方法的PSI[27-30]、基于电路设计的PSI[31,32]、运用OT协议实现的PSI[12,33-39]以及基于全同态加密框架开发的PSI方案[4]。其中基于公钥密码学的方法利用Diffie-Hellman和RSA等核心机制构建OPRF协议，并能在密文状态下完成集合求交运算；而OT辅助型方案则通过构造OPRF协议实现运算过程，并且其开销显著低于前一类方法；但两类方案均面临通信复杂度与较大一方数据量呈线性关系这一局限性，在非平衡数据场景下表现不佳；针对这一问题背景，在全同态加密框架下实现了通信复杂度降维到对数级别方案设计；尽管如此，在实际运行过程中该类方案仍会带来较高的计算开销限制其大规模部署应用能力

2.2 不经意关键词检索与相关任务的关系

2.2.1 不经意关键词检索、隐私信息检索及不经意传输

这些任务从场景出发具有高度相似性，并均由用户端向持有数据的数据库发起查询请求以获取所需数据。三者的区别主要体现在媒介类型和对隐私的保护程度上，并可见于表1。其中最关键的前提条件是——用户方必须提前了解目标数据的具体位置或相关信息。
具体而言，在Pirate（PIR）中仅负责保护用户的隐私，在协议执行过程中确保数据库不掌握任何关于目标的数据；而Oblivious Transfer（OT）和One-Knowledge Signature（OKS）则会兼顾数据库的安全性——即用户方只能获得对应的目标值而不了解其他位置的信息。
需要注意的是，在Pirate和Oblivious Transfer中采用了具体的索引方式来构造查询请求——而Oblivious Key Search（OKS）则采用具体的关键词来进行定位。
其中最关键的前提条件是——用户方必须提前了解目标数据的具体位置或相关信息。

表****1****不经意关键词检索、隐私信息检索以及不经意传输的关系

隐私保护要求	查询媒介
用户端	数据库端	数组下标	关键词
PIR	√	√
OT	√	√	√
OKS	√	√	√

新窗口打开**|下载CSV** 2.2.2 不经意关键词检索与隐私集合求交

在分析当前研究领域时发现, 不经意关键词检索技术与隐私集合求交存在多个方面上的共性特征, 不经意关键词检索本质上可以被视为一种附加特定标签的非平衡隐私集合求交过程。具体而言, 附加特定标签指的是为原始数据集合中的每个元素添加对应的描述性标识符, 而这些元素与相应标识符的组合则构成了系统中独特的键值对结构。在实际操作过程中, 当执行某种形式的不经意关键词检索协议时, 隐私集合间的求交运算会隐式地进行, 即无需显式声明即可完成计算任务。因此, 部分现有的隐私集合求交协议[4-6]也成为了现有不经意关键词检索协议的重要理论基础。

3 典型技术路线

3.1 基于不经意多项式评估的技术路线

该Oblivious Polynomial Evaluation（OPE）机制属于双方安全计算领域中的重要方法之一。最初由Naor和Pinkas在1999年提出这一创新性解决方案。该方案主要应用于一种特定场景：涉及一名发送者和一名接收者。其中，发送方持有待分解的多项式_P_，而接收方则拥有需要代入计算的变量_x_。经过该协议运行后，在线程安全的前提下实现了以下目标：第一，在线程不可信的情况下确保发送方无法获取输入信息_x_；第二，在线程不可信的情况下确保接收方除了上述评估结果_P_(x)外无法了解多项式_P_的任何其他细节。

基于OPE的不经意关键词检索协议最初由Freedman等[3]于2005年提出,其流程如图1所示。该协议的核心思路在于将数据库中的键值对利用多项式插值法转换为阶数为 n- 1的多项式 P,即由α0,α1,…,α(n-1)组成的一组系数,其中 n_代表键值对的数量。随后,双方通过不经意评估完成了关键词检索的关键操作。OPE的实际实现依赖于半同态加密算法,例如Paillier方案。接收方生成半同态加密的公私钥对(pk,sk),并对查询关键词_w_的所有幂次从w^0到w(n-1)进行加密处理后输出密文给发方。发方则在接收到密文后进行计算,P(w)=∑(i=0)(n−1)αiwi=P(w)=∑(n-1)(i=0)αiwi,从而得到密文状态下的多项式评估结果_P(w),并将此结果传递给收方。收方通过使用私钥_sk_解密即可获取所需的查询结果_P_(w)。该协议的一个显著缺陷在于其计算复杂度与通信复杂度皆为_O(n)_水平,这导致该方法无法有效支持大规模数据集上的检索任务。Chen等[4]于2017年提出了基于全同态加密的概念框架Labeled PSI,并在后续研究中对其进行了多方面的优化改进工作

图 1

图1基于OPE的不经意关键词检索协议流程**[3]**

3.2 基于不经意伪随机函数的技术路线

ORP（Oblivious Pseudo Random Function）是一种基于伪随机函数加密机制的安全计算范式

基于O PRF 的不经意关键词检索协议的核心思想是双方通过 O PRF 对关键词实施加密操作，并确保相同关键词产生相同密文这一特性得以实现随后发送方利用生成的新密钥对原始关键词进行加密处理并构造出新的密钥值对这些新生成的内容随后被发送至接收方接收方则通过特定机制对这些接收到的新密钥值对进行解密最终实现所需的关键词检索功能在这一过程中双方均能够安全地完成其 respective 的操作步骤

在这一协议中 F reedman 提出了采用宽松 O PRF 方案的具体实施方法由于传统严格 O PRF 协议会对接收方造成过高的通信开销 F reedman 建议适当放宽安全标准以降低实施成本具体而言他允许接收方仅获知部分子密钥而不了解全部信息这种改进使得该类协议在实际应用中更具可行性

O PRF 执行过程主要包括以下几个关键环节首先是数据预处理阶段此处数据主要以键值对的形式存在发送方会将这些键值对存储在一个特定的数据结构中随后在加密过程中会用到这个存储空间

图 2

图2基于OPRF的不经意关键词检索协议流程**[3]**

3.3 基于Key-Value Store的技术路线

它是一种存储键值对的数据结构，在密码学领域已知的一些变体包括布谷鸟哈希表[10]和混淆布隆过滤器[11]等技术手段。其本质上构成一个单一的数组结构。而基于这种数据组织形式展开的不经意关键词检索机制，则其核心理念在于将所有键值对一次性注入到该数据结构中，并实现将关键词与数组索引之间的映射关系，并最终将未加密的关键词检索问题转化为一种基于隐私保护的信息检索机制。

通常情况下，在数据存储系统中会设计两个 Key-Value Store 结构来实现特定功能。其中一个是用于验证关键词在数组中的具体位置（结构 K），这是因为每个关键词 w 都会被映射到 k 个下标 (i₁,…,i_k)，而接收方在协议执行前并不掌握这些下标的具体位置信息；另一个则是用于存储对应的关键字值（结构 V），以便后续检索操作能够快速定位所需数据。在PIR协议的实际操作中需要注意以下几点：首先，在执行PIR协议时（即本方案中所指的 PIR 实现方式），必须采用 SPIR 技术来进行通信交互过程；其次，在初始化阶段需要完成两者的通信交互过程：接收方通过获取 k 个指定下标 i₁至i_k来进行 SPIR操作；这样不仅能够完成对目标位置数据的读取与返回（即 K[i₁],…,K[i_k] 的获取），而且会暴露非查询相关的其他位置信息；因此为了保护隐私安全并防止非查询关键词的位置信息被泄露出来；双方系统需引入 OPRF 技术进行数据加密处理；这样接收方就可以通过对密文进行比较来确定查询目标的具体索引位置 j；然而由于加密处理的关系无法反推出其他潜在的相关索引位置信息；最后 receiver 可以通过 SPIR 方式直接访问 V[j] 这一位置的数据单元并获得最终结果 V[j] 。整个协议的具体工作流程如图3所示

图 3

图3基于Key-Value Store的不经意关键词检索协议执行流程**[10-11]**

3.4 技术路线比较

采用了基于OPE的技术以实现...这一协议在通信复杂度方面已达到 O(logn) ，适用于通信资源较为有限的情况。然而该协议的成本表现为运算负担的增长。尽管Chen等人[5-6]采用了SIMD技术和分箱策略来减少运算负担，但仍存在显著的成本。由此可见，在处理大规模数据时，运算成本过高将限制该技术路线的实际应用。

该OORP基下的无隐式关键词检索协议在通信复杂度方面表现虽为 O(n),但伴随OPRF技术的进步,计算负担逐渐减轻。由此可见,OORP方案通过创新地采用OT扩展机制实现了资源效率与性能的最佳平衡。具体而言,Chase等[12]提出的解决方案是基于OT扩展理念的一种轻量级OPRF方案:首先利用少量非对称加密生成大量对称加密密钥;其次通过这些对称密钥完成整个OPRF过程;最后成功降低了公钥密码系统中所需使用的次数的同时显著提升了整体计算效率。

该键值存储模式下的不经意关键词检索协议通过优化实现了较低层次上的计算消耗和通信消耗。将其与其他OPE方案对比后发现，在通信复杂度方面两者均达到 O(logn)水平。尽管其计算复杂度维持在线性水平上，并未像其他方案那样需要大量资源用于插值多项式的生成。相较于ORF方案而言，在通信效率上有显著优势的同时其计算负担却相对较高。

4 不经意关键词检索技术面临的挑战与发展趋势

该任务可被视为隐私计算体系中的基础性研究领域之一。然而,目前仍面临诸多亟待解决的关键问题。随着隐私计算技术的不断进步,学术界及产业界对该领域的关注度持续提升。本文系统性地探讨了4个核心领域的挑战现状及其未来发展趋势。

4.1 实时检索协议

目前，在大规模数据集处理方面，现有的研究工作主要集中在对大规模数据集进行处理的情形中，并且通常情况下用户端会同时进行多关键词查询操作。然而，在实时检索的情境下，查询请求往往呈现小批量甚至单目标的特点，在这种情况下现有工作的大部分优化措施将难以有效实施。由于这些优化措施难以有效实施而导致的结果是：使得协议运行所需的计算和通信资源成本显著提高，并且无法满足当前对实时性要求的需求。因此，在这种背景下如何构建高效的实时检索协议成为亟需解决的核心挑战。

4.2 适应数据库动态变化的检索协议

在实际应用场景中,数据库能够实现动态更新键值对,例如新增新的键值对。然而,现有工作尚未针对这种情况进行相应的处理,导致在多次检索过程中,旧的键值对都会被重复访问。这不仅引入了多余的计算负担和通信开销,还影响了整体性能效率。因此,如何构建增量式的动态检索机制成为一个亟待解决的问题。

4.3 多条件检索协议

现有研究主要集中在仅依据关键词进行检索的方法上，在实际应用场景中，则更倾向于通过多维度属性组合检索来增强协议筛选的效果。例如，在这一场景下，则要求信托机构不仅要依据身份证信息进行初步筛选，并需综合考虑用户存款与设定下限之间的关系；因此，在同一检索过程中综合考虑多项查询条件成为一个亟待解决的关键问题。

4.4 隐藏检索结果的后处理技术

偶尔进行关键词检索经常会作为数据处理的前置任务，在计算一批用户的平均信用评分时需要通过关键词（例如身份证）来提取对应用户的信用评分信息。从"数据可用不可见"的角度出发，在数据处理过程中可能会有意地保留部分信息以便于后续使用。因此，在不泄露检索结果的前提下对检索结果进行后续处理成为一个亟需解决的关键问题。

5 结束语

随着国家针对个人隐私保护方面颁布了包括《网络安全法》《数据安全法》《个人信息保护法》《网络数据安全管理条例》等多部相关法律法规,隐私计算逐渐受到重视并得到了广泛应用,其应用领域已延伸至数据联合分析、机器学习联合建模等多个方面。其中,不经意关键词检索作为一种基础性的重要组成部分,在实际部署和应用中发挥着关键作用。与现有基于数组下标的检索方法相比,基于关键词的不经意关键词检索模式更能贴合现实应用场景需求。鉴于此,深入研究高效的安全性 nxt 关键词检索协议将有助于推动隐私计算技术的发展,进一步拓宽其应用场景范围。

本文通过调研现有研究工作并对其特点进行深入分析,最终对典型技术路线进行了系统性划分,将其分为基于OTE的技术路线、基于OPRF的技术路线以及基于Key-Value Store的技术路线等三大类。每一类技术路线均具有鲜明的特点和独特优势,同时也伴随着相应的局限性,且适用于特定的应用场景范围。在此基础上,进一步探讨了如何实现计算开销与通信开销的最佳平衡,从而彻底解除对不经意关键词检索协议应用场景的限制,这一目标仍需要研究者们的持续努力和创新探索。此外,本文还深入剖析了现有研究中尚未解决的关键技术难题,并提出了未来发展的主要方向:即开发实时检索协议,使其能够更好地适应数据库动态变化的需求;设计多条件检索协议以提升功能完整性;探索隐藏检索结果后处理技术以增强安全性;同时致力于优化资源分配策略以降低运行成本。随着不经意关键词检索任务效率的不断提升和功能日益完善,其在隐私计算领域中的作用将更加突出,其所带来的价值也将愈发显著