一種改進(jìn)的云環(huán)境下排序的密文模糊關(guān)鍵字檢索方案

常雪琴

(亳州學(xué)院 電子與信息工程系，安徽 亳州 236800)

近年來云加密技術(shù)、模糊關(guān)鍵字檢索技術(shù)以及排序檢索技術(shù)都在蓬勃發(fā)展，但以目前的技術(shù)情況來說，這些技術(shù)的功能不僅較為單一，不能綜合處理復(fù)雜的問題，而且當(dāng)前比較流行的模糊關(guān)鍵字檢索因為索引的規(guī)模比較大，所需要的存儲空間較大，對檢索的效率具有較大的影響[1].因此，上述問題是當(dāng)前密文檢索算法迫切需要改進(jìn)的地方.

基于公鑰加密的密文檢索(PEKS)技術(shù)使用的是對稱加密方案，對于使用非對稱加密的數(shù)據(jù)文件，授權(quán)用戶使用自己的密鑰就可以進(jìn)行密文檢索[2].PEKS只能夠進(jìn)行比較查詢以及子集查詢，不支持連續(xù)查詢，而隱藏向量查詢(HVE)支持連續(xù)查詢，但并不能支持對密文的析取查詢[3].

最早的在云服務(wù)器環(huán)境下的隱私保護(hù)模糊關(guān)鍵字檢索算法對關(guān)鍵字之間的相似性是用編輯距離來測量的[4]，利用通配符構(gòu)建模糊關(guān)鍵字集合結(jié)構(gòu)(WFSC),即每一個關(guān)鍵字都會擁有一個模糊集合.后來的研究者基于上述的算法進(jìn)行了改進(jìn)，將模糊關(guān)鍵字結(jié)構(gòu)變?yōu)榛谧值浼囊环N模糊關(guān)鍵字結(jié)構(gòu)(DFSC)[5-6].該結(jié)構(gòu)減小了模糊集合的規(guī)模，提高了模糊檢索的效率.但是，這些模糊關(guān)鍵字檢索技術(shù)不支持多關(guān)鍵字檢索[7].雖然近年來在云數(shù)據(jù)上的隱私保護(hù)及加密檢索技術(shù)發(fā)展較為迅速[8]，但以研究的結(jié)果來看，這些技術(shù)僅支持單一的功能，不能進(jìn)行深度復(fù)雜的檢索，對在檢索中的問題或者可能出現(xiàn)的問題都沒有進(jìn)行妥善合理的處理[9-10].

本文在DESC和OPM算法的基礎(chǔ)之上，進(jìn)行索引結(jié)構(gòu)上的創(chuàng)新，提出一種新的索引結(jié)構(gòu)，以在用戶進(jìn)行檢索關(guān)鍵字輸入時可能出現(xiàn)的錯誤(拼寫錯誤、格式錯誤等)為例，進(jìn)行了模糊查詢處理，即在加密云數(shù)據(jù)的環(huán)境下，既能夠進(jìn)行模糊查詢，也能夠進(jìn)行排序檢索的綜合檢索方案——PFKS.本文算法與傳統(tǒng)算法相比可以減小計算的復(fù)雜度，且實現(xiàn)了多關(guān)鍵字檢索、模糊查詢以及檢索結(jié)果排序，極大地彌補(bǔ)了傳統(tǒng)算法的劣勢，提高了檢索效率，同時兼顧了安全性.

1 基本框架

在云環(huán)境下，模糊關(guān)鍵字檢索技術(shù)主要分以下兩個步驟：

1)Setup階段.數(shù)據(jù)的持有人使用KeyGen算法對系統(tǒng)中的參數(shù)進(jìn)行初始化，把數(shù)據(jù)集中關(guān)鍵字取出，再對這些關(guān)鍵字逐個計算出它們的模糊關(guān)鍵字合集，使用IndexBuilder處理數(shù)據(jù)文件得到一個能夠?qū)λM(jìn)行檢索的倒排索引.再將這些文件進(jìn)行加密處理，上傳外包到云服務(wù)器中去.在本階段，數(shù)據(jù)的持有者可以將一些密鑰發(fā)放給授權(quán)的客戶，發(fā)送密鑰時，可以使用現(xiàn)有的公鑰技術(shù)，也可以使用廣播技術(shù)來進(jìn)行操作.

2)Retrieval階段.在得到了授權(quán)用戶所輸入的關(guān)鍵字之后，計算出該關(guān)鍵字對應(yīng)的模糊關(guān)鍵字集合，然后利用TrapdoorGen算法生成暗門，再將這些信息提交到云服務(wù)器上.云服務(wù)器接收到該檢索請求后，調(diào)用Search算法在加密數(shù)據(jù)索引上進(jìn)行檢索操作，并返回用戶檢索結(jié)果信息，即匹配的加密文件ID和文件分?jǐn)?shù)，這個結(jié)果是按照順序返回的.在這樣的流程下，云服務(wù)器所獲得的信息只有加密文件的ID和加密分?jǐn)?shù)，除此之外無法得到其它的數(shù)據(jù)信息，保證了數(shù)據(jù)的安全性.

2 索引結(jié)構(gòu)

在進(jìn)行規(guī)模的數(shù)據(jù)檢索時，索引是一種高效的檢索處理方案，而倒排索引是在檢索技術(shù)中一種經(jīng)常使用的技術(shù)[11]，它的主要作用是將關(guān)鍵字與對應(yīng)的數(shù)據(jù)文件形成集映射，形成一種集映射的索引結(jié)構(gòu)，保存各個文件中所包含的詞匯，所以倒排索引也稱倒排表或反向索引，同時該索引支持全文本的搜索.為了使檢索的精確度最高并且所得結(jié)果能排序，本文使用了一些排序算法來計算文件對應(yīng)關(guān)鍵字的相關(guān)度，相關(guān)度用分?jǐn)?shù)來表示；在實現(xiàn)模糊檢索時，根據(jù)一些關(guān)鍵字之間的相似度標(biāo)準(zhǔn)來量化關(guān)鍵字之間的關(guān)系，幫助構(gòu)建出關(guān)鍵字的集合，本文在進(jìn)行關(guān)鍵字模糊集合構(gòu)建時，將以編輯距離為量化標(biāo)準(zhǔn).

本文的PFKS算法的倒排索引結(jié)構(gòu)見表1.在表1中，關(guān)鍵字集合將編輯距離d作為關(guān)鍵字wi倒排索引的量化標(biāo)準(zhǔn)，文件ID代表含有關(guān)鍵字的數(shù)據(jù)文件，相關(guān)分?jǐn)?shù)為用來進(jìn)行檢索結(jié)果排序相關(guān)度的分?jǐn)?shù)值.采用的倒排索引結(jié)構(gòu)能夠?qū)崿F(xiàn)可排序的、支持多關(guān)鍵字搜索及模糊查詢算法的目標(biāo).

表1 倒排索引示例(編輯距離d)

3 加密云環(huán)境下的隱私保護(hù)PFKS算法

基于上述的基本框架和索引的結(jié)構(gòu)，使用DFSC以及OPM加密算法來實現(xiàn)模糊檢索、多關(guān)鍵字查詢以及檢索結(jié)果排序.在加密云環(huán)境下，RDKS具體實現(xiàn)如下：

1)Setup階段

2)Retrieval階段

c)按照上一步得到的相關(guān)度分?jǐn)?shù)值OPMfz(wi)(SCij)將所得的文件進(jìn)行排序，然后發(fā)送給用戶.如果用戶定義了只需要k個相關(guān)文件，則只需發(fā)送給用戶前k個文件即可.

d)用戶可以利用密鑰z來解密服務(wù)器返回的文件，得到自己想要的排序檢索結(jié)果，即

Index(K',F)初始化:對所得的文件集進(jìn)行關(guān)鍵字提取,文件集定義為F={F1,F2,…,Fn},所得的關(guān)鍵字集合為:W={w1,w2,…,wm},在wi∈W(1≤i≤m)時,獲取含有關(guān)鍵字wi文件ID的集合F(wi).滿足wi∈W,當(dāng)構(gòu)建與該關(guān)鍵字相關(guān)的模糊關(guān)鍵詞集合SDwi,d滿足1≤j≤Ni時:算出文件Fj(含有關(guān)鍵字wi的第j個文件)的相關(guān)度分?jǐn)?shù)SCij,再利用算法OPMfz(wi)(SCij)計算出加密的分?jǐn)?shù),利用所得的分?jǐn)?shù)與該文件的ID一并形成索引Ij索引項:.對于每一個索引Ii'(1≤i≤m),使用密鑰加密所有的條目:,填充為0時表示有效的索引(1≤j≤Ni).隨后減去有效索引條目,剩下的就是v-Ni,使得索引長度保持一致.用πx(wi)來代替wi.得到索引I={I1,I2,…,Im}.

4 實驗性能分析

加密云數(shù)據(jù)隱私保護(hù)算法進(jìn)行實驗驗證，算法的實現(xiàn)由C++語言來完成，實驗的數(shù)據(jù)集來自于RFC網(wǎng)站，共10 182個數(shù)據(jù)文件.

4.1 索引構(gòu)造算法的實現(xiàn)與性能分析

圖1 PFKS算法與KFSC算法索引規(guī)模比較

在建立模糊關(guān)鍵字索引時，使用的是表1的索引結(jié)構(gòu).該索引結(jié)構(gòu)在編輯距離d相等時，使用DFSC算法生成的索引規(guī)模要比PFKS小得多.本文生成的數(shù)據(jù)集隨機(jī)選擇為2 000，4 000，6 000，8 000以及10 000個文件.本文的索引規(guī)模與主流的索引規(guī)模是非常接近的.模糊關(guān)鍵詞集合構(gòu)建時采用的隨機(jī)長度為5，6，7，10，11，12的關(guān)鍵詞共10個.圖1為PFSK算法和KFSC算法索引規(guī)模的比較，從圖1可以看出本文提出的算法和DFSC的方案所得關(guān)鍵字?jǐn)?shù)量是一樣的，圖中的兩個算法的模糊關(guān)鍵字集合的大小是相同的，平均模糊關(guān)鍵字的數(shù)量也是相同的.從表2中可以看出，數(shù)據(jù)集合文件數(shù)量為1 000和2 000時，本文所提出的方案為關(guān)鍵字建立索引所花費的時間與傳統(tǒng)的方法所花費的時間是非常接近的.同時，本文在已有的算法基礎(chǔ)上添加了排序功能，提高用戶的檢索體驗；實現(xiàn)了模糊關(guān)鍵字檢索，糾正用戶在進(jìn)行關(guān)鍵字鍵入時的拼寫或者格式上的錯誤，提高檢索的容錯.

綜上所述，本文的算法方案實現(xiàn)了關(guān)鍵字的糾錯和排序查找功能，系統(tǒng)的花費沒有因此增加，從而提升了系統(tǒng)的效率和可用性，同時也證明了一對多的保序映射技術(shù)憑借索引結(jié)構(gòu)優(yōu)化使得其安全性和效率性上比傳統(tǒng)的算法更好.

4.2 檢索算法的性能分析

檢索算法的效率體現(xiàn)在算法的計算時間和精度上，模糊關(guān)鍵字算法運算時間不僅包括索引中各個條目的匹配時間，也包含模糊關(guān)鍵字集合匹配的時間以及解密和排序的時間[12-14].因此top-k檢索是一種改進(jìn)的思路，就是返回給用戶想要的關(guān)鍵字分?jǐn)?shù)最高的k個文件.在本文提出的方案中，是可以得到和明文檢索一樣的k個文件.本文算法索引建立的時間相比之下是比較少.出現(xiàn)這種情況的主要原因是因為所采用的關(guān)鍵字相關(guān)度分?jǐn)?shù)排序加密算法、倒序索引等規(guī)模都較小.除此之外本文的算法還支持多關(guān)鍵字的檢索，所以，授權(quán)用戶在輸入了少量的錯誤關(guān)鍵詞時，利用模糊關(guān)鍵字查找出相近的關(guān)鍵字完成檢索的過程，對檢索的速度和準(zhǔn)確度都有不小的提升.

表2 不同數(shù)據(jù)文件集索引構(gòu)建花費時間(編輯距離d=2)

綜上，本文的算法在傳統(tǒng)的算法基礎(chǔ)之上做出改進(jìn)，在傳統(tǒng)算法基礎(chǔ)之上，縮小了索引的規(guī)模，并且允許用戶能進(jìn)行多關(guān)鍵字的檢索和排序檢索.本文算法在云服務(wù)器環(huán)境下的安全性上，在算法的精度上，特別是一對多保序映射算法的正確性上，具有較大的提升.實驗結(jié)果如圖2所示.

圖2 PFKS算法與DFSC方案模糊關(guān)鍵字?jǐn)?shù)目比較

5 結(jié)語

針對當(dāng)前流行的云服務(wù)器環(huán)境,提出基于隱私保護(hù)的PFKS算法;在傳統(tǒng)的DFSC算法和OPM密文檢索算法基礎(chǔ)之上增加多關(guān)鍵字檢索、模糊檢索以及排序檢索，并且改進(jìn)索引結(jié)構(gòu).對算法的安全性和效率進(jìn)行分析研究,結(jié)果證明本文算法在云服務(wù)器環(huán)境下的安全性上，在算法的精度上，特別是一對多保序映射算法的正確性上，具有較大的提升.因此，在云環(huán)境下，本文提出的模糊關(guān)鍵字檢索技術(shù)是可行的、有效的.

參考文獻(xiàn)：

[1] 閆明.一種新的云計算環(huán)境下數(shù)據(jù)安全保護(hù)算法研究[J].科技通報,2017,33(9):184-187.

[2] LIU C,ZHU L,LI L,et al.Full keyword search on encrypted cloud storage data with smallindex[J].IEEE,2011:269-273.

[3] LI X,LI J,HUANG F.A secure cloud storage system supporting privacy-preserving fuzzydeduplication[J].Soft Computing,2016,20(4):1437-1448.

[4] KHAN A N,KIAH M L M,ALI M,et al.BSS:block-based sharing scheme for secure data storage services in mobile cloudenvironment[J].Journal of Supercomputing,2014,70(2):946-976.

[5] 華鋼,王永星.基于信號衰減模型補(bǔ)償?shù)腞SS指紋定位算法[J].徐州工程學(xué)院學(xué)報(自然科學(xué)版),2015,121(4):28-32.

[6] CHAN P T,RAD A B,HO M L.A study on lateral control of autonomous vehicles via fired fuzzy rules chromosome encoding scheme[J].Journal of Intelligent & Robotic Systems,2009,56(4):441-467.

[7] WANG S,ZHAO D,ZHANG Y.Searchable attribute-based encryption scheme with attribute revocation in cloudstorage[J].Plos One,2017,12(8):e0183459.

[8] 張克軍,竇建君.基于Contourlet變換和不變矩的圖像檢索方法[J].徐州工程學(xué)院學(xué)報(自然科學(xué)版),2012,27(1):48-51.

[9] WANG Y,BAO W,ZHAO Y,et al.AnElGamal encryption with fuzzy keyword search on cloud environment[J].International Journal of Network Security,2016,18(3):481-486.

[10] LI W,WEN Q,LI X,et al.Attribute-based fuzzy identity access control inmulticloud computing environments[J].Soft Computing,2017(1):1-12.

[11] ARGONETO P,RENNA P.Supporting capacity sharing in the cloud manufacturing environment based on game theory and fuzzylogic[J].Enterprise Information Systems,2016,10(2):193-210.

[12] SHOJAFAR M,JAVANMARDI S,ABOLFAZLI S,et al.FUGE:A joint meta-heuristic approach to cloud job scheduling algorithm using fuzzy theory and a geneticmethod[J].Cluster Computing,2015,18(2):829-844.

[13] LIU C,ZHU L,LI L,et al.Full keyword search on encrypted cloud storage data with smallindex[J].IEEE,2011:269-273.

[14] SHEKOKAR N,SAMPAT K,CHANDAWALLA C,et al.Implementation of fuzzy keyword search over encrypted data in cloud computing[J].Procedia Computer Science,2015,45(2):499-505.