杨光远 杨大利 张 羽 马利民 张 伟

1(北京信息科技大学计算机学院 北京 100101)

2(国家信息中心信息网络安全部 北京 100045)

(guangyuany86@163.com)

可搜索加密(searchable encryption, SE)[1-2]的设计是使用户能够将自己的数据安全地外包到服务器，同时保留查询和搜索功能.SE被认为是建立加密数据库，防止隐私数据泄露最有前途的解决方案.通用的解决方案如全同态加密、安全多方计算等，虽然增强了数据的安全性，但增加了大量的计算和通信开销.属性保留加密，如确定性加密是有效的，但这些解决方案在实际应用[3]中并不安全.近年来，SE方案的快速发展具备了更多的功能和更高的安全性[4-5].

在动态SE中，前向隐私的概念是指新添加的数据和之前发布的搜索查询之间的链接应该隐藏在服务器上，后向隐私的概念是指删除的数据和删除后的搜索查询之间的链接应该隐藏.现有的前向和后向隐私SE方案[6-7]在客户端和服务器端都引入了大量的存储和计算开销，增加了客户端和服务器之间的交互.为了提高SE的效率，一种方法是采用硬件辅助的方案，例如Intel SGX，它可以在受信任且隔离的执行环境中执行本机代码和数据，从而减轻客户端存储和计算的开销，并减少客户端和服务器之间的通信成本.

Amjad等人[8]提出了第1个使用SGX的前向和后向隐私SE方案.方案中数据的添加和删除对服务器是完全不知情的.但是，由于SGX和服务器之间的高I/O复杂性，这种方法仍然是低效的.后来他们在安全性和更高的效率之间进行权衡，提出了Bunker-B[8].文献[8]中给出了Bunker-B的理论构造，但是它是不可扩展的，尤其是在处理大型数据集时.首先，删除操作是通过插入操作实现的，这将导致2个问题：1)导致SGX与服务器之间的通信成本较高；2)由于所有删除的数据都需要从搜索结果中检索、解密和过滤掉，这就会增加搜索延迟.

为了避免SGX的引入而导致的潜在性能瓶颈， 本文利用SGX enclave充分发挥客户端的作用,enclave将同时缓存关键字状态和删除操作，以减少SGX与服务器之间在搜索、添加和删除操作中的通信成本和往返次数，并使客户端几乎没有任何计算和存储上的额外消耗.1)本文设计并实现了前向和后向隐私SE方案，称为TSE.TSE利用SGX套件跟踪关键字状态和数据删除，以最大程度地减少SGX和不受信任的内存之间的通信开销.2)我们在数据集上进行实验并对数据进行了分析，结果表明提出的技术相较于之前的技术降低了通信成本，查询效率有所提高.向数据库中插入106条数据时的ecall/ocall调用次数仅为Bunker-B方案的10%.

1 相关工作

可搜索加密:Song等人[1]提出了第1个可搜索加密(SE)，可以对加密的数据进行搜索.古宜平等人[2]和Kamara等人[9]分别对静态和动态SE的安全定义进行相关研究，并提出了具有次线性搜索时间的方案.自从SE研究以来，一系列的相关研究开始致力于提高查询效率[10]和支持表达性查询[11].

可信执行环境中的密文搜索: 文献[8,12-14]的研究是利用可信执行环境(TEE).通常，TEE(例如Intel SGX)可以减少客户端和服务器之间的网络通信，并增加加密数据库功能.Fuhry等人[14]提出了HardIDX，它以B+树结构构建数据库索引，并利用enclave遍历树节点的子集进行搜索.文献[8]提出了3种方案来启用具有不同搜索泄露(即服务器可以从中获悉有关查询和数据的信息)的单关键字查询.但是，他们尚未研究这些方案的实际性能.同时，Ren等人[15]提出了一种通过SGX的隐藏范围查询方案.

2 相关知识

2.1 Intel SGX

Intel SGX是一组x86指令集，旨在提高应用程序代码和数据的安全性[16-17].在启用SGX的平台上，需要将应用程序划分为受信任部分和不受信任部分.受信任的部分称为enclave，位于物理RAM的专用内存部分中，由SGX实施强保护.不受信任的部分作为普通进程执行，并且只能通过名为ecall的明确定义的接口调用enclave，而enclave可以加密明文数据并通过名为ocall的接口发送给不受信任的代码.此外，当将数据加载到enclave内时，将执行解密和完整性检查.所有其他软件，包括操作系统、特权软件、虚拟机管理程序和固件，都无法访问enclave的内存.在enclave中用于存储数据的实际内存最多只有96 MB[18].在此之上，SGX将自动应用页面交换. SGX还具有远程认证功能，该功能允许在远程服务器上验证enclave的创建，并创建与enclave的安全通信通道.

2.2 动态搜索对称加密

动态SE中的前向和后向隐私：按照文献[4-5]中的表达，DB代表数据库，每条具有唯一标识符id的数据是一个可变长度的唯一关键字集.我们使用DB(w)来显示出现关键字w的数据集. 关键字-数据对的总数用N表示，W是DB中不同关键字的总数.indexMI是一种字典结构，用来存储所有N个关键字-数据对，将每个唯一关键字w映射到DB(w)中的匹配列表.名为EDB的加密数据库是加密数据的集合.动态SE方案Σ=(Setup，Search，Update)由客户端和服务器之间的3个协议组成，如下所示:

1) Setup(1λ,DB).协议输入1个安全参数λ，输出1个密钥K，1个客户端状态ST和1个加密数据库EDB.

2) Search(K,w,ST;EDB).协议允许在客户端根据状态ST、密钥K和状态ST查询w，在服务器端根据加密数据库EDB查询w.然后输出搜索结果Res.

3) Update(K,(op,in),ST;EDB).该协议接收K、ST、一个与客户端操作op相关的输入以及EDB，其中op∈{add,del}，in由数据标识符id和该数据中的一组关键字组成.然后，协议执行op操作时从EDB插入或删除数据.

3 问题分析及算法设计

3.1 问题分析

Amjad等人[8]提出了3种采用SGX支持的向后隐私的方案:Type-I方案Fort，Bunker-B和Bunker-A.Fort是最安全的，但是由于其开销较大，本文不对其进行研究.Bunker-A不执行重新加密和重新插入，只实现向后隐私.因此，本文主要分析Bunker-B的局限性，Bunker-B协议总结如下所示.

协议1.Bunker-B: update和search协议.

① Update(op,in):

/*op∈{add,del},in=(w,id)*/

② client从st检索stw=(version,

count);

③ 发送(w,version,count,op,id)到

enclave;

④ client更新st中的stw=(version,

count+1);

⑤ enclave生成update令牌utk=(u,v):

uFK1(w‖version‖count+1),

vEnc(K2,id‖op);

⑥ enclave发送sutk到server;

⑦ server从enclave中检索sutk=(u,v);

⑧ server更新mapMI[u]=v

⑨ Search(w):

⑩ client从st检索stw=(version,count);

enclave的st;

count);

count);

qtk=(u1,u2,…,ui,…,ucount),其中:

v2),…,(uc,vc)}到enclave;

键字-数据对；

∈L}过滤未删除的ids;

Bunker-B的性能分析:对于每个(w,id),Bunker-B让enclave遵循相同的例程来生成用于添加和删除的令牌，并使用生成的令牌来更新服务器上的MI(协议1中的⑤).然而,它会导致高计算复杂度,并且在搜索过程中涉及到大量的数据传输.在Search协议中，Bunker-B的核心思想是让enclave读取MI中与关键字对应的所有记录(与add或del相关).然后，enclave对它们进行解密，并根据操作过滤被删除的id.查询之后，enclave重新加密未删除的id，并将新生成的令牌发送到服务器进行更新.这些步骤总结在协议1的第～行中.本文复现了Bunker-B(见第4节的实验)，发现该方案在实践中还存在以下局限性:1)密集ecall/ocall调用.将具有标识符id和M条唯一关键字的数据提供给服务器，Bunker-B通过使用M次ecall，然后使用相同数量的ocall重复执行更新协议，以将令牌插入索引映射MI.2)搜索延迟.每次搜索都会对未删除的id重新加密，这使得Bunker-B效率降低.

3.2 系统概述

通过分析Bunke-B具有的一些限制，我们设计了TSE，TSE的整体架构如图1所示:

图1 TSE系统整体架构及工作流程

TSE方案涉及3个实体:客户端(数据所有者，因此是受信任的)、不受信任的服务端和服务器内受信任的SGX enclave，系统工作流程包括11个步骤.

在步骤1中，客户端使用SGX认证功能对enclave进行身份验证，并与enclave建立安全通道. 然后，客户端通过此通道将密钥K提供给enclave. 这样就完成了协议中的Setup协议.

在步骤2中，为客户提供具有唯一标识符id的数据，客户端管理器使用密钥K加密数据，并将数据的加密版本发送到服务器管理器(步骤3).然后将带有id的加密版本插入到EDB中.客户管理器通过安全通道将原始数据发送到位于enclave的状态管理器(步骤4).在此步骤中，状态管理器执行加密操作以生成将被发送到服务端管理器的更新令牌(步骤5).令牌用于更新位于服务端管理器中的动态SE的加密索引.动态SE MI的索引位于服务器管理器中，而加密数据存储于加密数据库EDB中.要删除具有给定id的数据(步骤6)，客户端管理器直接将数据id发送给状态管理器(步骤7).

在步骤8中,客户端想要搜索包含给定查询关键字w的数据.客户端管理器将关键字w发送给状态管理器(步骤9).然后,状态管理器计算查询令牌并排除标记为删除数据.之后，状态管理器将它们发送到服务器管理器(步骤10).服务器管理器将搜索接收到的令牌，并将加密的匹配数据列表返回给客户端管理器，并用K解密加密的数据.

3.3 系统的假设和威胁模型分析

对Intel SGX的假设:本文假设SGX是可信的(即没有硬件错误或后门)，并且enclave内的预置代码和数据是受到保护的.此外，客户端和enclave之间的通信依赖于SGX认证期间创建的安全通道.和其他SGX应用程序[19]一样，对SGX的[20]的侧边通道攻击不在我们的范围内.拒绝服务(DoS)攻击也不在我们的关注范围之内，也就是说，enclave总是在客户端调用或查询时可用.最后，我们假设SGX使用的所有加密原语和库都是可信的.

威胁模型:根据文献[17],我们认为服务器端有一个半诚实但强大的攻击者.尽管攻击者不会偏离协议，但可以通过enclave之外的软件堆栈、操作系统和管理程序，以及服务器中的硬件组件(处理器包除外)获得完全访问权.攻击者可以在内存总线上、内存中或EDB中观察内存地址和(加密的)数据，以生成数据访问模式.此外，攻击者可以记录这些内存操作发生时的时间.

3.4 TSE算法思想及伪代码

TSE的基本思想是让enclave存储关键字的最新状态ST，并保留已删除数据的数据id的列表d，方便后期搜索使用.然后，enclave仅在2次删除操作之间加载用于第1次搜索的被删除的数据，以便于更新删除的id和查询的关键字之间的映射.在2次删除更新之间的后续搜索不需要再次加载删除的数据.我们注意到，enclave在第1个查询中检索到d后显然需要删除d，以保存enclave的存储.一旦enclave知道查询关键字和已删除数据之间的映射，它就会推断查询关键字与其余未删除数据的映射，以便生成查询令牌. 之后，服务器根据接收到的令牌检索数据，并将数据结果列表返回给客户端.接下来将结合协议伪代码进一步解释协议，Setup协议如下所示:

协议2.Setup(1λ).

client:

①kΣ,kf←{0,1}λ；

② 启动远程认证；

③ 建立安全的渠道;

④ 发送K=(kΣ,kf)到enclave;

enclave:

⑤ 初始化ST和D:

⑥ 初始化一个列表d;

⑦ 初始化T1和T2;

⑧ 接收K=(kΣ,kf);

server:

⑨ 初始化MI和Mc;

⑩ 初始化存储库R.

在Setup过程中，客户端在建立的安全通道上与enclave通信，以提供K=(kΣ,kf)，其中kΣ使enclave域能够生成更新/查询令牌，而kf是用于数据加密/解密的对称密钥.enclave维护映射ST和D以及列表d，其中ST存储关键字的状态，D表示关键字和已删除数据之间的映射，d是已删除id的数组.服务器保存1个加密索引MI、加密状态Mc的映射、带有R[id]的存储库R存储数据标识符id的加密数据.

如下为TSE的Update协议流程：

协议3.Update(op,in).

client:

① ifop=add then

②f←Enc(kf,data);

③ 发送(id,f)到server;

④ end if

⑤ 发送(op,id)到enclave;

enclave:

⑥ ifop=add then

⑦f←R[id];

⑧ {(w,id)}←Parse(Dec(kf,f));

⑨ foreach (w,id) do

⑩kw‖kc←F(kΣ,w);

server:

如下为TSE的Search流程：

协议4.Search(w).

client:

① 发送w到enclave;

enclave:

②stwc←{∅},Qw←{∅};

③kw‖kc←F(kΣ,w);

④ foreachidiinddo

⑤fi←R[idi];

⑥datai←Dec(kf,fi);

⑦ ifwindataithen

⑧D[w]←idi∪D[w];

⑨ 删除R[idi];

⑩ end if

server:

client:

4 实验及数据分析

4.1 实验设置

实验设置与实现:本文选择了Enron电子邮件数据集(1.4 GB)，使用C++和Intel SGX SDK4构建了TSE原型，此外，实现了Bunker-B的原型作为比较的基准，因为其实现是不公开的，原型利用SGX SDK中的内置加密原语进行相关加密操作.它还使用SDK中的设置和API来创建、管理和访问为SGX设计的应用程序(enclave).实验环境部署在具备SGX功能的Intel i7 1.8 GHz和8 GB内存的主机.

图2 Bunker-B与TSE查询时间对比(删除25%的数据)

4.2 实验数据分析

插入和删除:首先，比较在Bunker-B和TSE方案下插入和删除的时间，如表1所示.测量在不同方案的加密数据库中添加关键字-数据对的运行时间.如表1所示，Bunker-B需要21 μs插入1对，当关键字-数据对的数量等于数据数量时，这比我们的方案(23 μs)要快.原因是上述3种方案的插入时间受到不受信任的应用程序和enclave之间的I/O(ecall/ocall)的限制.对于Bunker-B,I/O成本与关键字-数据对的数量成线性关系，而TSE的I/O成本与数据数量成线性关系.当插入1×106个数据时,我们的方案只需要7 μs来插入1对关键字-数据对,速度比Bunker-B (12 μs)快了近2倍.

表1 Bunker-B与TSE插入数据时间对比

对于删除，Bunker-B的性能与插入(12 μs)是一样的，因为删除运行相同的算法只是操作不同.对于我们的方案，删除过程只将数据id插入到列表中，并且在查询阶段通过排除已删除的id来执行删除操作.因此，我们的方案在删除阶段只需要4 μs就可以处理1个数据.

查询延迟：为了测量关键字频率和删除操作带来的查询延迟，我们选择在删除部分数据后查询前25个关键字，如图2所示，当插入2.5×105条数据、删除25%的数据后.对于最频繁的关键字，Bunker-B需要1.3 s的查询时间.虽然TSE执行第1次搜索需要5 s，但它也会在enclave中缓存已删除的关键字-数据对，并在第1次查询期间对数据执行删除.因此，接下来的查询速度要快得多，因为调用的次数大大减少.即使是第25个最常见的关键字，TSE(159 ms)仍然比Bunker-B(221 ms)快40%.

通信成本:接下来展示了I/O操作(ocall/ecall)对不同方案性能的影响.如表2所示，Bunker-B比本文方案多需要10倍的ecall/ ocall操作.因此，尽管Bunker-B和本文方案都在最后生成并存储加密的关键字-数据对，但是本文方案可以实现更好的插入性能，因为本文方案依赖较少的I/O操作.在删除操作上，Bunker-B比本文方案多了将近30倍的I/O操作(如表3所示).而且本文方案的删除操作只需要插入已删除的id，不涉及任何加密操作，而Bunker-B执行的过程和插入数据是一样的.这表明本文方案比Bunker-B通信成本更低.

表2 Bunker-B与TSE插入数据通信成本对比

表3 Bunker-B与TSE删除数据通信成本对比

内存消耗:因为与服务器和enclave相比，客户机的内存消耗可以忽略不计(即小于1 MB).如图3所示，TSE的加密数据库始终保持不变，因为它们在添加1×106条数据后保持相同的关键字-数据对.另一方面，当我们删除更多的数据时，Bunker-B的内存使用量会持续增加，因为它应该在服务器上维护已删除的关键字-数据对.在enclave中，Bunker-B不维护任何持久的数据结构，而TSE需要存储删除所需的信息.对于TSE，它会缓存enclave中的所有数据id，这将导致非常高的内存使用量，删除25%的数据时是304 MB.

图3 Bunker-B与TSE内存占用对比(删除25%的数据)

5 总 结

为了解决传统SE降低加密数据的查询效率，增加了客户端和服务器之间通信成本的问题，本文引入了硬件辅助解决方案——Intel SGX来解决这2个问题.本文通过分析当前解决方案，发现当前的解决方案存在密集ecall/ocall调用和搜索延迟的问题，提出利用Intel SGX的enclave来缓存关键字的状态，并且保留已删除数据的id的列表d，为后期的数据查询提供方便.本文的方案存在如下优点：

1) 由于在enclave中缓存了已删除数据的关键字-数据对，查询效率相较于Bunker-B更高；

2) 数据查询过程中依赖较少的I/O操作，因此通信开销更低.

虽然本文的方案在查询效率和通信开销方面有所优化，但是可以看到方案对enclave的内存占用还较高，这将触发enclave的自动分页机制，这个过程也会影响查询效率，同时本文方案在大数据量时的处理表现还不好.因此接下来的研究工作将着力于提高方案的批处理能力，减少enclave的内存占用，进一步提高数据查询效率.