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

韩宗达 邓宇涛 程祥

(北京邮电大学计算机学院(国家示范性软件学院)网络与交换技术国家重点实验室，北京 100876)

0 引言

在信息技术高速发展的数字经济时代，数据的有效利用对推动经济发展、改善社会生活有着重大意义。中共中央、国务院《关于构建更加完善的要素市场化配置体制机制的意见》明确指出数据将与土地、劳动力、资本、技术等传统要素并列，成为一种新的生产要素。然而，数据中隐私信息的存在阻碍了数据价值的充分释放。如何在满足数据隐私保护约束的同时，有效促进数据流通，成为当今时代的关键问题。

隐私计算是解决数据流通与隐私保护之间矛盾的主要手段，其允许多方在隐藏各自敏感信息的前提下执行协同计算，实现“数据可用不可见”。不经意关键词检索(Oblivious Keyword Search，OKS)是在隐私保护下实现信息检索的重要手段，也是隐私计算的基础任务之一。该任务是隐私保护协同计算的关键步骤，为数据处理全流程的隐私保护提供了重要保障。本文对不经意关键词检索的任务定义及其相关任务进行了介绍；然后，结合对现有研究的调研，总结出三种不经意关键词检索的典型技术路线，并分析了各个技术路线的优劣势；最后，对当前不经意关键词检索所面临的主要技术挑战和未来发展趋势进行了分析与探讨。

1 不经意关键词检索

关键词检索是信息检索中的一项基本任务。在传统的关键词检索任务中，数据库端持有一组键值对，用户端通过关键词对数据库发起检索请求，数据库端在接收到查询请求后，通过查询请求中的关键词对持有数据进行检索，并将检索结果反馈给用户端。

然而，传统的关键词检索需要向数据库暴露查询目标的关键词。在实际应用中，查询目标的暴露可能导致隐私信息的泄露，从而使用户利益受到损失。对此，最早由Ogata与Kurosawa[1]在2002年正式提出了不经意关键词检索的定义与协议。该任务的场景设置包含一个数据库端和用户端，数据库端持有一个存储键值对的数据库D={(x1,v1),(x2,v2),…,(xn,vn)}，用户端通过关键词xi对数据库进行查询，得到对应的值vi。不经意关键词检索要求同时保护数据库端与用户端的隐私，即数据库端不能得到用户端的查询目标，而用户端不能得到除了查询目标对应值以外的其他信息。

2 相关任务及其关系

2.1 相关任务

隐私信息检索(Private Information Retrieval，PIR)是一种密码学原语，允许用户端对数据库进行查询而不会向数据库暴露任何有关查询目标的信息。具体来说，数据库端持有一个数据库D={D1,D2,…,Dn}，数据库中有n个元素，接收者持有一个查询索引i，协议执行完成后，接收者可以得到查询结果Di。在这个过程中，协议保证接收者不会得到查询索引i的任何相关信息。Chor等[13]首次提出PIR协议，并随后出现了大量的相关研究工作[14-26]。现有研究大多基于同态加密[14-21]，核心思想是构造密文二值向量w∈{0,1}n，若查询索引存在，则向量中对应位置的值为1，反之为0。该技术路线的通信复杂度可以达到对数复杂度，但是其计算代价较高[16,17,21]。对此，有一部分研究通过编码理论对PIR协议的计算开销与通信开销进行优化[22-26]，避免使用大量的密码学原语。

不经意传输(Oblivious Transfer，OT)是安全多方计算的基础原语，广泛应用于安全多方计算中，如生成乘法三元组[47]、构造混淆电路[48]等。OT允许一方从另一方的n个数据中，获取其中的k个数据。在该过程中，持有数据的一方不应知道另一方的查询目标，而拿到查询结果的一方不应得到除了查询结果以外的信息。传统的OT协议基于公钥密码学构造，如RSA[45]。为了降低OT的计算开销，一方面研究者们相继提出OT扩展(Oblivious Transfer Extension，OTE)[40-42]以及SimplestOT[43,44]，通过降低公钥密码学原语的使用次数，大大提高协议的计算效率；另一方面研究者们提出Random OT[46]，将大量计算与通信转移到线下进行，提高线上的计算与通信效率。

隐私集合求交(Private Set Intersection，PSI)的场景设置为：持有各自数据集合X、Y的两方期望计算得到双方数据的交集X∩Y，同时不暴露交集以外的其他信息。隐私集合求交具有很长的发展历史，最早被提出用于解决两个公司间寻找共同顾客的问题，目前广泛应用于密码泄露的发现、隐私信息的数据对齐等场景。隐私集合交的现有研究按照技术路线可以划分为基于公钥密码学的PSI[27-30]、基于电路的PSI[31,32]、基于OTE的PSI[12,33-39]以及基于全同态加密的PSI[4]。基于公钥密码学的PSI通过Diffie-Hellmann、RSA等公钥密码原语构造OPRF协议，并在密文下完成集合求交。基于OTE的PSI通过OTE构造OPRF协议，其计算开销远远小于基于公钥密码学的PSI。两者的共同缺陷在于协议执行的通信复杂度与集合较大一方的集合大小呈线性复杂度关系，不适合于非平衡场景，即双方的集合大小不相等的场景。针对该问题，基于全同态的PSI将协议的通信复杂度降低为与集合较大一方的集合大小呈对数复杂度关系，显著降低了通信开销。但是，基于全同态的PSI在执行时会产生较大的计算开销，使其难以应用于大规模数据场景。

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

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

不经意关键词检索、隐私信息检索及不经意传输在任务场景上非常类似，均为用户端向持有数据的数据库端发起查询请求，以获取指定数据。三个任务的区别在于查询媒介以及隐私保护要求(见表1)。对于隐私保护要求，PIR仅保护用户端的隐私，即数据库端在协议执行过程中不会得到查询目标的相关信息，OT与OKS会兼顾数据库端的隐私，即用户端仅能得到查询目标对应的值，而无法得到其他位置的值。对于查询媒介，PIR与OT将数组下标作为查询请求，而OKS则使用关键词。因此，PIR和OT存在一个前置条件，用户端在查询前已得知查询目标在数据库中的精确位置。

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

2.2.2 不经意关键词检索与隐私集合求交

不经意关键词检索技术与隐私集合求交存在诸多共同之处，不经意关键词检索可以视作一种特殊的携带标签的非平衡隐私集合求交。携带标签指为隐私集合求交中的数据集合元素添加相应的标签，元素与标签的组合即可视作不经意关键词检索中的键值对。在执行不经意关键词检索协议的过程中，隐私集合求交会隐式进行。因此，部分隐私集合求交协议[4-6]也成为了现有不经意关键词检索协议的基础。

3 典型技术路线

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

不经意多项式评估(Oblivious Polynomial Evaluation，OPE)是一种两方安全计算协议，最早由Naor与Pinkas[2]于1999年提出。OPE的场景设置中存在一个发送者以及接收者，发送者持有多项式P，接收者持有待评估的输入x，协议执行完成后，接受者获得评估结果P(x)。OPE的安全要求是发送者不能得到输入x的相关信息，接收者除了得到最终结果P(x)，不能得到其他更多关于多项式P的信息。

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

不经意伪随机函数(Oblivious Pseudo Random Function，OPRF)是一种以伪随机函数加密为基础的两方安全计算协议。OPRF的场景设置中存在一个发送者以及接收者，发送者持有伪随机函数f的种子k，接收者持有输入x。经过OPRF协议之后，接收者得到得到伪随机函数的计算结果f(x,k)。在协议执行过程中，要求发送者不获得有关x的任何信息，接收者也不会获得有关k的任何信息。

基于OPRF的不经意关键词检索协议的核心思想是双方通过OPRF对关键词完成加密，并保证相同的关键词可以得到相同的密文，然后发送者利用密文关键词构造新的密文键值对，并将其发送给接收者，接收者通过密文键值进行匹配与解密，从而完成信息检索。Freedman[3]在2005年提出了一种基于宽松OPRF的不经意关键词检索协议。由于严格的OPRF要求接收者不能获取有关发送者密钥的任何信息，Freedman认为达到该安全强度需要付出过高的代价，从而放松了安全要求，使接收者允许获得发送者的部分子密钥。该协议的OPRF执行过程如下：发送者拥有存放键值对的数据库x，首先发送者生成一个由两组随机数作为密钥种子的伪随机函数，然后其将关键词xi∈X切分为两个份额xi=(x1,x2)，并将切分后的两个份额作为索引分别在两个密钥集合r1,r2中选取对应的密钥r1,x1,r2,x2，最后利用选择得到的密钥对关键词x进行加密，得到fr1,x1(xi),fr2,x2(xi)，再将两份关键字密文的异或结果作为关键词xi的加密结果fr(xi)；发送者使用关键词的密文对键值对中的值进行加密，得到新的密文键值对X′；接收者在发起查询请求时对查询关键词w进行切分(w1,w2)，通过不经意传输[7]获取发送者密钥集合中特定的两个子密钥r1,w1,r2,w2，并使用与发送者一致的加密方法对查询请求w进行加密，得到fr(w)。在双方完成OPRF后，接收者得到的关键词密文仅能解密该关键词所对应的密文键值对，在实现信息检索的同时不会对接收者暴露除查询目标以外更多的信息。基于OPRF的不经意关键词检索协议的整体执行流程如图2所示。

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

Key-Value Store是一类可以存储键值对的数据结构，包括布谷鸟哈希表[10]、混淆布隆过滤器[11]等，本质是一个一维数组。基于Key-Value Store的不经意关键词检索的核心思想是将所有键值对插入到Key-Value Store中，完成关键词到数组下标的映射，从而将不经意关键词检索问题转化为隐私保护的信息检索问题。

一般而言，会针对关键词和值构造两个Key-Value Store结构，其中一个结构K用于验证关键词在数组中的具体位置，这是由于关键词w会被映射为k个下标(i1,…,ik)，而接收者在协议执行前无法得知关键词在数组中的具体位置；另一个结构V用于存储关键词对应的值，以用于检索操作。在执行PIR的过程中，需要注意三个关键点：接收者必须使用SPIR技术。这是由于PIR无法保证发送者的隐私安全，可能造成非查询关键词的相关信息的泄露；接收者首先通过k个下标(i1,…,ik)执行k次SPIR，以得到所有位置存储的关键词K[i1],…,K[ik]，但是其暴露了非查询关键词的位置，使接收者获得了额外信息。因此，为了避免上述信息的泄露，需要引入OPRF技术，双方同时对持有的关键词进行加密。接收者可以通过比较密文确定查询关键词在数组中的位置j，但是其无法通过密文反推出其余关键词的位置。最后，接收者通过SPIR查询数组V中第j个位置的值，获得查询结果V[j]。协议整体执行流程如图3所示。

3.4 技术路线比较

基于OPE的不经意关键词检索协议在通信复杂度上已达到O(logn)，适用于通信资源较贫乏的场景。但是，其代价是计算开销的增长。虽然，Chen等[5-6]利用SIMD、分箱等手段降低计算开销，但总体上仍较高。因此，当面临大规模数据时，计算开销的过大会限制该技术路线的实际应用。

基于OPRF的不经意关键词检索协议虽然在通信复杂度上为O(n)，但随着OPRF技术的发展，其计算开销逐步降低。Chase等[12]提出了一种轻量级的OPRF协议，其启发于OT扩展，使用少量的非对称加密生成大量的对称加密密钥，并利用对称加密密钥完成OPRF，降低了公钥密码系统的使用次数，显著提高了协议整体的计算开销。因此，该技术路线适用于计算资源较为贫乏的场景，但缺陷在于需要承担庞大的通信开销，当查询较为频繁时，信道压力会过大。

基于Key-Value Store的不经意关键词检索协议在计算开销与通信开销上取得了较好的平衡。与基于OPE的技术路线相比较，该技术路线的通信复杂度与其一致，均为O(logn)；在计算开销上，虽然仍为线性复杂度，但是，该技术路线无需花费较大的计算资源代价生成插值多项式，因此，在计算开销上优于基于OPE的技术路线。而与基于OPRF的技术路线相比较，该技术路线虽然具备较小的通信开销，但其所花费的计算开销仍较高。

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

不经意关键词检索任务是隐私计算的基础性任务之一。近年来，随着隐私计算的发展，学术界与业界均对不经意关键词检索逐渐引起重视。但是，该任务目前还存在许多挑战亟待解决。本文总结了4个不经意关键词检索任务面临的挑战及发展趋势。

4.1 实时检索协议

目前，已有的研究工作均集中于大批量检索的场景，用户端一次性查询多个关键词的值。但是，在实时检索的场景下，查询请求往往是小批量的，甚至是单目标检索。而此时，现有工作的大部分优化措施将失效，导致协议的计算、通信资源代价过高，无法满足实时检索要求。因此，如何构造效率较高的实时检索协议是亟待解决的关键问题。

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

在实际应用场景中，数据库会实时更新键值对，比如增加新的键值对。而已有工作尚未考虑该场景设置，导致在多次检索中，旧键值对会重复检索，增加了不必要的计算开销与通信开销。因此，在数据库动态变化的场景设置下，如何形成增量式动态检索是一个亟待解决的关键问题。

4.3 多条件检索协议

现有的研究工作均聚焦于仅依赖关键词的检索方法，但在实际应用中，用户端可能希望采用多个属性进行组合检索，以拓展协议的筛选能力。例如，信托机构需要向银行检索一批用户的信用评分，但对用户存款设置下限，若低于下限，则无需返回信用评分。在该场景设置下，信托机构不仅需要使用用户的身份证进行筛选，还需要同时考虑该用户的存款是否低于已设置的下限。因此，如何在检索时同时考虑多个查询条件，是一个亟待解决的关键问题。

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

不经意关键词检索经常会作为数据处理的前置任务，如计算一批用户的平均信用评分前需要通过关键词(比如身份证)取出对应用户的信用评分。从“数据可用不可见”的角度考虑，被检索方可能只希望暴露数据处理结果，而检索结果可以对用户端隐藏。因此，如何在隐藏检索结果的前提下，对检索结果进行后处理是一个亟待解决的关键问题。

5 结束语

随着国家针对个人隐私保护颁布了包括《网络安全法》《数据安全法》《个人信息保护法》《网络数据安全管理条例》等在内的多个法律法规，隐私计算逐渐引起重视并广泛应用于各种应用场景，包括数据联合分析、机器学习联合建模等。不经意关键词检索作为隐私计算的基础性任务之一，对隐私计算的实际部署及应用有着至关重要的作用。相较于隐私信息检索、不经意传输等面向数组下标的检索方法而言，面向关键词的不经意关键词检索任务更贴近于实际应用场景。因此，研究高效的不经意关键词检索协议有助于促进隐私计算的发展，拓展隐私计算的应用边界。

本文通过对现有研究工作进行调研、分析与讨论，将典型技术路线划分为基于OTE的技术路线、基于OPRF的技术路线以及基于Key-Value Store的技术路线。三种技术路线均存在各自的优势与劣势，并且适用于不同的应用场景，而如何取得计算开销与通信开销的最佳平衡，使不经意关键词检索协议的应用场景不再受限，仍需要研究者们的不断探索。进一步地，本文还对现有研究尚未解决的技术挑战进行了分析与探讨，并给出了未来发展趋势：实时检索协议、适应数据库动态变化的检索协议、多条件检索协议以及隐藏检索结果的后处理技术。当不经意关键词检索任务的效率不断提升、功能逐渐完备时，必将在隐私计算的发展潮流中充当更为重要的角色，释放更为巨大的价值。