基于改進的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.