一种基于动态索引表的对称可搜索加密方案

张成， 褚莹， 凌力(复旦大学 通信科学与工程系， 上海 200433)

一种基于动态索引表的对称可搜索加密方案

张成， 褚莹， 凌力
(复旦大学 通信科学与工程系， 上海 200433)

可搜索加密机制在现阶段的云端存储服务中有着广泛的应用，可以在保护用户数据隐私的情况下快速查询指定的加密数据。基于对称密钥加密的可搜索加密方案SSE计算开销小，效率高，特别适合个人用户的大规模数据块加密。针对传统SSE方案中BuildIndex算法的不足，提出了改进的索引表模型设计。实验证明，该算法建立索引表的时间花销更小，同时保留了查询速度快的特点，改善了SSE方案的动态性。

可搜索加密； 动态索引表； 对称密钥加密； 云存储； 数据安全

0 引言

早在1996年左右，O. Goldreich和R. Ostrovsky 等人就首次提出过关于搜索加密数据的一些问题：加密云端数据可以让用户以最小的开销和较高的安全性来存储大量的数据。然而，任何人都无法对加密后的数据进行搜索，上传者本身也无法选择性地获取数据片段。要想使用数据必须从云端全部下载。这会带来两个问题：第一，大量文件的下载会占用大量网络带宽；第二，文件的完全解密费时费力，效率极低，浪费本地资源。

对于这个问题的思考引出了可搜索加密(searchable encryption，简称SE)技术的雏形，并在近几年蓬勃发展。这个概念在2000年被Song XD[1]等人提出，用户使用特殊加密方法生成一张关键字索引表，之后将加密数据c以及加密索引表γ上传到云端服务器。当用户需要查询某个关键字w时，使用密钥生成一个关键字搜索凭证τw(search token)，云端服务器用此搜索凭证在索引表中进行查找，如果匹配成功，就将这个关键字对应的所有文件发回给用户。云端服务器无法获得关键字内容以及文件的明文，保护了用户个人数据的隐私；而对于用户来说，使用可搜索加密方案大大节省了网络开销和存储空间，同时充分利用了云端服务器的强大计算能力，查询效率很高。

1 对称密钥可搜索加密(SSE)

SE技术根据加密方法可以分为对称密钥可搜索加密(SSE)和非对称密钥可搜索加密(ASE)。SSE机制通常使用伪随机函数或哈希表处理关键字索引表，相比ASE机制，SSE计算开销小，效率高，特别适合个人用户的大规模数据块加密。

在SSE方案中，用户可以自己组织数据的顺序，或者引入一些额外的数据结构以便于搜索，只有拥有密钥的用户才可以获取数据。在这种情况下，用户的初始工作会比较繁重，需要预处理很多数据，但是后续工作例如查询搜索就比较轻松，且搜索时间和数据大小关联很小，用户的查询习惯也很容易掩盖。

在Song XD的方案之后, 还有两种经典的SSE构造方案。Curtmola R等人[2]提出SSE-1方案，逐渐规范化了SSE安全方案，构建了健全的“关键字-文件”索引表，云服务器搜索时间复杂度仅为O(1)，但是更新索引表较慢，需要O(n)时间。Kamara等人[3]则在SSE-1方案的基础上提出了一个高效动态的方案，额外构建了“文件-关键字”索引表，改善了建立索引表的时间，同时保留了搜索时间开销小和安全性高的特点。

2 索引表建立算法

由于SSE-1作为对称密钥可搜索加密的基本方案已经非常成熟，因此近年来SSE的研究基本集中在对基本方案的功能拓展和安全性优化上。例如查询方式拓展、多关键词搜索、模糊关键词检索、安全性优化[4]、以及本文重点研究的密文文件及索引表的动态更新。

2.1 两种传统BuildIndex算法

Curtmola等人设计的SSE-1方案是当时最为完善的对称密钥可搜索加密方案，在搜索开销极小的情况下，还保证了很高的安全性，即使攻击者获取了过去的搜索凭证和搜索结果，也无法从中获取更多信息，做到了真正意义上的不泄露任何信息。基本算法包括密钥生成Keygen，索引表建立BuildIndex，搜索凭证生成Trapdoor和搜索Search。

为了支持高效的检索，SSE-1引入了两个重要的数据结构：第一个是数组，用于存储加密后的文件集合，第二个则是核心部分，一张存储了关键字相关信息的索引表，用于定位对应关键词的文件在数组中的位置。索引表建立BuildIndex方法如下：

(1)使用密钥生成算法生成全局密钥s,y,z，并设置全局计数器ctr=1。

(2)建立链表。以关键字W(i)作为链表核心，包含关键字W(i)的文件作为节点，将这些节点随机存储在数组A中。每一个节点都使用密钥生成算法生成节点密钥Ki,j。以 “文件标识符||下一个节点解密密钥||下一个节点在数组A的存放位置”这一形式创建链表LW(i)的第j个节点并存储至数组A中。Ψs(ctr)表示使用第一个对称密钥s加密计数器，这个密文用来表示节点在数组中的存放位置。最后使用前一个节点的密钥Ki,j-1加密节点Ni,j，存储在A[Ψs(ctr)]中，计数器加1，即

A[Ψs(ctr)] =HKi,j-1[id(Fi,j)||Ki,j,||Ψs(ctr+1)]

(3)建立搜索表时，需要对每一个关键字W(i)链表的头节点地址和头结点密钥打包进行加密，方法就是使用第二个对称密钥y加密W(i)，再将两者异或，接着使用第三个对称密钥z加密W(i)，将这个关键字密文和加密后的链表头节点做点对点映射，存放入数组中，即

T(πz(W(i)))= (addr(Ni,1)||Ki,0)⊕fy(W(i))

由于每个节点都存储了下一个节点的地址和密钥，因此可以遍历整个链表，获得所有包含关键字的文件标示符。

可以看到SSE-1避免了对密文逐个搜索，效率较高。但是对文件进行增删操作时需要重构索引表，查找增删链表内的元素会造成很大的开销，因此这个方案更加适用于稳定的文件集合。

在SSE-1的基础之上，Kamara等人提出了一个线性搜索时间的动态更新SSE方案。基本算法包括生成密钥Gen，建立索引并加密Enc，生成搜索凭证SrchToken，文件添加凭证AddToken，文件删除凭证DelToken，密文搜索Search，索引表内容添加Add，索引表内容删除Del，和密文解密Dec。该方案重新定义了SSE-1的搜索数组As和搜索表Ts，并且额外加入了删除数组Ad和删除搜索表Td，删除数组Ad内存储的是以文件为核心的删除链表，可以跟踪每个文件包含的关键字。搜索链表的格式为“关键字-文件”，而删除链表的格式为“文件-关键字”，节点格式呈对偶关系。因此删除搜索表不仅存储删除链表，也存储每个节点的对偶节点在搜索数组中的位置。[6]通过新算法AddToken和DelToken就可以实现索引表的动态更新，方法如下：

(1)搜索表和搜索数组的建立和SSE-1类似，不同点在于除了存储头节点地址，也存头节点的对偶节点的地址，即

As[Ψs(ctr)] =HKi,j-1[id(Fi,j)||Ki,j||Ψs(ctr+1)]

Ts(πz(W(i)))= (addrs(Ni,1)||

addrd(Ni,1*) )⊕fy(W(i))

(2)以文件集合中的每一个文件f为核心，建立一个删除链表，每一个节点Di都是搜索链表节点N的对偶节点。以 “下一个节点解密密钥||下一个节点在删除数组Ad的存放位置||对偶节点在搜索数组As存放位置||对偶节点的前后节点在搜索数组As的存放位置”这一形式创建删除链表并存储至数组Ad中，即

Di=Ki,j’||Ψs(ctr+1)||addrs(N)|

|addrs(N-1) ||addrs(N+1)

Ad[Ψs(ctr)] =HKi,j-1[Di]

(3)删除搜索表的构建与之前相同，即

Td(πz(F(i)))= (addrd(D1))⊕fy(F(i))

至此动态搜索表构建完成，若需要添加文件，找出此文件包含的关键字，通过关键字链表将新的“关键字-文件”组合加入到搜索数组中。需要删除文件时，通过密钥生成删除凭证定位需要删除的文件，利用删除链表找到该文件对应的所有关键字，并利用对偶节点找到搜索链表中需要删除的节点，无需重构链表。

2.2 改进的buildIndex算法

Kamara等人的设计拥有非常好的性能，搜索时间为O(#fw)，复杂度和所有包含关键字w的f数量成正比，而且改善了第一代SSE方案的动态性，文件变更时无须再重做索引表，只需要在之前的索引表上进行修改。然而，这个方案建立索引表需要大量的时间，时间复杂度为O(∑w#fw+#W)，所有链表的总长度为所有“关键字-文件”组合数，链表总数等于关键字的数量。随着文件和关键字总数的提升，“关键字-文件”组合会随之大量增加，建立索引表的时间也会成倍增加，影响效率。

改良后的索引表，如图1所示。

利用跳跃表的思路，将所有的链表汇总成一个多指针链表，在这张链表当中，以文件f作为节点，所有的关键字w作为指针。设置头节点head，包含所有关键字指针，以“下一个节点解密密钥||指针K1的前后节点在数组A中的存储位置||指针K2的前后节点在数组A中的存储位置||……||指针K#w的前后节点在数组A中的存储位置”的形式创建每一个节点。即

Ni=Ki||Ψs(ctr+1)||addrs(NK1-1) ||

addrs(NK1+1)||…||addrs(NK#W-1)||addrs(NK#W+1)

As[Ψs(ctr)] =HKi[Ni]

图1 动态索引素

由于所有链表结合为一个，因此索引表和搜索数组也可以合并，所有的搜索请求都送往头节点处理。即

As(0)= (addrs(N0))⊕fy(W(i))

搜索时只需要通过对称密钥y计算出fy(w(i))这个搜索凭证，就可以通过异或得到关键词对应的密文链表头节点的存储位置和节点的内容。另外，通过密钥s计算Ψs(ctr), 便可相继得到链表的其他节点。

其余基本算法与Kamara等人的方案相同。以图1为例，若对5个文件和5个关键字进行处理，存储时只需要存储头节点加上文件总数个节点，共6个节点。相比Kamara的方案的14个节点，本方案的节点数量大大减少，可以节省很多建立索引表和索引数组的开销。随着文件和关键字数量的上升，本方案在建立索引表和数组方面的性能会更加突出。添加文件时，只需整理出文件中包含的关键字，创建一个新的节点，将关键字对应的指针链接起来。删除文件时，由于每一个节点的关键字指针都记录了前后节点，且链表只有一个，因此拼接链表的效率也比Kamara的方案更高，删除文件的效率也更高。即使需要增删关键字，也可以直接在链表节点的数据结构中进行修改，无需重建索引表。

3 实验和结果分析

与之前的方案相比，本搜索表的搜索时间复杂度为O(#Fw)，搜索表建立时间为O(#F)，#Fw代表所有包含某关键字的文件数量总和，#F代表所有文件数量总和，充分改善了建立搜索表的时间，同时也没有损失安全性。

我们测试了此方案建立索引表以及搜索密文方面的性能。实验配置如下：intel core i7-4790 CPU，7.87G内存。软件环境为：WIN7操作系统以及Eclipse编程环境。我们选择纯文本文件作为测试对象，并选择其中出现频率最高的一些词语作为关键词。选取拥有四组数据进行测试，文件大小分别为160M、480M、1.6G和16G。比较结果如图2图3所示。

可以看到，搜索时间基本和传统方案相同，而索引表建立时间明显少于传统算法。对于传统SSE方案而言，索引表生成的时间与“关键字-文件”组合的数量成线性关系，大约在35微秒/组合左右。这个数字基本不随“关键字-文件”组合数量的上升而改变。而对于本文提出的新型模型，时间复杂度仅与文件总数有关，因此文件越大、数量越多，表现出的性能越好。

图2 两种算法的搜索时间对比图

图3 两种算法的索引表建立时间对比图

而对于SSE方案中的其他基本算法，执行时间与“关键字-文件”组合的数量无关，而且针对每个单元(关键字或文件)的平均花销也和关键字或文件总数无关，是一个很小的常量，如表1所示。

表1 各类基本操作单元时间花销

从表1中可以看出，搜索、文件删除凭证生成和添加文件这几个操作的效率很高，非常实用。

4 总结

由于云存储服务概念的普及，可搜索加密现已被广泛研究和使用。基于对称密钥的可搜索加密SSE机制计算开销小，效率高，特别适合个人用户的大规模数据块加密。SSE方案都应当满足搜索速度快，安全性高，动态性好的要求。

本文的工作中都满足了上述性质，另外，相比传统模型，我们改善了建立索引表的时间花销，提升了性能。实验证明我们的方案非常有效，动态性得到了改进。

[1] Song XD, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C]//Proc. of the IEEE Symp. on Security and Privacy. IEEE Press, 2000. 44-55.

[2] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions[C]//Proc. of the 13th ACM Conf. on Computer and Communications Security (CCS 2006). New York: ACM Press, 2006. 79-88.

[3] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption[C]//Proc. of the 19th ACM Conf. on Computer and Communications Security (CCS 2012). New York: ACM Press, 2012. 965-976.

[4] 李经纬,贾春福,刘哲理,等. 可搜索加密技术研究综述[J]. 软件学报, 2015, 26(1):109-128.

[5] 沈志荣, 薛巍, 舒继武. 可搜索加密机制研究与进展[J]. 软件学报, 2014, 25(4):880-895.

[6] Ren X, Yan S. Keyword-based Cipher-text Search Algorithm under Cloud Storage [J]. 2016, 61.

ASearchableSymmetricEncryptionSchemeBasedonDynamicIndex

Zhang Cheng, Chu Ying, Ling Li
(College of Information Science and Engineering, Fudan University, Shanghai 200433)

Searchable encryption has been widely applied in cloud storage service now, it can help the user to search over specified cipher-text rapidly without leaking users’ data privacy. Searchable symmetric encryption (searchable encryption based on symmetric key cryptography) has a low calculating overhead and is very suitable for large data block encryption by private user. Because the "Build Index" algorithm of traditional SSE is insufficient, a new index is proposed with an improved algorithm. Experiment results indicate that the overhead of building index becomes smaller and searching time is still satisfactory, and the dynamic performance has been improved.

Searchable encryption; Dynamic index; Symmetric key cryptography; Cloud storage; Data security

张 成(1993-)，男，上海，硕士研究生，研究方向：网络与数据通信。

褚 莹(1994-)，女，上海，硕士研究生，研究方向：网络与数据通信。

凌 力(1967-)，男，浙江，副教授，研究方向：网络与数据通信。

1007-757X(2017)11-0039-03

TP309

A

2017.07.05)