1.   引言

用户与企业在考察选用稳定、可靠、高弹性服务的云服务的同时，往往担忧重要隐私信息(如企业生产数据、个人生物特征信息等)存在泄露风险，带来经济损失、安全和伦理问题等一系列不良后果。数据以密态形式存储与流通可以有效缓解上述困境，为数字经济发展保驾护航，但也对数据的查询功能带来了技术挑战。

顾名思义，密文检索技术旨在提供密态数据查询服务，提高密文数据的可用性。常见形式之一为可搜索加密(Searchable Encryption, SE)技术，尤其是对称可搜索加密(Symmetric Searchable Encryption, SSE)技术。其主要技术特点为面向特定的查询类型，设计专门的密文索引数据结构，支持服务器依据加密查询条件(或称检索陷门)，对密文索引执行“查找”操作，从而得到结果集数据标识。2006年，Curtmola等人^[1]首次提出关键词对称密文检索的两个安全性要求：非适应性安全与适应性安全，以及具备该安全性质的解决方案，并采用基于模拟器的安全证明框架形式化地证明了方案安全性，为后续工作提供了理论基础。在其安全性证明中，将访问模式与检索模式构成的查询踪迹(trace)定义为允许公开的信息^[1]。此后，在构造单关键词检索以外的其他SSE机制(如多关键词检索、动态检索、区间检索等)时，研究者发现必须公开的信息远不止于此：除访问模式与检索模式外，还必须公开中间结果集大小、密文之间的顺序等信息。因而引入泄露函数(leakage function)，显式定义最大可能的泄露信息，并形式化证明除此之外没有信息泄露。泄露函数成为后续SSE机制刻画自身安全性的基本依据，尽量最小化泄露函数成为主要设计目标之一。

人们根据泄露函数定义无法准确了解公开信息对SSE机制的危害程度。相反，攻击者可以利用SSE的泄露信息发起推理攻击(inference attack)、泄露滥用攻击(leakage-abuse attacks)、重建攻击(reconstruction attack)^[2–18]，攻击者通过对比泄露信息与一些公开数据集之间的统计特征关联，可以恢复出用户搜索的关键词或部分数据内容。

为了提高SSE机制的隐私保护能力，研究者借鉴多个相关领域研究进展，积极探索解决方法。一种尝试途径为结合可信执行环境(Trusted Execution Environment, TEE)技术，从纯软件方案向软硬件协同技术思路转变，利用TEE为数据机密性与数据、代码的完整性提供基本安全保障，从而大幅降低了原有问题难度。基于TEE安全假设，相关研究重心在于如何实现数据不经意(data oblivious)特性，接近零隐私泄露。相似技术也应用于密文数据库检索安全性改善。另一种尝试方向为引入安全多方计算、全同态加密等密码学算法与协议构造检索方案，实现检索模式隐藏或检索结果集尺寸隐藏，减少信息泄露。例如，采用非共谋双服务器模型，分别掌握不同秘密的两个服务器通过执行安全两方计算协议完成安全检索功能；或者采用多个服务器，通过秘密共享协议实现数据检索等。此外，虽然理论上利用全同态算法可以构建任意计算函数，包括各种SSE功能，但考虑到算法实现效率因素，当前比较现实的目标是基于全同态算法保护查询意图，实现隐匿信息检索(Private Information Retrieval, PIR)。此外，随着检索类型向多样化转变，许多查询(如K近邻查询、近似K近邻查询、Skyline查询等)处理过程涉及大量复杂数值计算，更需要特殊关注，确保在密文计算步骤中没有额外的隐私泄露。本文总结了近年来隐私保护密文检索研究方面涌现出的一批新成果，主要围绕多样化密文检索、基于可信执行环境的密文检索、隐匿信息检索等研究热点展开阐述，并给出未来的技术发展方向建议。

2.   背景知识

2.1   基础框架

2.1.1   系统部署

SSE一般由数据拥有者、数据查询者和云服务器三者组成。其中数据拥有者是数据属主，在将数据上载之前，构造支持查询功能的密文索引，并将密文索引与加密后的数据一同发送至云服务器；数据查询者是查询请求的发起者，负责为查询条件构造陷门，将其提交给云服务器等待结果；而云服务器通常具备强大的存储能力和计算能力，负责利用密文索引和陷门进行协议运算，并将满足查询条件的密文数据返回给数据查询者。大多数场景下，云服务器采用单服务器模型部署，如图1(a)所示；也有些场景采用双服务器模型，由两个非共谋服务器安全交互完成检索功能。如图1(b)所示，通过“存储器”与“解密器”之间的安全计算协议联合实现云服务器功能。虽然服务器间多轮交互会引入额外通信代价，但是双服务器模型相对更容易达到零隐私泄露目标。

图 1  可搜索加密系统部署图

下载: 全尺寸图片 幻灯片

2.1.2   访问模式

后文中提到宏观与微观两个层次的访问模式，请读者结合语境加以辨析。前者为SSE安全协议层面概念，1次“访问”指代1个“查询”，“访问模式”意指为可观察到的查询返回结果。例如文献[1,19,20]中定义如下：

给定数据集合DB和一组针对DB的查询${Q}_{1},{Q}_{2},\cdots {,Q}_{S}$：

定义1查询模式：查询模式为一个$S\times S$的矩阵$\bf{S}\bf{P}$，对于任何$1\le i,j\le S$，若${Q}_{i}\left(w\right)$=${Q}_{j}\left(w\right)$，则${\bf{S}\bf{P}}_{i,j}=1$，否则${\bf{S}\bf{P}}_{i,j}=0$。

定义2访问模式：访问模式为所有查询返回的结果集，即$\left\{\mathrm{D}\mathrm{B}\right({Q}_{1}),\mathrm{D}\mathrm{B}({Q}_{2}),\cdots ,\mathrm{D}\mathrm{B}({Q}_{S}\left)\right\}$。

而后者为系统操作层面概念，指代对指定存储位置的读写数据行为，如对操作系统内容中内存单元的访问，或者对于数据库表某条记录的访问等。考虑到密文检索的过程发生在云服务器，检索过程中对内存或存储单元的访问都可以被服务器观察，此类访问模式也理应在机制安全性考察范围内。

2.2   安全模型

服务器威胁模型包括3种：(1)诚实且好奇(honest-but-curious)模型：在该模型中，服务器忠实地执行协议，但会监听或搜集用户隐私信息。(2)恶意(malicious)模型：该模型中的服务器为了最大化自身利益，可以采用各种手段欺骗、干扰甚至中止协议的执行，例如返回部分结果等。(3)强敌手(strong adversary)模型：该模型中敌手能力介于前两者之间，攻击者以搜集用户隐私信息为主要目的，不仅可以被动地监听所有的服务器内存、磁盘存储以及网络通信，而且可以主动施加影响，例如发出硬件中断信号强制重启，启动服务软件的debug模式等。目前在无硬件依赖的方案多采用半诚实模型，而在基于可信执行环境的密文检索中，考虑到敌手可能具备对硬件环境的控制能力，部分方案采用强敌手模型。

目前针对SSE的安全攻击包括^[21,22]：(1)推理攻击^[2–17]：也有文献称为泄露滥用攻击^{[3,4,7,8,10–15]}或重建攻击^[9,16,17]。在此类攻击中，敌手收集用户查询时产生的信息泄露进行统计分析，通过比较用户产生的数据和一些公开数据之间统计特征的相似之处，进而推断用户搜索的关键词内容。(2)文件注入攻击(file-injection attacks)^[18,23,24]：敌手向系统注入一些含有特定关键词的文件，然后利用用户已查询过的陷门再次进行查询，根据查询结果恢复陷门对应的关键词。

2.3   密码学工具

2.3.1   同态加密

同态加密是一类特殊的密码算法，允许通过密文上的运算间接地实现明文计算。其中全同态加密同时具备加法同态和乘法同态性质且允许对密文进行任意次的同态运算，目前主流方案基于带误差学习(Learning with Errors, LWE)问题构造。首个基于LWE问题的同态加密方案^[25]通过密文的张量积进行同态乘法运算，采用重线性化操作消除密文维度扩张，利用模切换控制噪声，自举操作消除多次计算产生的累计误差，支持任意次加法、乘法同态运算，此后相继出现了BFV方案^[26]、BGV方案^[27]和GSW方案^[28]。其中BFV的明文和密文采用多项式环形式，支持以单指令多数据(Single Instruction Multiple Data, SIMD)的形式同时对多个消息并行计算；GSW方案利用“近似特征向量”技术，使用矩阵的加法和乘法来实现密文的同态加法和同态乘法运算缩短了自举时间，还支持与BFV密文之间的同态乘法。类同态加密技术(SomeWhat Homomorphic Encryption, SWHE)仅允许有限次数的加法和乘法同态运算，典型方案包括加法同态加密算法Paillier^[29]，乘法同态加密算法RSA^[30]等。

2.3.2   不经意访问

不经意随机访问机(Oblivious Random Access Machine, ORAM)最早由Goldreich等人^[31]在1996年提出，旨在隐藏程序处理器对操作序列和地址序列之间的关系，从而避免逆向攻击，增强软件的安全性。它通过构造合适的存储结构和访问机制，使每一次访问和随机访问不可区分，从而隐藏访问数据块的位置、数据块请求的顺序、访问的频率和具体的读写方式。由于上述良好的特性，不经意随机访问机是保护可搜索加密访问模式的重要技术之一。由于不经意随机访问机服务器需要存储冗余数据块和执行冗余操作^[32]，在利用其优点的同时需要优化服务器的存储性能。最先被提出适用于小型客户端的Path ORAM^[33]是目前最实用的不经意随机访问机方案之一。其主要思想为，在客户端设立数据缓冲区与查询数据块地址映射表，在服务器端采用树结构存储数据块。每次读取根节点到目标叶子节点路径上所有桶中的数据块至缓冲区，更新目标数据块后分配新的地址，同时更新数据块地址映射表，尽可能将缓冲区中的数据块写回服务器以减少存储空间。其他相关工作包括：Ring ORAM^[34]采用修正算法对服务器的存储空间进一步优化；PrORAM^[35]设计数据预读取机制，通过预取出预测的数据块减少访问延迟；Circuit ORAM^[36]将每次查询数据块的路径与驱逐路径合并，进一步优化了电路的复杂度。

2.4   可信执行环境

可信执行环境基于底层芯片硬件与一套特殊的指令集，构造出一个隔离的计算环境，在不安全的环境下对数据与代码进行机密性与完整性保护，代表性厂商与技术包括Intel SGX, ARM TrustZone等。以SGX为例，它通过飞地(Enclave)维护进程中一个隔离的虚拟地址空间，其中代码和数据都存储在被保护的内存页中，称为EPC (Enclave Page Caches)，Enclave之外的进程无法访问该内存页。EPC中的数据由内存加密引擎(Memory Encryption Engine, MEE)加密，且只解密CPU缓存中的数据。客户端通过远程证明协议在远程主机上验证Enclave及其加载的代码/数据的真实性，并在此后于客户端和Enclave之间建立安全通道传递秘密密钥。

在恶意模式、强敌手模式下，攻击者可以控制整个系统的资源，从而发起侧信道攻击。TEE不仅可能面临物理类攻击，例如攻击者通过物理接触CPU实施如能量分析等，更大可能面临来自相同CPU上的恶意软件或者操作系统内核的软件类攻击：如基于Cache的缓存计时攻击(cache-timing attack)，基于快表(Translation Lookaside Buffer, TLB), DRAM等的侧信道攻击^[37]，基于页表失效的缺页异常攻击(Page-Fault Attack)，基于内核精心选择系统调用返回值，从而间接修改应用程序数据的Iago攻击^[38]等。TEE自身无法抵御物理攻击，但若TEE 中运行程序没有数据相关(Data Dependent)的内存访问模式以及控制流分支，满足数据不经意特性，则可以抵抗部分软件侧信道攻击。侧信道攻击是可信硬件的一个重要隐患，高性能系统如何高效抵抗侧信道攻击仍然是一个开放问题。

3.   多样化密文检索

3.1   安全K近邻(K Nearest Neighbor，KNN)查询

K近邻查询是数据处理领域的基础性算法之一，在数据挖掘、信息检索和社交网络等领域应用广泛。给定数据项集合$\bf{D}\bf{B}=\{{\boldsymbol{P}}_{1},{\boldsymbol{P}}_{2},\cdots ,{\boldsymbol{P}}_{N}\}$以及查询点$\boldsymbol{Q}$，K近邻查询从$\bf{D}\bf{B}$中找到距离$\boldsymbol{Q}$最近的前K个数据项，具体定义如下：

定义3K近邻查询：给定数据项集合$\bf{D}\bf{B}= \{{\boldsymbol{P}}_{1},{\boldsymbol{P}}_{2},\cdots ,{\boldsymbol{P}}_{N}\}$、查询点$\boldsymbol{Q}$以及距离度量函数$\varDelta$(如欧氏距离)，K近邻查询返回结果集合$\boldsymbol{R}\in \bf{D}\bf{B}$ ($\left|\boldsymbol{R}\right| = K$)，使得$\forall {\boldsymbol{P}}_{i} \in \bf{D}\bf{B}-\boldsymbol{R},\mathrm{ }\varDelta ({\boldsymbol{P}}^{{{'}}},\boldsymbol{Q}) \le \varDelta ({\boldsymbol{P}}_{i},\boldsymbol{Q})$，其中${\boldsymbol{P}}^{{{'}}}=\mathrm{m}\mathrm{a}\mathrm{x}\{\varDelta (\forall {\boldsymbol{P}}_{j}\in \boldsymbol{R},\boldsymbol{Q}\left)\right\}$。

安全K近邻查询的难点在于如何安全实现距离计算和距离比较。文献[39]提出了一种基于矩阵加密算法的安全K近邻查询方法。矩阵加密算法通过引入随机矩阵与明文向量相乘得到密文向量，利用其密文向量的内积等于明文向量的内积的特性，可以快速实现密文数据点之间的距离计算和比较。然而由于矩阵加密算法无法提供语义安全，因而此类方案安全性存在较大缺陷。为避免复杂的距离计算和比较操作，文献[40–42]将查询点“附近”的数据项返回给客户端，客户端解密后往往还需要在明文查询结果中找到距离查询点$\boldsymbol{Q}$最近的K个数据项。文献[40]提出一种基于R树和保序加密算法的安全K近邻查询方法。该方法以查询点$\boldsymbol{Q}$为中心构造查询矩形，利用保序加密的保序性质对密文R树搜索，找到查询矩形内的全部数据项并返回给客户端。然而，保序加密导致密文直接泄露了明文的顺序关系。文献[41]提出了一种基于Voronoi图的安全位置最近邻查询方法。该方法基于Voronoi图将数据空间划分为若干个互不相交的区域，查询时服务器需要将Voronoi多边形与查询点$\boldsymbol{Q}$所在区域相交的数据项返回给客户端，并利用AES等标准加密算法实现数据机密性。文献[42]提出了一种基于映射编码的安全位置K近邻查询方法。该方法利用映射函数$h\left(\boldsymbol{P}\right)=\left\lfloor(\boldsymbol{a}\cdot \boldsymbol{P}+b)/d \right\rfloor$ (其中$\boldsymbol{a}=(\theta ,1)$是极坐标下的随机向量，$d$是预设的宽度参数，$b\in [0,d)$)的组合形式对数据空间坐标映射后网格化，查询时服务器将查询点$\boldsymbol{Q}$所在网格内的数据项返回给客户端。该方法通过对网格编码将K近邻查询问题转换为多关键词查询问题，并构造不可区分布隆过滤器树索引^[43]实现安全关键词查询。该方案会泄露各关键词对应的部分查询结果，且仅返回近似查询结果。上述安全K近邻查询方案主要基于单服务器模型，查询效率高，对百万条数据的查询时间可以达到秒级。但是从安全性角度，上述方案普遍存在以下不足：(1)查询过程会泄露访问模式；(2)除文献[39]外，查询结果中包含冗余数据。

面向高安全性应用场景，文献[44,45]分别提出了访问模式隐藏的安全K近邻查询方案，查询者仅得到K个最近邻数据项，没有额外的数据隐私泄露。这类方案基于“存储器-解密器”双服务器模型和Paillier同态加密技术，查询时通过两方服务器交互实现零隐私泄露的安全协议。主要思路是存储器利用Paillier的同态性质将密文数据盲化后发送给解密器，解密器解密后使用明文盲化数据进行计算并将结果重加密后返回给存储器，最后由存储器对解密器返回的密文结果去盲化。

文献[44]提出了一种线性扫描的安全K近邻查询方案。该方案首先分别计算各数据项与查询点之间的密文平方欧氏距离，然后使用安全比较协议得到K个最近邻点。为隐藏访问模式，服务器需要遍历K次全部数据，因此该方法需要${O}\left(KN\right)$次安全比较协议。文献[45]提出使用Voronoi图加速位置数据的K近邻查询过程。根据Voronoi图的性质，如果${\boldsymbol{P}}'_{1},{\boldsymbol{P}}'_{2},\cdots ,{\boldsymbol{P}}'_{K}$为查询条件$\boldsymbol{Q}$的K个最近邻点，则${\boldsymbol{P}{{}}}'_{K}\in \mathrm{A}\mathrm{G}\left({\boldsymbol{P}{{}}}'_{1}\right)\cup \cdots \cup \mathrm{A}\mathrm{G}\left({\boldsymbol{P}{{}}}'_{K-1}\right)$，其中$\mathrm{A}\mathrm{G}\left({\boldsymbol{P}{{}}}'_{i}\right)$为${\boldsymbol{P}{{}}}'_{i}$的邻接数据项集合。如图2所示，该方法根据Voronoi图分别构建网格索引和分桶索引。网格索引将数据空间分割为互不相交的网格，每个网格对应一个集合${\boldsymbol{G}}_{i,j}$，如果${\boldsymbol{P}}_{t}$对应的多边形与${\boldsymbol{G}}_{i,j}$对应的网格相交，则将${\boldsymbol{P}}_{t}$放入${\boldsymbol{G}}_{i,j}$中。分桶索引将数据项按照标识分桶，并保存各数据项的邻接数据项集合信息。在查询阶段，服务器首先根据网格索引找到包含查询点$\boldsymbol{Q}$的网格，并线性扫描相应集合${\boldsymbol{G}}_{i,j}$中的数据项找到最近邻点${\boldsymbol{P}}'_{1}$。然后，服务器从分桶索引中找到${\boldsymbol{P}'}_{1}$的邻接数据项$\mathrm{A}\mathrm{G}\left({\boldsymbol{P}}'_{1}\right)$，并从$\mathrm{A}\mathrm{G}\left({\boldsymbol{P}}'_{1}\right)$中扫描找到下一个最近邻点，重复此过程直到找到K个最近邻点。该方案通过分桶索引对数据过滤，每一轮仅需要在候选集合$\mathrm{A}\mathrm{G}\left({\boldsymbol{P}}'_{1}\right)\cup \cdots \cup \mathrm{A}\mathrm{G}\left({\boldsymbol{P}}'_{t-1}\right)$中扫描找到下一个最近邻点${\boldsymbol{P}}'_{t}$。因此，该方案可以将安全比较协议减少至${O}\left(M{K}^{2}\right)$次，其中M为最大的邻接数据项集合大小。文献[44,45]通过服务器间的交互实现零隐私泄露的安全计算，在查询过程中可以完全隐藏数据项、查询条件、访问模式和搜索模式。但是，此类方案的计算和通信代价极高，比如文献[45]对1万条数据进行最近邻查询就需要上百秒。

图 2  基于Voronoi图的安全K近邻查询方案^[45]示意图

下载: 全尺寸图片 幻灯片

3.2   安全近似K近邻(Approximate K Nearest Neighbor, ANN)查询

在现实应用中，数据通常有成百上千维度，对这些高维数据进行K近邻查询面临着“维度灾难”问题。即使是在明文状态下，当维度大于20时，现有基于R树、LSD树等索引结构的K近邻查询方法的效率与顺序扫描相比并没有明显优势^[46]。为此，一种折中的办法是牺牲结果准确度来换取查询效率的提升，即仅返回近似查询结果。现有的安全近似K近邻查询方法主要分为两类：基于LSH的方法和基于聚类的方法。

文献[47]提出了一种基于聚类的安全近似K近邻查询方法。为解决原始k-means方法导致的聚类不均衡问题，本方法提出对较大聚类进行重新聚类，直到所有的聚类大小均小于某个预设参数。查询时，服务器首先找到中心点距离查询条件$\boldsymbol{Q}$最近的若干个聚类，然后从这些聚类包含的数据项中线性扫描找到距离$\boldsymbol{Q}$最近的K个数据项。此外，为加速Top-K计算过程，该方法提出了一种近似选择算法。首选对输入值进行随机置换，将置换后的数据集分成$L > K$组，使用线性扫描的方式从每组中找到各组的最小值，然后从这些最小值中计算K个最小值。为实现安全查询，该方法使用同态加密算法BFV实现安全距离计算(图3步骤(2)、步骤(5))，使用混淆电路实现距离大小比较(图3步骤(3)、步骤(6))，使用FLORAM实现不经意数据读取(图3步骤(4))。该方案可以实现数据、查询条件机密性保护，并隐藏访问模式、搜索模式，但是查询过程需要服务器和客户端之间进行大量交互，比如对百万条数据项进行查询的通信量在1～2 GB。

图 3  基于聚类的安全近似K近邻查询方案^[47]示意图

下载: 全尺寸图片 幻灯片

为减少客户端的计算和通信代价，文献[48]提出了一种基于LSH(Locality Sensitive Hashing)的安全近似最近邻查询方法。为避免使用计算、通信代价高昂的安全比较协议，该方法借助基数排序(Radix Sorting)算法，使用$L$个$({R}_{i},c{R}_{i},{p}_{1},{p}_{2}){\text{-}} \mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}$ LSH函数${H}_{1},{H}_{2},\cdots ,{H}_{L}$分别构造查找表${T}_{1},{T}_{2},\cdots ,{T}_{L}$，其中${R}_{1}$<${R}_{2} < \cdots$<${R}_{L}$。在查询阶段，服务器分别查找各表中与查询点LSH值一致的数据项标识，并从第一个非空集合中随机返回一个数据项标识给客户端(如图4所示)。为保护查询条件、隐藏访问模式，该方法采用基于非共谋双服务器模型和分布式点函数的PIR算法实现对${T}_{1},{T}_{2},\cdots ,{T}_{L}$的不经意访问，PIR算法结束后双服务器分别得到查找结果的秘密共享份额。此时，服务器如果将各表的查找结果份额直接返回给查询者，则会造成额外的数据库隐私泄露。因此，服务器使用不经意掩码(Oblivious Masking)技术对各表的查询结果进行掩码计算，最终查询者只能得到第一个有效的数据项标识，其他数据项标识均被随机化。此外，该方法使用LSH多探头(LSH Multi-Probe)技术进一步降低查找表的个数$L$，提升查找效率。在安全性方面，该方法额外泄露了查询结果所在的查找表，但是在查询性能方面，该方法将通信量降低到MB级。

图 4  基于LSH的安全近似最近邻查询方案^[48]示意图

下载: 全尺寸图片 幻灯片

此外，文献[49,50]分别提出了基于LSH的安全近似K近邻查询方案。文献[49]使用Z-Order Code对数据项对应的LSH值进行线性编码，根据编码构建索引树，并使用密文可比较的加密算法(comparable encryption)保护编码值，查询过程会泄露访问模式。文献[50]使用OMapE(Oblivious Map with Encryption)对LSH查找表进行不经意查询，可以实现访问模式隐藏，但是会将各表的查找结果泄露给客户端。

3.3   安全Skyline查询

Skyline查询在多目标决策、数据可视化、用户偏好查询等领域有着广泛应用。Skyline查询用于返回给定数据集中所有不被其他数据项所“支配”的数据项，具体定义如下：

定义4“支配”关系：给定两个$d$维数据项${\boldsymbol{p}}_{a}$和${\boldsymbol{p}}_{b}$，如果对于任意维度$i$，均有${\boldsymbol{p}}_{a}\left[i\right]\le {\boldsymbol{p}}_{b}\left[i\right]$，且至少在一个维度$i$上满足${\boldsymbol{p}}_{a}\left[i\right] < {\boldsymbol{p}}_{b}\left[i\right]$，则称${\boldsymbol{p}}_{a}$支配${\boldsymbol{p}}_{b}$，记为${\boldsymbol{p}}_{a}\prec {\boldsymbol{p}}_{b}$。

定义5Skyline查询：给定数据集$\bf{D}\bf{B}= \{{\boldsymbol{p}}_{1}, {\boldsymbol{p}}_{2},\cdots ,{\boldsymbol{p}}_{N}\}$，返回结果集合$\boldsymbol{R}=\{\boldsymbol{p}\in \bf{D}\bf{B}|\forall \boldsymbol{p}{{'}}\in \bf{D}\bf{B}, \boldsymbol{p}{{'}}\nprec \boldsymbol{p}\}$，即$\boldsymbol{R}$中的数据项不被其他数据项所“支配”。

安全Skyline查询的关键问题在于如何快速找到新的Skyline点以及快速过滤被“支配”的数据项。根据Skyline查询的定义，分别为各数据项计算属性值的累加和，累加和最小的数据项一定是Skyline点。基于此思想，文献[51]提出了一种基于非共谋双服务器模型和Paillier同态加密算法的线性安全Skyline查询方法。该方法依次找到累加和最小的数据项，并通过扫描将被该数据项所“支配”的数据项剔除。为快速过滤被“支配”的数据项，实现次线性查询，文献[52]提出了一种基于R树的安全Skyline查询方法。如图5所示，该方案设计了一种半盲化R树(semi-blind R-tree)索引结构，将同一父节点的叶节点构成节点桶(Node Bucket)，并为各叶节点生成加密二进制向量IV，用于标识叶节点的存储位置。查询时，服务器通过分支定界法优先查找属性值累加和最小且未被支配的索引项，并通过IV向量不经意读取叶节点，从而实现查询不可链接性。此外，文献[53]基于Materialization方法预先计算Skyline结果，将动态Skyline查询问题转换为索引表查找问题。该方法可以实现次线性查询，但是需要将索引保存在客户端。

图 5  半盲化R树索引结构示意图

下载: 全尺寸图片 幻灯片

此外，现有的关键词查询方法大多基于关键词的准确匹配，返回的结果往往无法完全满足用户的查询意图，因此子串查询、语义查询等关键词扩展查询方法也受到关注。文献[54]提出了一种安全子串查询方法，通过将子串查询改写为区间查询，可以直接集成到现有数据库系统中。该方法将字符串划分为一组重叠的子串，每个子串都对应一个位置列表，为子串构建统一的存储索引并通过状态信息记录子串存储区间，同时使用FHOPE (Frequency-Hiding Order-Preserving Encryption)算法加密位置信息。文献[55]基于简洁的概念层级结构提出了一种高效的安全语义查询方法。该方法引入属性信息对概念层级结构进行扩展，根据扩展后的结构为每篇文档/查询条件构建两个索引/查询向量，一个用于概念匹配，另一个用于属性匹配，同时使用矩阵加密算法保护向量安全性。然而，方案[54,55]均存在访问模式泄露等安全问题。针对大规模图数据，文献[56]首次提出了一种隐私保护的强模拟(strong simulation)查询方法。强模拟查询在图的球上进行搜索，可以在计算复杂度和匹配灵活性之间取得较好的平衡。安全图查询的难点在于如何实现顶点匹配以及迭代修剪不满足查询条件的匹配。该方法使用邻接矩阵表示图结构，将查询转换为一系列矩阵上的加法和乘法运算，并采用基于循环群的加密算法(Cyclic Group Based Encryption, CGBE)实现矩阵机密性保护。为避免数据溢出导致CGBE解密错误，该方法提出了非准确强模拟算法EncSSA，对不同跳数的邻居采用不同的修剪策略。

4.   基于可信执行环境的密文检索

4.1   基于SGX的可搜索加密

依托Enclave的隔离与内存加密功能，由对称加密算法保护的明文索引可以起到类似密文索引的效果，从而更高效地实现机密性保护、访问模式保护以及前后向安全等安全目标。与大多数可搜索加密设计路线不同，基于TEE的可搜索加密关注重点在于如何合理改造明文索引，使其更适应Enclave环境。本节以Intel SGX为例介绍基于TEE的可搜索加密机制设计，4.1.1节介绍实现数据机密性保护的典型架构，4.1.2节介绍如何通过不经意查询操作进一步消除可能的侧信道攻击。

4.1.1   数据机密性

早期由于SGX中安全内存EPC受限(例如，第1代SGX中EPC大小被限制在相对较小的128 MB)，系统通常被拆分成可信与非可信两部分：不可信的代理服务器负责网络信息处理与I/O读写，运行于Enclave之外；可信的部分为核心且精简的数据处理模块，运行于Enclave内。数据与索引均以密态形式存储于外部的不可信存储服务器。如图6所示，其基本处理步骤包括：(1)初始化，用户本地加密索引与数据上传至不可信代理服务器；(2)安全发送密钥，用户通过远程证明与Enclave建立安全信道，并通过该信道将数据与索引的解密密钥发送给飞地内可信部分；(3)提交查询，用户由安全信道提交查询条件。在另一端的Enclave内，可信部分获得明文查询条件；(4)索引加载，Enclave进程根据需要载入加密的索引并解密；(5)执行查询，在Enclave内，根据解密后的明文条件与索引进行检索，得到结果集；(6)返回结果集，若用户希望得到结果索引编号，则将该结果集经安全信道返回给用户；若用户希望得到数据项，则还须进一步提取密文数据，解密后由可信信道发送给用户。由于加密索引随着新一代Intel SGX处理器内核数量与安全内存大幅扩容，EPC不再受限(目前已扩增至1 TB)，架构设计可以进一步简化。

图 6  基于SGX的可搜索加密架构示意图

下载: 全尺寸图片 幻灯片

该基础架构结合不同索引类型可形成不同构造方案，如基于SGX的B+树索引^[57]，多关键词倒排索引^[58]，支持多关键词析取、合取、否定等复杂布尔查询的动态多关键词索引^[59]，以及支持TF-IDF的文本索引以及面向人脸特征向量计算与识别的加密图像索引^[60]等。此外，上述架构也并非基于SGX实现可搜索加密的唯一的思路，还有一些不同的解决方法：例如，文献[61]仍旧保持在密文索引上检索操作，但采用SGX辅助部分计算；文献[62]利用用户与Enclave之间的秘密共享协议实现多用户密钥临时存储，降低持久密钥泄露危害。

基于SGX的SSE方案在可信执行环境中更易于实现前、后向安全^[63–65]，且提供强后向安全保证，避免使用可穿刺加密、ORAM等复杂密码学原语，防范文件注入攻击^[66]。前向安全确保密文更新不会与以前提交的查询发生关联，后向安全保证查询不会泄露和已删除文档之间的关系。通过飞地内物理更新数据可取代复杂密码原语，采用1轮次的检索与更新操作，在计算与通信代价方面有明显改善。此外，由于运行在不可信的环境中，存储经常可能遭受破坏或者重放攻击，在读取数据之前经常性地需要进行完整性验证。这既可以利用SGX内部的完整性树结构，也可以采用加密存储在外部的MHT结构实现^[67]，在可信存储中部署计数器可进一步实现数据新鲜性验证。

4.1.2   数据不经意检索

如前所述，攻击者可以通过观察Cache查询时间、磁盘读写位置、输出数据规模等Enclave外部特征推测索引、查询条件，甚至数据的内容。若运行于Enclave中的可信部分支持数据不经意检索，则可以降低系统遭受侧信道攻击的风险。目前，实现数据不经意性检索有两种途径：(1)采用不经意比较(=, >,<)运算符^[68,69]以及不经意算子(如ObliVM^[70]中的排序算子)构建索引，令代码具备不经意特性；(2)基于不经意内存访问机制(如Path ORAM^[33], Ring ORAM^[34], PrORAM^[35]等)设计检索机制，实现不经意数据访问。

如图7所示，文献[71]基于Path ORAM实现了Oblivious Bitmap, Oblivious Forward Index以及Oblivious Bloom Filter Tree等多种不经意索引数据结构，实现访问模式保护的布尔检索。

图 7  基于SGX的布尔检索方案^[71]示意图

下载: 全尺寸图片 幻灯片

图7(a)展示了Oblivious BitMap索引的设计原理：索引服务由可信进程与不可信进程两部分构成。可信进程内运行一个经典的关键词倒排索引，以及Path ORAM机制中的客户端—ORAM Client。倒排索引中包含一个BitMap数据结构，常驻内存用于快速查找关键词是否存在，以及以“键-值”形式存储数据地址的Multimap结构，记录与缓存关键词与内存块的对应关系。Multimap所占用的内存页面由ORAM Client负责管理。对应的ORAM Server部署于非可信部分，两者交互实现密文索引页的不经意访问，避免与用户端的交互。图7(b)展示了Oblivious Bloom Filter Tree索引的设计原理，总体思路十分相似，同样采用Path ORAM机制实现内存不经意访问，不同之处在于采用Bloom Filter Tree作为Enclave中的明文索引。该系统性能达到最坏情况下次线性(worst-case sub-linear)。

Oblix^[67]针对此前不经意Map数据结构在插入操作时的安全与效率缺陷，提出了不经意排序Multimap数据结构。在Path ORAM机制支持下，采用类似平衡二叉树的数据结构存储同一键值对应的所有数据，方便快速查找键所对应的第$i$个值。进一步地，基于Path DORAM机制将索引改造为具有双重不经意特性(double-oblivious)数据结构，在满足外存访问与内部RAM访问之间不经意特性的同时，保证了查询效率优于Zerotrace ^[72]中的双重不经意实现方式。文献[73]提出了一个不经意的子串查询方案。

4.2   基于可信执行环境的密文数据库

支持面向结构化数据库的SQL查询是密文检索的重要应用之一。经典的密文数据库^[74]以查询代理模式运行，通过端对端加密的方式支持密文表上的多种类型数据SQL查询，无法很好地解决复杂子查询、内存密钥泄露等问题。而采用高代价的全同态计算的实现^[75]，以及基于安全多方计算的实现^[76]，都导致数据库性能3～5个数量级的急剧下降。SGX, TrustZone等可信执行环境的出现提供了第3种选择。基于可信执行环境的密文数据库旨在基于硬件TCB打造数据库引擎，实现远程不可信服务器上的高效查询。

4.2.1   基于TEE的密文数据库

由于SGX平台的普及性，本文主要讨论基于SGX平台的密文数据库，图8是3种典型的体系结构。

图 8  3种典型的基于SGX平台的密文数据库体系结构

下载: 全尺寸图片 幻灯片

一般来说，基于TEE的密文数据库最为直观的做法是DBMS作为整体运行于Enclave内，用户与Enclave经远程证明建立安全信道后，连接并使用数据库服务(如图8中架构类型I)，典型代表是文献[77]。早期类型I面临Enclave大小、技术特点等限制因素，但随着新一代Intel SGX处理器内核数量与的安全内存大幅扩容，EPC不再受限(目前已扩增至1 TB)，并且Graphene、Occlum等底层轻量级LibOS支持可实现网络通信与资源调度，限制性因素已逐渐消失。架构类型I的最大优势是部署简单，且对于上层应用几乎没有影响。但需要指出的是，即使技术条件完全满足，上述做法也不是唯一最佳选择。原因在于，一方面DBMS作为大型综合性软件，代码量大且复杂度高，全部放入Enclave中导致TCB过大，相应的系统面临的攻击面也更大。另一个不可忽略的重要因素是：由于DBMS与数据库系统都在Enclave中，因而对于所有使用者都是明文，不可信的管理员频繁访问Enclave中的数据库进程，容易引发管理风险，无法防止来自恶意数据库管理员的内部攻击。

需要指出的是，近年来出现的细粒度TEE概念^[78,79]为密文检索提供了类型I、II之外的新型思路。例如，基于硬件指令扩展构造出多层嵌套的SGX Enclave^[78]，可以实现代码库隔离与多级安全，限制算法库漏洞危害扩散范围；基于SGX的MPK技术可在单个Enclave中设立多个内存隔离区域，构成多个轻量级飞地^[79]，在细粒度的隔离与降低Enclave切换代价之间取得了更好的平衡。可以将精简的查询处理引擎放在一个飞地。

图8中架构类型II对DBMS代码进行拆解，在Enclave中仅部署一个精简的查询处理引擎，而将DBMS的其他部分放在外部Non-Enclave中。与类型I相比，不仅TCB尺寸大幅减少，而且减少了受攻击面。典型代表是EnclaveDB^[80]。如图9所示，Enclave内容为一个精简的Hekaton查询处理引擎，包含本地编译过的存储过程以及用于维护必要运行环境、证明、封装等功能的一个可信内核。而大量的其他数据库功能，如查询编译器、公开数据库的查询处理、日志管理、存储管理、数据库管理(除敏感数据部分外的其他职责)等都位于Enclave之外的查询处理器。用户提交查询前，首先利用本地的数据库系统和密钥编译生成加密存储过程，发送至服务器。查询时，用户调用库函数生成SQL查询发送至不可信服务器，后者根据需要决定是否启动Hekaton引擎处理加密存储过程。EnclaveDB通过预编译查询提高了性能，和工业界的内存数据库相比，代价较低(TPC-C代价40%)。EnclaveDB最大限度地考虑了来自网络、磁盘、内存的安全攻击，通过协议校验日志的安全性、完整性与新鲜性。该协议支持并发、异步的添加与删除，最小化线程间的同步代价，可防范来自日志操作的安全威胁。由于类型II需要合理拆分DBMS内核代码，其技术难度较类型I与III更高。

图 9  EnclaveDB^[80]架构示意图

下载: 全尺寸图片 幻灯片

图8中架构类型III在3种类型中Enclave尺寸最为紧凑，仅负责临时存储加密密钥并进行明、密文计算。加密数据库内容与DBMS代码中的大部分都放在不可信区域。采用架构类型III的有StealthDB^[81]、Azure SQL^[82]以及Operon22^[83]。这种方式对DBMS代码改动很小：磁盘读写与网络传输部分代码都无需改变，仅仅是对查询解析树中最底层的操作符(如 <=, >=, +, ×)进行重定义，将针对明文的操作符改写为对加密数据上的操作符，其主要处理逻辑为先解密数据、再执行操作符运算、最后再加密输出到Enclave之外。图10展示了一个采用类型III架构的密文查询处理流程^[81]。图中可见，DBMS与数据库均不在服务器端的Enclave中，只有用户认证、查询条件预处理、操作符计算等关键步骤运行于相应的Enclave中。但这种方式引入了信息泄露途径：攻击者通过观察Enclave的行为可以判断每一条加密记录是否满足当前查询条件，在大量观察的基础上可发起密文内容推理攻击。在下一节中介绍了如何通过引入不经意数据库操作算子消除此类信息泄露。

图 10  StealthDB架构与查询处理流程示意图

下载: 全尺寸图片 幻灯片

4.2.2   不经意密文数据库

一般来说，采用类型III架构数据库，由于Enclave中的代码逻辑简洁，极易遭受推理攻击，因而对代码不经意特性的要求更为严格，相关工作包括Opaque^[84], ObliDB^[85]和Obladi^[86]。相比之下，类型I或类型II架构数据库在Enclave中的部分逻辑复杂，并不关注代码不经意特性，威胁主要来自内存访问模式泄露。本节重点介绍现有方案中Oblivious Filter/Select, Oblivious Join, Oblivious Aggregation等基本数据库查询算子构建方法。

(1) Oblivious Filter/Select：Filter算子含义为选择满足条件的元组。经典的做法是将输入记录集合中满足条件的元组写入输出结果集，但这让攻击者通过观察每条记录读入后是否执行写操作，判断该记录是否满足检索条件。Oblivious Filter算子要求让攻击者无法判断密文元组是否满足检索条件。Opaque^[84]中的做法是：首先Enclave读入记录时对每个记录都执行写操作，满足条件写入“1”，否则写入“0”。然后调用不经意排序算子混淆所有密文元组次序，并且所有含“1”的记录排在含“0”的记录之前，最后删除后面含“0”的记录。在ObliDB^[85]中，根据数据库表大小以及返回结果集所占比例不同，提出了多种优化模式，Query Planner根据统计信息，选择适当的优化策略。(1)若Enclave中的不经意内存足够大(至少大于输出结果集的4倍)，采用最为直观的Naive方式，将所有输入记录中满足条件者先保留在内存中，再调用ORAM算子不经意地写入输出数组。(2)当几乎所有元组都满足条件时，可以采用Large模式，读入每条记录后都执行一次写操作，满足条件元组的输出真实内容，若元组不满足条件则执行一个无效写操作(Dummy Write)，该模式下无需使用不经意内存。(3)Small方式适用于返回结果集较小，且有部分不经意内存场景(假设大小为$S$)。此时依次读入所有记录，满足条件者记录在不经意内存中，其余抛弃。若内存被写满，则后续满足条件的元组也被抛弃，但记录下断点位置。本次扫描结束后将内存数据写入输出结果集。若断点不是队尾，则再次扫描全部记录，从上次断点位置开始，将满足条件的记录写入内容。这样通过$\left|R\right|/S$轮的扫描可以将所有满足条件的记录以不经意的方式填入输出集。(4)当满足条件的元组占有连续存储单元时，可以采用一个更为巧妙的方法：若位置i元组满足条件，则将它写入$R\left[i\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{ }\right|R\left|\right]$中($R$为输出结果集)，若不满足条件则执行一个无效写操作。(5)若上述优化都不满足，可以采用Hash模式。若位置$i$元组满足条件则将它写入输出结果集位置$R\left[h\right(i\left)\right]$中，否则就执行无效写操作。考虑到可能产生的位置冲突，需要为每一个位置准备多个槽位(Slot)，且同时为了满足不经意特性，每个写操作都要完成最差情况的所有槽位的读写。例如，若采用2个哈希函数以及5个槽位的配置，则每个记录需要对输出结果集$R$完成$2\times$5=10次写操作。

(2) Oblivious Aggregate：数据库聚集操作Aggregate算子将属性值相同的记录在内存中放在一起，这样不仅容易泄露关于组别的统计信息，还容易泄露记录与组之间的成员关系，在分布式数据库中问题尤为明显，因而需要设计Oblivious Aggregate算子消除该威胁。若所有的数据存储于单一服务器，则可以采用底层的不经意排序算子对该属性进行排序，由于相同组的记录处于相邻位置，通过1次顺序扫描就可以计算出每个组的信息。但对于分布式数据库则情况更为复杂。为了避免泄露分组长度信息，在文献[84]中规定不经意排序操作后每个节点保留的记录数目仍然相同，这样导致某些较大的分组可能会跨越多个节点存储。因而该算子引入跨边界分组处理：扫描每个节点，统计最末尾分组数量，安全发送给下一个顺序节点进行数量合并。文献[85]讨论了Oblivious Aggregate算子实现的几种情况：当内存足够大时(例如足够为每个分组保留4字节计数)，可以在Enclave中设置1个计数器数组，每个用于记录1个分组聚集后的统计值。依次读入每一条记录并更新该计数器数组，对于某个分组或者加1或者简单重复写。由于外部攻击者无法看见写的内容，只能观察访问模式且没有差别，因此通过1次扫描就可以做到不经意聚集，运行时间复杂度为O(|T|)。但当内存条件无法满足时，需要采用类似Opaque^[84]中的不经意排序再统计处理方案，代价为O(|T|log²|T|)。

(3) Oblivious Join：文献[84]通过类似排序-合并连接(Sort-Merge Join)的方式实现Oblivious Join算子。总体思路是先将待连接的两个表${T}_{1}$与${T}_{2}$存入一张新表$T$，然后以飞地安全内存大小的块(Chunks)为单位、对新表数据进行块内快速排序，数值相同时默认${T}_{1}$的记录在${T}_{2}$记录之前，例如某个排序片段为${\cdots T}_{1}.a, {T}_{2}.a{{,T}_{2}.a,T}_{1}.b{,T}_{2}.b\cdots$。在此基础上对排序数据块不断执行合并操作。最后对排好序的新表进行依次扫描，删除不匹配的行，将匹配的行合并输出到Output表。分布式数据库的排序操作还要引入类似于Oblivious Aggregate算子中的跨边界节点处理。ObliDB^[85]采用较为直观的哈希连接(Hash Join)来实现该算子。具体做法是，若${T}_{1}$与${T}_{2}$两个表做连接操作，则在Enclave中设置一个与${T}_{1}$相等大小的表。先扫描${T}_{1}$，对于其中的每一行，计算它的Hash值，然后在${T}_{2}$中查找具有相同Hash值的所有行。若两者相等则将记录写入输出，否则做一个无效写操作；以此类推，直至${T}_{1}$的最后一行。由于依次读${T}_{1}$与${T}_{2}$中的每一行，而且每次都有写操作，所以该算子满足不经意特性，其时间复杂度为O(|${T}_{1}$||${T}_{2}$|)，需要足够的安全内存。若安全内存不够则将引入频繁的内存调换，虽然仍可以满足不经意特性，但性能会进一步受到影响。ObliDB还提供了基于双调排序、无需安全内存的方法，与文献[84]不同，并不需要先在Enclave中对它们分别进行快速排序，而是在两个表的每一行上都针对Join条件进行双调排序。由于双调排序总是执行相同数量的比较操作，与待排序的数据集无关，因而满足不经意特性。当然，若存在一定安全内存该方案也可以进行优化，当待排序的内容足够小时可以一次性放入Enclave，可以在Enclave进行排序防止通信耗费时间。这种做法不影响安全性，但可以减少排序时Enclave与不可信内存之间的通信，从而起到加速内存访问的效果。

5.   隐匿检索PIR

PIR最初旨在让用户从远程公开数据服务器上下载数据，但服务器并不了解用户所访问的具体内容。作为一个基础性的密码原语，目前被广泛应用于安全浏览、匿名通信^[87]等领域。但它最直接的应用是可以为密文数据检索提供支持，在保护数据安全的基础上保护用户查询目的。

PIR从概念上分为两大类，其一是基于信息论安全的IT-PIR，数据库内容复制到非共谋的多个服务器；其二是基于计算安全的cPIR，又称单服务器PIR，基于特定的困难性问题假设单服务器“不超过多项式”的计算能力。前者方案性能高，但非共谋的安全假定在很多场景难以满足，应用范围略受限制；后者的限制性因素为计算代价高昂，在2016年XPIR^[88]出现以前，cPIR性能甚至并不明显优于直接让客户下载整个数据库。但近年来出现的基于格的PIR协议(FHE-based PIR)极大地提升了效率，引发更多关注。考察PIR协议的关键指标包括查询请求尺寸、响应结果尺寸以及服务器端的计算量等。更准确地说，是上述指标与数据库大小的比值。

5.1   单服务器PIR

5.1.1   索引PIR(Index PIR)

所有索引PIR方案的基本假定是用户在查询数据库之前已预知想要查询的数据索引信息。Stern^[89]首次提出了一个基于同态加密的cPIR基础框架，为后续研究奠定了基础。此后采用不同的同态加密算法与技巧，速度不断提升，目前最新的cPIR方案Simple PIR吞吐率约为每秒10 GB，接近IT-PIR吞吐率，接近机器的内存带宽和最快的双服务器隐私信息检索方案的性能。

基本原理如图11所示。假设数据库长度为$d$，客户端将查询目的表示为一个长度为$d$的二进制数组$\boldsymbol{Q}={\left\{\mathrm{0,1}\right\}}^{d}$，其中需要访问的位置$\mathrm{i}\mathrm{d}\mathrm{x}$对应二进制位设为1，其余位置的值设为0。采用Paillier加法同态算法加密每一个比特${q}_{i}$，将加密后的查询向量$\mathrm{E}\mathrm{n}\mathrm{c}\left(\boldsymbol{Q}\right)=\left\{\mathrm{E}\mathrm{n}\mathrm{c}\right({q}_{0}),\mathrm{E}\mathrm{n}\mathrm{c}({q}_{1}),\cdots \}$发送至服务器。服务器将该加密数组中的每一项密文与对应的数据明文相乘再求和，得到的结果$\displaystyle\sum\nolimits_{i=\mathrm{0,1},\cdots ,d-1} \mathrm{E}\mathrm{n}\mathrm{c}\left({q}_{i}\right) \cdot \bf{D}\bf{B}\left[i\right]$返回给用户。根据半同态加密算法的性质，所得结果解密后恰好为$\displaystyle\sum\nolimits_{i=\mathrm{0,1},\cdots ,d-1}{q}_{i}\cdot\bf{D}\bf{B}\left[i\right]= \bf{D}\bf{B}\left[\mathrm{i}\mathrm{d}\mathrm{x}\right]$，即用户感兴趣的数据项。在此过程中，服务器无法判断用户真实访问目的。

图 11  基于同态加密的cPIR基本框架

下载: 全尺寸图片 幻灯片

从图11可以看出，该方案的问题主要体现在要求加密查询向量的长度与数据库长度相等，这不仅带来难以接受的通信代价，用户端的计算量也巨大。XPIR^[88]在此基础上被提出，将数据库由一个长度为N的单维向量改为一个$\sqrt{N}\times \sqrt{N}$的矩阵，将原有的查询也改为两个查询：一个针对行编号向量，一个针对列编号向量，两者联合指示原数据库中的某个特定元组，这样将通信代价由线性降至次线性；此外还利用格上的困难问题Ring-LWE进行同态加密算法的构造，通过对数据采用NTT-CRT的表示方法来实现有限域中快速计算多项式乘积，并快速求解同余多项式，降低了服务器端的计算开销，这是第1个可用于实践的cPIR方案。

为了进一步压缩查询向量，2018年SealPIR方案^[90]提出由客户端直接发送加密位置$\mathrm{E}\mathrm{n}\mathrm{c}\left({x}^{\mathrm{i}\mathrm{d}\mathrm{x}}\right)$，在服务器端将其恢复成加密查询向量再进行后续运算，以取代原有的直接发送加密查询向量的思路。客户端在加密之前，先将查询向量$\boldsymbol{Q}$中的所有比特嵌入到一个明文多项式$p\left(x\right)=\displaystyle\sum\nolimits_{i\in \{1,2,\cdots, N\}}{q}_{i}{x}^{i}$，再采用BFV同态加密算法对该多项式进行加密(当然，为了避免该多项式的次数与N一样大，也可以采用与XPIR类似的技巧，将数据库表示为一个$\sqrt{N}\times \sqrt{N}$的矩阵)；而在服务器端的解压缩算法设计上，作者也巧妙提出利用全同态加密中的替换算子(Substitution)功能将密文Enc$\left(p\left(x\right)\right)$恢复为加密查询向量$\left\{\mathrm{E}\mathrm{n}\mathrm{c}\left({q}_{0}\right),\mathrm{E}\mathrm{n}\mathrm{c}\left({q}_{1}\right),\cdots \right\}\mathrm{的}\mathrm{算}\mathrm{法}$。通过上述处理，可以将客户端的“查询向量”压缩至原本的$1/n$，其中n是BFV密文中的多项式次数，一般取值在${2}^{10}$到${2}^{15}$之间。此外，SealPIR还提出了一种在处理来自同一客户端的多个查询时分摊服务器CPU成本的新技术：采用布谷鸟哈希算法实现PBC (Probabilistic Batch Code)。常见的(n,m,k,b)-batch code表示为n个元素的数据库DB，编码成m个码字，分布在b个桶中，一次同时查询k个元素，且满足总的码字$m < kn$。早在2004年，Ishai等人^[91]就提出了批处理代码(Batch Code)的实现和应用，但在SealPIR之前的批处理代码为了保证能够成功地一次查询k个元素，b的值一般取得过大，导致引入了巨大的通信开销。SealPIR采用布谷鸟哈希来实现PBC，以概率失败为代价，将b的数量降低到了1.5k，每个桶中元素的数量2n/k；对于$k > 200$的情形失败的概率大概仅为${2}^{-40}$。

在XPIR和SealPIR方案中由于采用了数据库的矩阵表示形式，额外引入了密文结果膨胀问题。具体原因为在服务器的同态计算步骤，为了降低噪声积累并提升运算效率，XPIR和SealPIR需要避免数据和多个查询向量出现密文和密文的同态乘法，具体来说，它们在每一步相乘之后都将得到的结果视为明文才进行下一步相乘。此处至关重要的一个效率度量是密文扩展因子，它被定义为密文大小和明文大小之间的比率。对于二者采用的BFV同态加密算法，$F={\mathrm{log}}_{2}q/{\mathrm{log}}_{2}p(q\mathrm{为}\mathrm{密}\mathrm{文}\mathrm{模}，p\mathrm{为}\mathrm{明}\mathrm{文}\mathrm{模})$且一般在${10}^{1}$的数量级。不难看出，如果将数据库表示为d维超立方体，则最终返回的密文大小将高达$O({F}^{d})$级别。受限于噪声增长和查询响应信息的长度，d一般取2而非更大的整数，否则会对最终性能产生影响。

同样是为了避免高代价的密文乘法运算，OnionPIR^[92]另辟蹊径，同时采用第2代BFV算法的第3代同态加密算法GSW^[28]，并利用$\mathrm{G}\mathrm{S}\mathrm{W}\times \mathrm{B}\mathrm{F}\mathrm{V}\to \mathrm{B}\mathrm{F}\mathrm{V}$的“外积运算”来代替BFV密文相乘的运算，在显著减小服务器的查询响应信息(Response Size)的同时大幅降低了计算开销。外积运算输入x的GSW密文和y的BFV密文，输出x·y的BFV密文。外积的优势在于，虽然它也需要进行多次多项式乘法；但若GSW的明文满足一定条件(无穷范数不大于1，在OnionPIR中此条件满足)，则该外积运算积累的噪声仅为线性增长而非BFV密文相乘中的指数增长，因而即便经过多次操作，噪声也很难达到上限。这样带来的结果是，在中间步骤处理密文和查询向量相乘的时候，我们不再需要被迫像XPIR和SealPIR那样分割密文为F块来实现“明文和密文的同态乘法”，而是可以直接将(R)GSW加密的查询向量与BFV密文作外积。

在具体实现方面，OnionPIR将第1维的查询向量用BFV加密，同时让第1维的长度${N}_{1}$远长于其他维的向量${N}_{i}$；这是为了减小外积运算的计算开销。一般而言第1维的查询向量长度为128，其他维的查询向量长度为4，数据库维数d取$1+\left\lceil{\mathrm{log}}_{4}\left(N/128\right)\right\rceil$。同时这些查询向量也可以用SealPIR的方法进行压缩；服务器收到密文之后先用Expand算法得到每一维的查询向量(BFV密文形式)，并将第2维及以后的查询向量(BFV密文)转化为GSW密文形式的查询向量。之后的同态计算步骤如图12所示。

图 12  OnionPIR的基本框架(以数据库表示为3维为例)

下载: 全尺寸图片 幻灯片

SPIRAL^[87]基于以下思路对OnionPIR进行了改进：像文献[93]提出的那样，采用矩阵版本的Regev加密来提高比率(Rate，取回的明文数据大小与响应的大小之比)。

相比于一般的BFV的密文格式$(a,a \cdot s + e + {\varDelta }\cdot m)$，SPIRAL将数据库中的数据视为一些由$n\times n$个多项式组成的矩阵，此时密文格式仅为$(n+1)\times n$的矩阵。如图13所示，不难看出，这样的加密方法$\mathrm{下}\mathrm{比}\mathrm{率}\mathrm{正}\mathrm{比}\mathrm{于}n/(n+1)$，从而明文矩阵维数增大会带来更大的比率，代价是更大的服务器端的计算量。SPIRAL同时提出了一系列算法使得其他部分的计算也适应此处的矩阵运算。值得注意的是，因为(相同明文下)GSW密文尺寸明显大于BFV密文尺寸，故直接将GSW密文作为查询向量传输是相当低效的。针对这个特点，OnionPIR提出了n=1的特殊情况下，BFV密文可以被用于构造(相同密钥加密下的)GSW密文，而SPIRAL对于一般情形进行了讨论。SPIRAL以更大的公共参数为代价，显著提高了比率，减小了查询向量大小和计算开销。

图 13  标量版本的Regev加密和矩阵版本的Regev加密对比

下载: 全尺寸图片 幻灯片

SimplePIR^[94]实现了10 Gb/s核心服务器吞吐量，接近机器的内存带宽和最快的双服务器隐私信息检索方案的性能。与上述PIR相比，SimplePIR最大的特点在于：为了降低在线交互导致的成本，它将大部分昂贵的在线计算和通信转移到了离线阶段。在预处理步骤中，客户端必须下载关于数据库内容的“提示”；这个非在线交互而且可以多次重复给不同用户使用的“提示”节省了大量计算开销。

如图14所示，交互之前，服务器端随机生成矩阵$\boldsymbol{A}$并计算$\bf{d}\bf{b}\cdot \boldsymbol{A}$作为hint。在查询阶段，客户端为了查询第${i}_{\mathrm{r}\mathrm{o}\mathrm{w}}$行第${i}_{\mathrm{c}\mathrm{o}\mathrm{l}}$列的数据，需计算$\left(\boldsymbol{A}\boldsymbol{s} + \boldsymbol{e} + {\varDelta }\cdot {\boldsymbol{u}}_{{i}_{\mathrm{c}\mathrm{o}\mathrm{l}}}\right)$(这里${\boldsymbol{u}}_{{i}_{\mathrm{c}\mathrm{o}\mathrm{l}}}$指仅在第${i}_{\mathrm{c}\mathrm{o}\mathrm{l}}$位为1其他位全0的向量，$\boldsymbol{s}$是客户端随机生成并持有的密钥，$\boldsymbol{e}$是噪声)作为查询向量。服务器端将db和qu直接相乘得到ans，客户端只需要利用密钥$\boldsymbol{s}$, hint, ${i}_{\mathrm{r}\mathrm{o}\mathrm{w}}$和ans即可解密出所需数据。由于hint的大小与数据库大小有关，在数据库过大的情况下，预处理步骤会导致客户端下载过大的数据。因此，为了解决这个问题，simplePIR的作者提出了doublePIR，本质上类似于将simplePIR实施两次，以折中的方式将用户端的hint的大小缩减到了常数级。而同时期的FrodoPIR^[95]也提出了与SimplePIR几乎一致的构造，只不过在数据库的形状上有所区别(SimplePIR将数据库当作$\sqrt{N}\times \sqrt{N}$的矩阵，而FrodoPIR将数据库当作$N\times \omega$的矩阵)，故不在此赘述。

图 14  SimplePIR方案^[94]示意图

下载: 全尺寸图片 幻灯片

像SimplePIR这类客户端和服务器事先准备离线内部状态，用于进行在线查询的PIR方案称为Stateful PIR；与之相对，仅有在线阶段的PIR方案则被称为Stateless PIR。对于Stateless PIR而言，每次查询会给服务器带来至少${O}\left(n\right)$的计算量；而Stateful PIR的意义正在于突破这个“下限”。当前一个比较热门的Stateful PIR方向以PIANO PIR^[96]为代表，其思路大致为在离线预处理阶段，客户端选择一些大小为$\sqrt{n}$的index集合，并对每个集合获取这$\sqrt{n}$个位置的数据的异或作为自己的hint。在这个阶段，服务器无法得知关于这些hint的任何信息。在线查询阶段，客户端为了查询index为$x$的数据，需要先找到一个hint中的集合$S$使之包含$x$，随后通过向服务器查询集合${S}{{'}}$对应数据的异或，计算出集合$S\backslash \left\{x\right\}$对应数据的异或，从而得到数据$\bf{D}\bf{B}\left[x\right]$。在整个流程中，客户端存储的hint数据量为$\stackrel{～}{O}\left(\sqrt{n}\right)$，而对于每次查询，服务器的在线计算量为$O\left(\sqrt{n}\right)$，小于Stateless PIR中的$O\left(n\right)$计算量。

表1列出了不同方案的安全性、查询尺寸、响应尺寸以及服务器端计算量对比，注意到XPIR, SealPIR, OnionPIR的查询尺寸、响应尺寸为多项式数量，而SimplePIR, FrodoPIR则代表整数数量。此外，虽然所有基于同态加密的PIR方案服务器端计算复杂度均为$O\left(n\right)$，但SimplePIR, FrodoPIR的计算量要明显低于其他方案。

表 1  PIR技术比较

	安全性假设	查询尺寸	响应尺寸	计算量
XPIR[88]	基于Ring-LWE困难性假设	$O\left(\sqrt[d]{n}\right)$	$O\left({F}^{d-1}\right)$	$O\left(n\right)$
SealPIR[90]	基于Ring-LWE困难性假设	$O(\sqrt[d]{n}/N)$	$O\left({F}^{d-1}\right)$
OnionPIR[92]	基于Ring-LWE困难性假设	$O(\sqrt[d]{n}/N)$	$O\left(1\right)$
SimplePIR[94]	基于LWE困难性假设	$O\left(\sqrt{n}\right)$	$O\left(\sqrt{n}\right)$
FrodoPIR[95]	基于LWE困难性假设	$O\left(n\right)$	$O\left(1\right)$
PIANO PIR[96]	统计安全	$O\left(\sqrt{n}\right)$	$O\left(1\right)$	$O\left(\sqrt{n}\right)$

下载: 导出CSV 

| 显示表格

5.1.2   关键词PIR(Keyword PIR)

Keyword PIR是PIR的另一个分支，由于Index PIR研究的前提是用户已知数据在服务器处的索引位置，而现实中更普遍的情况是用户不知道数据索引，只知道自己需要查询的数据项的提示。例如在KV数据库中，用户根据自己持有的Key查询得到相对应的值。Keyword PIR研究的问题在于如何让用户以不经意的方式发起关键词查询并获得正确结果，并通过尽量少的交互轮次(如1轮交互)实现该目标。

Keyword PIR协议高层框架如图15所示，以同态加密的方式让查询关键词与服务器上的关键词依次进行等值比较，得到一个同态加密的1/0向量，然后再采用Index PIR协议得到加密的数据项。

图 15  Keyword PIR协议高层框架示意图

下载: 全尺寸图片 幻灯片

显然可以看出，其中最为关键的问题是如何高效、不经意地实现等值算子。最直观的同态比较算子的实现是将待比较关键词分别表示为长度为$\ell$的二进制串$x$与$y$，$x,y\in {\left\{\mathrm{0,1}\right\}}^{\ell }$，那么等值算子$f(x,y)$可以表示为$f={\prod }_{i\in \{\mathrm{0,1},\cdots ,\ell -1\}}(1-\left(x\right[i] -y[i\left]\right)^{2})$ 或 $f={\prod }_{y\left[i\right]=0}(1-x[i\left]\right){\prod }_{y\left[i\right]=1}x\left[i\right]$，采用同态加密算法实现时，其同态乘法深度为$1+\left\lceil{\mathrm{log}}_{2}\ell \right\rceil$与$\left\lceil{\mathrm{log}}_{2}\ell \right\rceil$。

为了降低同态密文乘法深度，CWP^[97]提出采用常重码Constant-Weight-Code进行优化，将关键词编码成长度为$m$，汉明重量为$k$的比特串，表示为$\mathrm{C}\mathrm{W}(m,k)$。并给出了相应的基于常重码的等值算子：若$x,y\in \mathrm{C}\mathrm{W}(m,k)$，可以表示为$f={\prod }_{y\left[i\right]=1}x\left[i\right]$，此时其同态乘法深度为$\left\lceil{\mathrm{log}}_{2}k \right\rceil$。由于等值算子的乘法深度只与常重比特串的汉明重量$k$有关，与之前的等值算子相比，计算时间缩短了超过10倍。查询时，用户将所需检索的关键词编码为常重比特串，并将常重比特串的每一比特作为多项式系数嵌入到一个明文多项式，利用FV同态加密方案进行加密，发送给服务器。而服务器收到密文多项式后，先采用类似Seal PIR中的做法将其扩展成加密的比特向量，对数据库中每个关键词的常重比特串与加密的比特向量计算等值算子$f={\prod }_{y\left[i\right]=1}x\left[i\right]$，得到的密文向量与数据库中的明文进行内积，并将内积后的密文返回给用户。用户将服务器的响应进行解密，得到的即为检索结果。该方案是第1个较为实用的单轮交互的基于关键词检索的PIR方案，但该方案要求额外的预计算：将所有关键词提前转换为尺寸更大的比特串。例如，当关键词尺寸为32位，汉明重量为3时，需要将关键词转化为一个2955 bit的比特串。因此，当数据库中键值对的数量庞大时，这种预计算的代价过大。

Pantheon^[98]放弃了采用逐位比较的方式，采取了全新的思路实现同态计算等值算子。要求客户端将要检索的关键词复制至预设长度形成查询向量，采用BFV密码系统对其加密，将密文向量发送给服务器。服务器端采取了3个步骤进行计算，如图16所示。

图 16  Pantheon^[98]步骤示意图

下载: 全尺寸图片 幻灯片

第1步，做减法。服务器将接收到的密文向量与明文关键词向量对应位相减，所得的结果为加密的差值向量。显然，只有当查询关键词与第i位的关键词相等时，差值向量的第i位为Enc(0)，其他位均为非0值的密文。第2步，标准化。服务器将差值向量中所有的非0值成员转化为1，而0值成员保持不变。方法是采用费马小定理(若p是素数且不是a的因子，那么${a}^{p-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$)，对上一步的结果进行密文指数运算，得到仅由0、1组成的密态向量。第3步，求反。为了与Index PIR对接，密态向量需要做一个取反的操作，将所有的0与1互换。方法比较简单，只需要用全1向量的密文与之相减即可。

为了提升方案的可伸缩性，Pantheon方案中将长度较大的关键词进行分块，例如：当选取的BFV明文模数为p=17，即长度为${\mathrm{log}}_{2}(p-1)=4$ bit时，若关键词长度为19 bit，则首先将关键词长度填充为模数长度的倍数20 bit，再将其分割成5块，此时一个关键词需要编码成5个明文，并对每个部分依次进行后续计算。这也意味着Pantheon方案的计算代价与关键词长度呈线性增大，而Constant-Weight PIR方案则是超线性增大。

由于利用第2代全同态加密方案BFV支持单指令多数据的特性，将多个关键词打包到1个密文中，通过1次密文的等性检验运算实现多次关键词比较的并行运算，这使得方案效率得到大幅度提升。与Constant-Weight PIR方案相比，服务器端的响应效率提升了约93倍，例如，对于存储1.6万个键值对且关键词尺寸为32 bit的数据库，使用Pantheon方案时服务器端的响应时间为1.15 s，而使用Constant-Weight PIR方案时服务器端的响应时间为107.8 s。此外，Pantheon方案可以支持服务器端的并行计算，其性能和可伸缩性得到了更好的体现，它是首个实现了对兆级键值对数量的秒级响应的方案。

在OT (Oblivious Transfer)方面的一些成果也可以用于构造Keyword PIR。在利用OT构造PIR时，其中一个优化方向是减少双方交互的通信代价。文献[99]指出，通过构造rate-1 OT(指满足如下条件的OT协议：发送方在协议中发送的密文长度$\left|\mathrm{o}\mathrm{t}\mathrm{s}\right|$与消息长度$\left|{m}_{0}\right|$满足：随着$\left|{m}_{0}\right|$增大，$\dfrac{\left|\mathrm{o}\mathrm{t}\mathrm{s}\right|}{\left|{m}_{0}\right|}\to 1$)可以实现一些强大的应用，如(1)用于分支程序的半紧凑同态加密(其中密文仅随着程序的深度而增长，而不是随着程序的大小而增长)以及(2)通信高效的隐匿检索(PIR)协议。在这些应用中，rate-1 的性质本质上使得当接收者只对数据库的一部分感兴趣时，发送方可以将整个数据库压缩，从而减小发送方的通信代价。在PIR中，这个性质可以大幅减小服务器到客户端的通信代价。文献[100]利用rate-1 OT实现了相应的PIR构造；在此基础上，文献[101]利用双线性群构造了amortized rate-1 OT，对接收者的通信代价进行了优化。

此外，还有基于批处理的优化PIRANA^[102]与BatchPIR等，通过引入Batch Code以及SIMD并行处理进行多查询优化，性能目前最优(优于SPIRAL)。以及针对稀疏数据集的优化方法SparsePIR^[103]。

5.2   多服务器PIR

1998年，Chor等人^[104]首次提出PIR模型并证明在信息论安全的条件下单服务器的PIR协议的最优方案即是平凡方案：将整个数据库返还给用户。基于此证明，后续的多服务器PIR协议设计通常假设各服务器本地持有数据库的完整副本，同时希望借助多服务器的交互模型设计更为高效的协议。至今多服务器PIR协议发展与演变经历了多个过程。

(1) $\boldsymbol{K}$-服务器PIR协议：最初的协议称为$K$-服务器PIR协议，假定所有服务器同时在线且不存在服务器间的串通。直观的做法是将数据库转换为高维矩阵，用户将索引$i$表示成高维数组$({i}_{1},{i}_{2},\cdots ,{i}_{\mathrm{l}\mathrm{g}K})$，任选$\mathrm{l}\mathrm{g}K$个随机子集${S}_{1},{S}_{2},\cdots ,{S}_{\mathrm{l}\mathrm{g}K}$，构造$\mathrm{l}\mathrm{g}K$个子集对$({S}_{1}^{0},{S}_{1}^{1}),({S}_{2}^{0},{S}_{2}^{1}),\cdots ,({S}_{\mathrm{l}\mathrm{g}K}^{0},{S}_{\mathrm{l}\mathrm{g}K}^{1})$，这里${S}_{t}^{0}={S}_{t}, {S}_{t}^{1}={S}_{t}\oplus{i}_{t}$，根据服务器编号的二进制将对应的$\mathrm{l}\mathrm{g}K$个子集发送给服务器，服务器计算下标索引属于这些子集的值的异或值返回给用户，用户计算这些返回值的异或值得到索引值，该方案的通信复杂度是${O}\left(k{n}^{1/\mathrm{lg}K}\right)$。Chor等人^[104]在此基础上将其改进得到一个2-服务器下的通信复杂度为${O}\left({n}^{1/3}\right)$的协议，Ambainis^[105]使用递归与归纳法得到一个复杂度为${O}\left({n}^{1/2K-1}\right)$的协议，之后数年多项工作仅优化该上界的常数部分，直到2002年Beimel等人^[106]打破了这个障碍，利用多元多项式的构造得到了${O}\left({n}^{\mathrm{lg}\left(\mathrm{l}\mathrm{g}K\right)/K\mathrm{l}\mathrm{g}K}\right)$的结果。Beimel的想法是构造一个多元多项式${P}_{X}({x}_{1},{x}_{2},\cdots ,{x}_{n})$与$n$个汉明重量小于指定常数的索引向量$L\left(1\right),L\left(2\right),\cdots ,L\left(n\right)$满足${P}_{X}\left(L\right(i\left)\right)= x\left[i\right]$，然后对索引向量$L\left(i\right)$用户做加法分享$L\left(i\right)= \displaystyle\sum\nolimits_{j=1}^{K}{{y}_{i}}$。关键的一步是用户给每个服务器分发$\left\{{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{K}}\right\}$的指定真子集，这样他们就可以利用这些“部分”信息去计算${P}_{X}\left(L\right(i\left)\right)$的多项式展开中的若干指定单项式，利用已知“部分”信息可以将指定的多项式化简为次数更小的多项式，然后得到的简化多项式的未知系数可以由其在$\left\{\overrightarrow{{y}_{1}},\overrightarrow{{y}_{2}},\cdots ,\overrightarrow{{y}_{K}}\right\}$中的补集进行计算。之后服务器与拿到补集信息的服务器做多服务器PIR协议，再次利用递归得到上述优化的结果。

(2) l选k协议：若考虑到通信带宽、网络延迟等因素，前述所有非共谋服务器同时在线假定无法满足，后续研究者提出l选k协议：对于l服务器的协议，用户只需要得到其中k个服务器的返回值即可恢复出目标的索引值。显然，用户做$\left(\genfrac{}{}{0pt}{}{l}{k}\right)$次对每个k-服务器子集做基础的k-服务器PIR协议可以实现，但此平凡方案的通信代价极为高昂。Beimel等人^[107]给出的方案是用户首先生成若干独立的基于k-服务器PIR协议的索引询问，目标是将这些独立的询问分发给所有服务器，期望在返回值中能根据鸽笼原理保证存在一个k-服务器PIR协议的回答。以$l$选2协议为例：假设目前有一个2-服务器协议，用户生成d个独立的索引询问$\left\langle{{Q}_{1},{Q}_{2},\cdots ,{Q}_{d}}\right\rangle$，这里${Q}_{i}=\left({Q}_{i}\right(0), {Q}_{i}(1\left)\right),d=\mathrm{l}\mathrm{g}l$。对于每个服务器的编号$1\le j\le l$，考虑其二进制表示${b}_{1}^{j}{b}_{2}^{j}\cdots {b}_{d}^{j}$，那么用户发给第$j$个服务器$d$个询问子元素：对于$1\le t\le d$，发送${Q}_{t}\left({b}_{t}^{j}\right)$给第$j$个服务器。由于这$l$个服务器中至少有两个服务器响应，且其对应的二进制表示至少在某一位不同(记为第$a$位)，那么这两个服务器的返回值一定包含对${Q}_{a}=\left({Q}_{a}\right(0),{Q}_{a}(1\left)\right)$的回答，所以用户可以遵循2-服务器协议恢复出目标索引值，而由于这$d$个询问是独立的所以该方案不泄露任何信息。从k-服务器PIR协议扩展到$l$选k协议的思路类似，只不过此时的询问拆分与分发需要更精细，我们需要用到完美哈希族等密码学原语，具体可参考文献[107]。

(3) t-隐私PIR协议：进一步地，在多服务器的协议中服务器之间的可能串通或腐化是需要纳入安全性的考量中。我们定义允许其中$t$个服务器腐化却能保证不泄露信息的PIR协议称为$t$-隐私PIR协议。另一个类似的定义是纠错性，定义用户可以恢复出正确的索引值但允许服务器返回的回答中包含至多b个错误回答称为b-纠错PIR协议。对隐私性与纠错性的保证可以使用Reed-Solomon纠错算法^[108]得以实现，在此不做过多赘述。此外，目前也有研究将纠错性放宽为概率性的要求(用户成功恢复的概率至少为$1-\varepsilon$)，具体可参考文献[109]。

(4)基于本地可解码代码(Locally Decodable Codes, LDC)与匹配向量族(Matching Vectors Family, MVF)的PIR协议：另一项与多服务器PIR密切相关的工作是本地可解码代码，LDC是一种纠错码，具有确定性的编码功能与随机化的解码功能，允许通过多次查询以高概率和次线性时间恢复出任何消息位。在文献[110]中已经证明具有少量服务器的高效k-服务器PIR协议可以转化为高效k-LDC协议，所以在LDC渐近复杂度上的突破势必会带来多服务器PIR协议的进展。其中Yekhanin^[111]和Efremenko^[112]的工作显著地优化了LDC协议的渐近复杂度，特别地，Efremenko的构造可以生成一个3-服务器PIR协议，得到${2}^{{O}\left(\sqrt{{\mathrm{log}}_{2}n{\mathrm{log}}_{2}{\mathrm{log}}_{2}n}\right)}$的通信复杂度改进以及${O}\left(1\right)$的返回用户消息。他们的工作建立在将匹配向量族引入LDC的构造中，给定集合$S\subset {\mathrm{Z}}_{m}\backslash \left\{0\right\}$，一个MVF满足如下条件：存在两个向量集合，$\boldsymbol{F}=(\boldsymbol{U},\boldsymbol{V}),\boldsymbol{U}=({\boldsymbol{u}}_{1},{\boldsymbol{u}}_{2},\cdots,{\boldsymbol{u}}_{k}),\boldsymbol{V}= ({\boldsymbol{v}}_{1},{\boldsymbol{v}}_{2},\cdots,{\boldsymbol{v}}_{k})$，如果i=j，则$\left\langle{{\boldsymbol{u}}_{i},{\boldsymbol{v}}_{i}}\right\rangle=0$；如果$i\ne j， \mathrm{则}\left\langle{{\boldsymbol{u}}_{i},{\boldsymbol{v}}_{i}}\right\rangle\in S$。这样的一个特殊结构可以明显优化LDC构造中的代数多项式结构从而得到方案上的改进，最早在文献[113]中已有研究。在此基础上，研究者还得到了类似的2-服务器PIR协议^[114]以及效率优化之后的协议^[115]。

(5)基于分布式点函数与函数秘密分享的PIR协议：另一个重要的多服务器PIR协议的领域是基于分布式点函数(Distributed Point Function, DPF)的秘密分享，于2014年由Gilboa等人^[116]提出并将其引入PIR的领域，之后与Boyle等人^[117]在2015年将DPF推广为函数秘密分享(Function Secret Sharing, FSS)，目前有非常多的工作是使用DPF和FSS构造多服务器PIR协议。其基础想法是将一个点函数拆分为若干个子函数的和，相当于对每一个点函数的值做一次加法秘密分享，其满足只有知道所有的子函数才可恢复出原点函数，知道任意子函数集的真子集不泄露点函数的信息。目前的可行方案是基于伪随机生成器(PRG)或单向函数(One-Way Function)，所以大部分方案是计算安全的。以普通的基于DPF的2-服务器PIR协议举例说明：对于用户的索引i，用户构造一个点函数$f:\left[n\right]\to {\mathrm{Z}}_{2}$满足$f\left(a\right)=1,a=i;f\left(a\right)=0,a\ne i$，根据DPF用户生成两个密钥${k}_{1},{k}_{2}$，接着用户将密钥分发给两个服务器，服务器计算响应算法得到子函数$\mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(i,{k}_{i},x)= {f}_{i}\left(x\right)$并满足$\forall x\in \left[n\right],{f}_{1}\left(x\right)+{f}_{2}\left(x\right)=f\left(x\right)$，最后服务器返回数据库向量与子函数值向量的点积$\displaystyle\sum\nolimits _{j=1}^{n}{f}_{i}\left(j\right)\cdot x\left[j\right]$，用户做本地加法得到$x\left[i\right]=\displaystyle\sum\nolimits_{i=1}^{2} \displaystyle\sum\nolimits_{j=1}^{n} {f}_{i}\left(j\right)\cdot x\left[j\right]$。具体流程如图17所示。

图 17  基于DPF的2-服务器PIR协议示意图

下载: 全尺寸图片 幻灯片

6.   总结与展望

本文主要围绕隐私保护密文数据的检索展开综述，分别介绍了多样化密文检索、基于TEE的密文检索和隐匿信息检索等方面的代表性研究成果。通过分析现有的密文检索方案，未来的研究工作可以关注以下几点：

(1) 基于全同态加密的零隐私密文检索被越来越多的研究者关注。随着全同态加密算法实现技术突破时间的临近，基于全同态加密算法的方案也将在未来一段时间内应用于各类密文计算场景，解决实际问题。在某些高安全场景，基于同态加密算法实现的零隐私泄露密文检索方案，取代传统基于泄露函数最小化的技术思路为更多用户接受。因此，如何结合全同态加密的最新进展设计密文检索协议，提升零隐私密文检索方案效率是未来的研究工作之一；

(2)与新型TEE架构结合是未来技术改进的可能方向之一。当前TEE研究也在不断发展之中，不断涌现各种新型结构，为基于TEE的密文检索提供新思路。以前文提到SGX环境为例，新型轻量级飞地架构^[79]实现单个飞地内多个代码区域的轻量级隔离，相对于不同飞地之间切换的高昂代价而言，性能更具优势。因此，结合新型TEE架构设计高性能的密文检索方案将更具吸引力。

(3)基于TEE与数据不经意化技术的结合将成为关注的热点。领域内公认不经意技术会带来巨大的性能代价，与那些非不经意版本或部分不经意版本相比，查询响应速度存在明显差异^[67,84–86]。由于数据不经意化技术的代价高昂，近期出现了DP-Oblivious相关工作，如Shrinkwrap^[118]采用完全不经意的算子但采用满足差分隐私的填充，极大地降低了中间的查询结果集大小。文献[119]采用了新的定义设计出满足DP-Oblivious的算子。因此，如何设计基于TEE与数据不经意化技术的密文检索方案成为未来的研究工作之一。