基于改进的PEKS方案的高效搜索加密算法

朱 林

(贵阳学院电子与通信工程学院， 贵州贵阳 550005)



基于改进的PEKS方案的高效搜索加密算法

朱 林

(贵阳学院电子与通信工程学院， 贵州贵阳 550005)

为了提高PEKS方案搜索加密算法的关键字索引搜索效率，提出基于Hash链表的关键字索引结构，以改进原始的单链表关键字索引结构，基于该结构，采用曲线拟合的方法构建Hash函数，将关键字映射到链表中。仿真实验结果表明，改进后的PEKS方案在大量关键字搜索的情况下，搜索效率得到了显著提升。

算法理论；PEKS方案；可搜索加密；关键字搜索；链表

PEKS(public key encryption with keyword search)方案是ACM在1999年实施的移动计算和交换项目中的移动计划[1-2]。计划中假设用户Bob发送携带一系列关键字的E-mail给用户Alice，前提是用户Alice所使用的E-mail服务器支持按邮件关键字进行终端分类投送，而用户Alice则根据不同的需要在不同的设备终端来及时阅读这些E-mail[3-5]。例如，如果E-mail服务器上的邮件包含了“及时处理”字样的关键字，那么E-mail服务器就会自动地将这封E-mail发送到Alice的手机端；如果邮件包含了“娱乐”字样的关键字，那么E-mail服务器会将该邮件投送到用户Alice的办公电脑上，等待用户闲暇时候查阅。具体的PEKS方案模型如图1所示[6-7]。

图1 PEKS方案模型Fig.1 PEKS scheme model

假设用户Bob向Alice发送一封带有关键字w1,w2,…,wk的加密E-mail，Alice的公钥是Apub，E-mail的内容主体是msg，则发送的消息可用式(1)表示：

[EApub[msg],PEKS(Apub,w1),…,

PEKS(Apub,wk)]。

(1)

这里的PEKS方案支持对消息中关键字的搜索，但是这个过程不能泄露E-mail内容中的任何信息，否则就会给邮件系统带来安全隐患[8]。

PEKS方案允许用户对邮件加密数据进行搜索，但是这个搜索是有特定条件的，而且是不能泄露任何邮件明文信息的。PEKS方案为了避免攻击者破译出加密信息和陷门的对应关系，设计了一个安全通道来传输从接受接收者发送到服务器的一个陷门，它的关键字管理、加密、解密、密钥管理机制等都相对比较简单，是个优秀的关键字搜索加密方案，但是也存在很多问题，例如关键字管理效率低，安全通道存在风险，搜索效率低等[9-10]。针对这些不足，国内外专家学者也提出了很多可行的研究方案。如文献[11]提出了云环境下对密文高效排序的查询方法；文献[12]提出一种使用关键字搜索的指定测试机公钥加密方法；文献[13]提出了一种基于连接关键词的可搜索加密方案等，这些方法都很好地优化了PEKS方案，但是对于研究关键字搜索效率低的问题比较少，还有更大的研究空间。

本文对PEKS方案的关键字搜索效率进行了优化。起初的PEKS方案采用了单链表索引结构来映射密文关键字，在关键字数量较少的时候关键字搜索效率没有问题，但密文有大量关键字的时候，关键字搜索效率就会大大降低，为此提出了基于曲线拟合的Hash链表结构来映射密文关键字。实验表明，改进后的PEKS方案的关键字搜索效率较之前得到了很大提升。

1 PEKS方案存在的问题

PEKS方案在设计之初因为应用的限制，并没有考虑一个文档含有大量关键字的情况。如上文提到邮件文件发送，邮件关键字wk只涉及到2个关键字。因涉及搜索的关键字很少，PEKS方案就采用线性链表的方式来搜索关键字，即：

PEKS(Apubw1)→PEKS(Apubw2)→…→

PEKS(Apubwk)。

对于要加密的文件，当只有少量关键字时，关键字的搜索效率没有受到太大影响。但是，如果所发密文包含大量关键字，这种线性链表索引结构就会影响关键字搜索的效率。在保证安全性的前提下，为了提高大量关键字搜索的效率，本文采用类Hash链表的形式来设计关键字索引。

2 PEKS方案的改进

2.1 关键字Hash索引结构的设计

针对上文分析的PEKS方案存在的问题，采用Hash链表的方法来构建关键字的搜索，如图2所示。这里可以将不同的关键字通过Hash函数来映射到同一个链表当中，每一个链表可认为是一个关键字分组。服务器在搜索密文关键字时，可以直接在对应的关键字链表中进行搜索，这样可大大减少搜索关键字的个数，以达到提高搜索效率的目的。

图2 Hash关键字索引结构Fig.2 Hash keyword index structure

2.2 Hash函数的构建

基于关键字Hash索引结构构建了一个Hash函数，来映射关键字到链表中，这里采用曲线拟合的方法来构建Hash函数。

式(2)给出了一个关键字到索引地址映射的数据集，设数据集中有m对映射，对于式(2)给出的数据集的近似拟合函数见式(1)，其中，n

{(xi,yi)|i=1,2,3,…,m} ，

(2)

y(x)=a0+a1x+…+anxn。

(3)

式(3)是一个近似函数，会有误差存在，所以根据最小二乘法，取{ak|k=1,2,3,…,n}为式(4)的极小集。其中F(a0,a1,…,an)为误差的平方和。

(4)

∂F(a0,a1,…,an)/∂aj=

(5)

用系数集{ak|k=1,2,3,…,n}来确定式(3)的函数，并对式(4)进行求导，得到式(5)，建立方程组，然后根据式(2)给出的映射数据集就可以解出系数集{ak|k=1,2,3,…,n}，有了系数就能确定具体的式(3)函数。在进行具体的关键字和地址映射时，式(2)则对应关键字序列，yi则是链表的地址，可以求出系数集{ak|k=1,2,3,…,n}，代入式(3)所确定的函数即为本文所构建的Hash函数。

3 改进后PEKS方案设计

1)生成密钥

客户端的密钥为xP和x；服务器端的密钥为yP和y。其中P是r阶循环加法群G1的生成元，x,y为2个随机整数。

2)加密关键字

对于关键字{wk|k=1,2,3,…,n}，它的加密密文如式(8)所示，其中h为随机整数。

(6)

Ui=h·Hash(wi)·P+h·x·P,

(1≤i≤m),

(7)

V=h·P,

(8)

S=[U1,U2,…,Um,V]。

(9)

式(6)是一个Hash函数，它将一个0和1的数串映射到一个q阶素数域上；式(7)是利用用户和服务器的公钥对关键字集进行PECK加密。

3)生成陷门

(10)

4)服务器检索

若服务器收到客户端的搜索请求，则判断式(11)是否成立，成立则检索成功，否则，则检索失败。

(11)

e:G1×G1→G2，

(12)

其中：G1为循环加法群；G2为循环乘法群。因方案有Diffie-Hellman问题，故使用G1和G22个群；式(12)表示双线性对。

4 结果仿真分析

4.1 理论算法实验

仿真采用Matlab7.1作为平台，建立一个基于PEKS方案的邮件收发模型。在这个模型上进行改进及仿真实验。首先用Matlab建立收发池，模拟邮件收发，并统一设定通信延迟0.2 s，然后，从互联网上随机选取300个关键字，及其对应的含文字、图片、视频等内容的文件，这些文件就是要收发的邮件，最后用链表实现图2所示的Hash关键字索引结构，及构建2.2 中的Hash函数，实现对关键字的搜索。实验中对优化前和优化后PEKS方案的索引构建时间和关键字搜索耗时进行对比，所有实验结果取100次的实验平均值。实验结果如图3和图4所示[14-15]。

图3 优化前后索引构建时间对比Fig.3 Comparison of the index before and after optimization

图4 优化前后关键字搜索耗时对比Fig.4 Comparison of the keyword search time before and after optimization

图3为优化前后索引构建时间对比曲线图，为了对比方便，将耗时进行归一化处理。从图3中可以看出，随着关键字个数的增加，索引构建时间也随之增加，但优化后的PEKS方案耗时要比优化前的方案低，索引构建效率得到了提升。

图4为优化前后关键字搜索耗时对比曲线图，将耗时进行归一化处理。从图4中可以看出，随着关键字个数的增加，搜索时间也随之增加，但优化后的方案搜索耗时大大降低，搜索效率得到了很大提升。

4.2 应用测试

4.2.1 实验条件

1)硬件配置

CPU：Intel酷睿i7-4500U；内存：8 GB； 硬盘：500 GB。

2)软件配置

Windows8(64位)：操作系统；Postfix：作为发送邮件服务器；Dovecot：作为接收邮件服务器；mysql：作为数据库；SPF：反垃圾验证。

4.2.2 实验结果

在Postfix和Dovecot中增加关键字链表，这里实验邮件数据仍采用4.1中随机获取的300个关键字及文件。实验结果的时间取100次邮件收发的平均值。然后与文献[16]中的实验结果进行对比，如图5所示。从对比结果可以看出，本文优化的PEKS算法以及邮件系统收发耗时都要比文献[16]中的耗时低，起到了优化效果。

图5 与文献[16]性能对比Fig.5 Performance comparison with literature 16

5 结 论

对PEKS方案中的关键字索引结构搜索效率低的问题进行了改进，设计了基于Hash链表的关键字索引结构，采用曲线拟合的方法构建Hash函数。该方法构建的Hash函数均匀性比较好，哈希搜索的效率比较高。仿真实验结果证明，在关键字索引方面，改进后的PEKS方案的搜索效率得到了显著提升。

[1] 李经纬,贾春福,刘哲理,等.可搜索加密技术研究综述[J].软件学报, 2015,26(1):109-128. LI Jingwei,JIA Chunfu,LIU Zheli,et al. Survey on the searchable encryption[J]. Journal of Software, 2015,26(1):109-128.

[2] LI Ruixuan,XU Zhiyong,KANG Wanshang, et al. Efficient multi-keyword ranked query over encrypted data in cloud computing[J]. Future Generation Computer Systems, 2014,30(1):179-190.

[3] YU Jiadi, LU Peng,ZHU Yanmin, et al. Toward secure multikeyword top-kretrieval over encrypted cloud data[J]. IEEE Transactions on Dependable and Secure Computing,2013,10(4):239-250.

[4] 沈志荣,薛巍,舒继武.可搜索加密机制研究与进展[J].软件学报, 2014,25(4):880-895. SHEN Zhirong,XUE Wei,SHU Jiwu. Survey on the research and development of searchable encryption schemes[J]. Journal of Software,2014,25(4):880-895.

[5] 锡晓峰,曹宝香.一种适用于云计算环境的改进全同态加密方案[J].计算机技术与发展,2015,25(2):144-147. XI Xiaofeng,CAO Baoxiang. An improved fully homomorphic encryption scheme under conditions of cloud computing[J]. Computer Technology and Development， 2015,25(2):144-147.

[6] DONG Changyu,RUSSELLO G,DULAY N. Shared and searchable encrypted data for untrusted servers[J]. Journal of Computer Security,2011,19(3):367-397.

[7] CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[J]. Journal of Computer Security,2011,19(5):895-934.

[8] WEN Mi, LU Rongxing, LEI Jingsheng, et al. SESA: An efficient searchable encryption scheme for auction in emerging smart grid marketing[J]. Security and Communication Networks, 2014,7(1):234-244.

[9] FANG Liming,SUSILO W,GE Chunpeng,et al. Chosen-ciphertext secure anonymous conditional proxy re-encryption with keyword search[J].Theoretical Computer Science, 2012,462:39-58.

[10]MTONGA K, PAUL A, RHO S. Time-and-ID-based proxy reencryption scheme[J]. Journal of Applied Mathematics, 2014(1):1-7.

[11]程芳权,彭智勇,宋伟,等.云环境下一种隐私保护的高效密文排序查询方法[J].计算机学报，2012，35(11):2215-2227. CHENG Fangquan,PENG Zhiyong,SONG Wei,et al. An efficient privacy-preserving rank query over encrypted data in cloud computing[J]. Chinese Journal of Computers, 2012,35(11):2215-2227.

[12]RHEE H S,PARK J H,LEE D H.Generic construction of designated tester public-key encryption with keyword search[J]. Information Sciences, 2012,205:93-109.

[13]王尚平,刘利军,张亚玲. 一个高效的基于连接关键词的可搜索加密方案[J]. 电子与信息学报,2013,35(9):2266-2271. WANG Shangping,LIU Lijun, ZHANG Yaling. An efficient conjunctive keyword searchable encryption scheme[J]. Journal of Electronics & Information Technology, 2013,35(9):2266-2271.

[14]周其林,雷菊阳,王昱栋,等.一种引入参数无需确定聚类数的聚类算法[J]. 河北工业科技, 2015,32(2):123-128. ZHOU Qilin,LEI Juyang,WANG Yudong,et al. A clustering algorithm with parameters that no need to determine the clustering number[J]. Hebei Journal of Industrial Science and Technology, 2015,32(2):123-128.

[15]李艳，张自立，吕建红.一种基于CMAC神经网络的板形模式识别新方法[J]. 河北工业科技, 2014,31(3):209-214. LI Yan,ZHANG Zili,LYU Jianhong. A new method for flatness pattern recognition based on CMAC network[J]. Hebei Journal of Industrial Science and Technology, 2014,31(3):209-214.

[16]贾王晶. 基于带关键字搜索的公钥加密体制的构造及应用[D].太原:山西大学,2015. JIA Wangjing.The Construction and Application of Efficient Public Key Encryption with Keyword Search[D].Taiyuan: Shanxi University,2015.

Efficient search and encryption algorithm based on improved PEKS scheme

ZHU Lin

(School of Electronic and Communication Engineering, Guiyang University, Guiyang, Guizhou 550005, China)

In order to improve the efficiency of keyword indexing search of PEKS scheme searchable encryption algorithm, A keyword index structure based on Hash chain is proposed, to improve the original single table key index structure, and based on this structure, using curve fitting method to construct hash function, to map a key to the list. Finally, the simulation results show that the improved PEKS scheme in the case of a large number of keyword search, the search efficiency has been greatly improved.

theory of algorithms；PEKS scheme; searchable encryption; keyword search; linked list

1008-1534(2016)06-0470-04

2016-06-28;

2016-09-14；责任编辑：陈书欣

贵阳市工业振兴科技计划项目([2011101]1-16号)

朱 林(1980—)，男，江苏扬州人，副教授，博士，主要从事并行计算与分布式方面的研究。

E-mail: xxz55881@126.com

TN918.1；

A

10.7535/hbgykj.2016yx06005

朱 林.基于改进的PEKS方案的高效搜索加密算法[J].河北工业科技,2016,33(6):470-473. ZHU Lin.Efficient search and encryption algorithm based on improved PEKS scheme[J].Hebei Journal of Industrial Science and Techno-logy,2016,33(6):470-473.