基于改進(jìn)的PEKS方案的高效搜索加密算法

朱 林

(貴陽學(xué)院電子與通信工程學(xué)院， 貴州貴陽 550005)

?

基于改進(jìn)的PEKS方案的高效搜索加密算法

朱 林

(貴陽學(xué)院電子與通信工程學(xué)院， 貴州貴陽 550005)

為了提高PEKS方案搜索加密算法的關(guān)鍵字索引搜索效率，提出基于Hash鏈表的關(guān)鍵字索引結(jié)構(gòu)，以改進(jìn)原始的單鏈表關(guān)鍵字索引結(jié)構(gòu)，基于該結(jié)構(gòu)，采用曲線擬合的方法構(gòu)建Hash函數(shù)，將關(guān)鍵字映射到鏈表中。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的PEKS方案在大量關(guān)鍵字搜索的情況下，搜索效率得到了顯著提升。

算法理論；PEKS方案；可搜索加密；關(guān)鍵字搜索；鏈表

PEKS(public key encryption with keyword search)方案是ACM在1999年實(shí)施的移動計算和交換項(xiàng)目中的移動計劃[1-2]。計劃中假設(shè)用戶Bob發(fā)送攜帶一系列關(guān)鍵字的E-mail給用戶Alice，前提是用戶Alice所使用的E-mail服務(wù)器支持按郵件關(guān)鍵字進(jìn)行終端分類投送，而用戶Alice則根據(jù)不同的需要在不同的設(shè)備終端來及時閱讀這些E-mail[3-5]。例如，如果E-mail服務(wù)器上的郵件包含了“及時處理”字樣的關(guān)鍵字，那么E-mail服務(wù)器就會自動地將這封E-mail發(fā)送到Alice的手機(jī)端；如果郵件包含了“娛樂”字樣的關(guān)鍵字，那么E-mail服務(wù)器會將該郵件投送到用戶Alice的辦公電腦上，等待用戶閑暇時候查閱。具體的PEKS方案模型如圖1所示[6-7]。

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

假設(shè)用戶Bob向Alice發(fā)送一封帶有關(guān)鍵字w1,w2,…,wk的加密E-mail，Alice的公鑰是Apub，E-mail的內(nèi)容主體是msg，則發(fā)送的消息可用式(1)表示：

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

PEKS(Apub,wk)]。

(1)

這里的PEKS方案支持對消息中關(guān)鍵字的搜索，但是這個過程不能泄露E-mail內(nèi)容中的任何信息，否則就會給郵件系統(tǒng)帶來安全隱患[8]。

PEKS方案允許用戶對郵件加密數(shù)據(jù)進(jìn)行搜索，但是這個搜索是有特定條件的，而且是不能泄露任何郵件明文信息的。PEKS方案為了避免攻擊者破譯出加密信息和陷門的對應(yīng)關(guān)系，設(shè)計了一個安全通道來傳輸從接受接收者發(fā)送到服務(wù)器的一個陷門，它的關(guān)鍵字管理、加密、解密、密鑰管理機(jī)制等都相對比較簡單，是個優(yōu)秀的關(guān)鍵字搜索加密方案，但是也存在很多問題，例如關(guān)鍵字管理效率低，安全通道存在風(fēng)險，搜索效率低等[9-10]。針對這些不足，國內(nèi)外專家學(xué)者也提出了很多可行的研究方案。如文獻(xiàn)[11]提出了云環(huán)境下對密文高效排序的查詢方法；文獻(xiàn)[12]提出一種使用關(guān)鍵字搜索的指定測試機(jī)公鑰加密方法；文獻(xiàn)[13]提出了一種基于連接關(guān)鍵詞的可搜索加密方案等，這些方法都很好地優(yōu)化了PEKS方案，但是對于研究關(guān)鍵字搜索效率低的問題比較少，還有更大的研究空間。

本文對PEKS方案的關(guān)鍵字搜索效率進(jìn)行了優(yōu)化。起初的PEKS方案采用了單鏈表索引結(jié)構(gòu)來映射密文關(guān)鍵字，在關(guān)鍵字?jǐn)?shù)量較少的時候關(guān)鍵字搜索效率沒有問題，但密文有大量關(guān)鍵字的時候，關(guān)鍵字搜索效率就會大大降低，為此提出了基于曲線擬合的Hash鏈表結(jié)構(gòu)來映射密文關(guān)鍵字。實(shí)驗(yàn)表明，改進(jìn)后的PEKS方案的關(guān)鍵字搜索效率較之前得到了很大提升。

1 PEKS方案存在的問題

PEKS方案在設(shè)計之初因?yàn)閼?yīng)用的限制，并沒有考慮一個文檔含有大量關(guān)鍵字的情況。如上文提到郵件文件發(fā)送，郵件關(guān)鍵字wk只涉及到2個關(guān)鍵字。因涉及搜索的關(guān)鍵字很少，PEKS方案就采用線性鏈表的方式來搜索關(guān)鍵字，即：

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

PEKS(Apubwk)。

對于要加密的文件，當(dāng)只有少量關(guān)鍵字時，關(guān)鍵字的搜索效率沒有受到太大影響。但是，如果所發(fā)密文包含大量關(guān)鍵字，這種線性鏈表索引結(jié)構(gòu)就會影響關(guān)鍵字搜索的效率。在保證安全性的前提下，為了提高大量關(guān)鍵字搜索的效率，本文采用類Hash鏈表的形式來設(shè)計關(guān)鍵字索引。

2 PEKS方案的改進(jìn)

2.1 關(guān)鍵字Hash索引結(jié)構(gòu)的設(shè)計

針對上文分析的PEKS方案存在的問題，采用Hash鏈表的方法來構(gòu)建關(guān)鍵字的搜索，如圖2所示。這里可以將不同的關(guān)鍵字通過Hash函數(shù)來映射到同一個鏈表當(dāng)中，每一個鏈表可認(rèn)為是一個關(guān)鍵字分組。服務(wù)器在搜索密文關(guān)鍵字時，可以直接在對應(yīng)的關(guān)鍵字鏈表中進(jìn)行搜索，這樣可大大減少搜索關(guān)鍵字的個數(shù)，以達(dá)到提高搜索效率的目的。

圖2 Hash關(guān)鍵字索引結(jié)構(gòu)Fig.2 Hash keyword index structure

2.2 Hash函數(shù)的構(gòu)建

基于關(guān)鍵字Hash索引結(jié)構(gòu)構(gòu)建了一個Hash函數(shù)，來映射關(guān)鍵字到鏈表中，這里采用曲線擬合的方法來構(gòu)建Hash函數(shù)。

式(2)給出了一個關(guān)鍵字到索引地址映射的數(shù)據(jù)集，設(shè)數(shù)據(jù)集中有m對映射，對于式(2)給出的數(shù)據(jù)集的近似擬合函數(shù)見式(1)，其中，n

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

(2)

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

(3)

式(3)是一個近似函數(shù)，會有誤差存在，所以根據(jù)最小二乘法，取{ak|k=1,2,3,…,n}為式(4)的極小集。其中F(a0,a1,…,an)為誤差的平方和。

(4)

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

(5)

用系數(shù)集{ak|k=1,2,3,…,n}來確定式(3)的函數(shù)，并對式(4)進(jìn)行求導(dǎo)，得到式(5)，建立方程組，然后根據(jù)式(2)給出的映射數(shù)據(jù)集就可以解出系數(shù)集{ak|k=1,2,3,…,n}，有了系數(shù)就能確定具體的式(3)函數(shù)。在進(jìn)行具體的關(guān)鍵字和地址映射時，式(2)則對應(yīng)關(guān)鍵字序列，yi則是鏈表的地址，可以求出系數(shù)集{ak|k=1,2,3,…,n}，代入式(3)所確定的函數(shù)即為本文所構(gòu)建的Hash函數(shù)。

3 改進(jìn)后PEKS方案設(shè)計

1)生成密鑰

客戶端的密鑰為xP和x；服務(wù)器端的密鑰為yP和y。其中P是r階循環(huán)加法群G1的生成元，x,y為2個隨機(jī)整數(shù)。

2)加密關(guān)鍵字

對于關(guān)鍵字{wk|k=1,2,3,…,n}，它的加密密文如式(8)所示，其中h為隨機(jī)整數(shù)。

(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函數(shù)，它將一個0和1的數(shù)串映射到一個q階素數(shù)域上；式(7)是利用用戶和服務(wù)器的公鑰對關(guān)鍵字集進(jìn)行PECK加密。

3)生成陷門

(10)

4)服務(wù)器檢索

若服務(wù)器收到客戶端的搜索請求，則判斷式(11)是否成立，成立則檢索成功，否則，則檢索失敗。

(11)

e:G1×G1→G2，

(12)

其中：G1為循環(huán)加法群；G2為循環(huán)乘法群。因方案有Diffie-Hellman問題，故使用G1和G22個群；式(12)表示雙線性對。

4 結(jié)果仿真分析

4.1 理論算法實(shí)驗(yàn)

仿真采用Matlab7.1作為平臺，建立一個基于PEKS方案的郵件收發(fā)模型。在這個模型上進(jìn)行改進(jìn)及仿真實(shí)驗(yàn)。首先用Matlab建立收發(fā)池，模擬郵件收發(fā)，并統(tǒng)一設(shè)定通信延遲0.2 s，然后，從互聯(lián)網(wǎng)上隨機(jī)選取300個關(guān)鍵字，及其對應(yīng)的含文字、圖片、視頻等內(nèi)容的文件，這些文件就是要收發(fā)的郵件，最后用鏈表實(shí)現(xiàn)圖2所示的Hash關(guān)鍵字索引結(jié)構(gòu)，及構(gòu)建2.2 中的Hash函數(shù)，實(shí)現(xiàn)對關(guān)鍵字的搜索。實(shí)驗(yàn)中對優(yōu)化前和優(yōu)化后PEKS方案的索引構(gòu)建時間和關(guān)鍵字搜索耗時進(jìn)行對比，所有實(shí)驗(yàn)結(jié)果取100次的實(shí)驗(yàn)平均值。實(shí)驗(yàn)結(jié)果如圖3和圖4所示[14-15]。

圖3 優(yōu)化前后索引構(gòu)建時間對比Fig.3 Comparison of the index before and after optimization

圖4 優(yōu)化前后關(guān)鍵字搜索耗時對比Fig.4 Comparison of the keyword search time before and after optimization

圖3為優(yōu)化前后索引構(gòu)建時間對比曲線圖，為了對比方便，將耗時進(jìn)行歸一化處理。從圖3中可以看出，隨著關(guān)鍵字個數(shù)的增加，索引構(gòu)建時間也隨之增加，但優(yōu)化后的PEKS方案耗時要比優(yōu)化前的方案低，索引構(gòu)建效率得到了提升。

圖4為優(yōu)化前后關(guān)鍵字搜索耗時對比曲線圖，將耗時進(jìn)行歸一化處理。從圖4中可以看出，隨著關(guān)鍵字個數(shù)的增加，搜索時間也隨之增加，但優(yōu)化后的方案搜索耗時大大降低，搜索效率得到了很大提升。

4.2 應(yīng)用測試

4.2.1 實(shí)驗(yàn)條件

1)硬件配置

CPU：Intel酷睿i7-4500U；內(nèi)存：8 GB； 硬盤：500 GB。

2)軟件配置

Windows8(64位)：操作系統(tǒng)；Postfix：作為發(fā)送郵件服務(wù)器；Dovecot：作為接收郵件服務(wù)器；mysql：作為數(shù)據(jù)庫；SPF：反垃圾驗(yàn)證。

4.2.2 實(shí)驗(yàn)結(jié)果

在Postfix和Dovecot中增加關(guān)鍵字鏈表，這里實(shí)驗(yàn)郵件數(shù)據(jù)仍采用4.1中隨機(jī)獲取的300個關(guān)鍵字及文件。實(shí)驗(yàn)結(jié)果的時間取100次郵件收發(fā)的平均值。然后與文獻(xiàn)[16]中的實(shí)驗(yàn)結(jié)果進(jìn)行對比，如圖5所示。從對比結(jié)果可以看出，本文優(yōu)化的PEKS算法以及郵件系統(tǒng)收發(fā)耗時都要比文獻(xiàn)[16]中的耗時低，起到了優(yōu)化效果。

圖5 與文獻(xiàn)[16]性能對比Fig.5 Performance comparison with literature 16

5 結(jié) 論

對PEKS方案中的關(guān)鍵字索引結(jié)構(gòu)搜索效率低的問題進(jìn)行了改進(jìn)，設(shè)計了基于Hash鏈表的關(guān)鍵字索引結(jié)構(gòu)，采用曲線擬合的方法構(gòu)建Hash函數(shù)。該方法構(gòu)建的Hash函數(shù)均勻性比較好，哈希搜索的效率比較高。仿真實(shí)驗(yàn)結(jié)果證明，在關(guān)鍵字索引方面，改進(jìn)后的PEKS方案的搜索效率得到了顯著提升。

[1] 李經(jīng)緯,賈春福,劉哲理,等.可搜索加密技術(shù)研究綜述[J].軟件學(xué)報, 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ī)制研究與進(jìn)展[J].軟件學(xué)報, 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] 錫曉峰,曹寶香.一種適用于云計算環(huán)境的改進(jìn)全同態(tài)加密方案[J].計算機(jī)技術(shù)與發(fā)展,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]程芳權(quán),彭智勇,宋偉,等.云環(huán)境下一種隱私保護(hù)的高效密文排序查詢方法[J].計算機(jī)學(xué)報，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]王尚平,劉利軍,張亞玲. 一個高效的基于連接關(guān)鍵詞的可搜索加密方案[J]. 電子與信息學(xué)報,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]周其林,雷菊陽,王昱棟,等.一種引入?yún)?shù)無需確定聚類數(shù)的聚類算法[J]. 河北工業(yè)科技, 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īng)網(wǎng)絡(luò)的板形模式識別新方法[J]. 河北工業(yè)科技, 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]賈王晶. 基于帶關(guān)鍵字搜索的公鑰加密體制的構(gòu)造及應(yīng)用[D].太原:山西大學(xué),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；責(zé)任編輯：陳書欣

貴陽市工業(yè)振興科技計劃項(xiàng)目([2011101]1-16號)

朱 林(1980—)，男，江蘇揚(yáng)州人，副教授，博士，主要從事并行計算與分布式方面的研究。

E-mail: xxz55881@126.com

TN918.1；

A

10.7535/hbgykj.2016yx06005

朱 林.基于改進(jìn)的PEKS方案的高效搜索加密算法[J].河北工業(yè)科技,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.