李珍 姚寒冰 穆逸誠(chéng)

摘 要：針對(duì)密文檢索中存在的計(jì)算量大、檢索效率不高的問(wèn)題，提出一種基于Simhash的安全密文排序檢索方案。該方案基于Simhash的降維思想構(gòu)建安全多關(guān)鍵詞密文排序檢索索引（SMRI），將文檔處理成指紋和向量，利用分段指紋和加密向量構(gòu)建B+樹(shù)，并采用“過(guò)濾精化”策略進(jìn)行檢索和排序，首先通過(guò)分段指紋的匹配進(jìn)行快速檢索，得到候選結(jié)果集;然后通過(guò)計(jì)算候選結(jié)果集與查詢陷門的漢明距離和向量?jī)?nèi)積進(jìn)行排序，帶密鑰的Simhash算法和安全k近鄰（SkNN）算法保證了檢索過(guò)程的安全性。實(shí)驗(yàn)結(jié)果表明，與基于向量空間模型（VSM）的方案相比，基于SMRI的排序檢索方案計(jì)算量小，能節(jié)約時(shí)間和空間成本，檢索效率高，適用于海量加密數(shù)據(jù)的快速安全檢索。

關(guān)鍵詞：密文檢索;排序檢索;Simhash;隱私保護(hù);安全k近鄰

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

Secure ranked search scheme based on Simhash over encrypted data

LI Zhen1，2*， YAO Hanbing1，2， MU Yicheng1

1.College of Computer Science and Technology， Wuhan University of Technology， Wuhan Hubei 430063， China;

2.Hubei Key Laboratory of Transportation Internet of Things （Wuhan University of Technology）， Wuhan Hubei 430070， China

Abstract：

Concerning the large computation and low search efficiency in ciphertext retrieval， a secure ranked search scheme based on Simhash was proposed. In this scheme， a Secure Multi-keyword Ranked search Index （SMRI） was constructed based on the dimensionality reduction idea of Simhash， the documents were processed into fingerprints and vectors， the B+ tree was built with the segmented fingerprints and encrypted vectors and the “filter-refine” strategy was adopted to searching and sorting. Firstly， the candidate result set was obtained by matching the segmented fingerprints to perform the quick retrieval， then the top-k results were ranked by calculating the Hamming distance and the vector inner product between candidate result set and query trapdoor， and the Simhash algorithm with secret key and the Secure k-Nearest Neighbors （SkNN） algorithm ensured the security of the retrieval process. Simulation results show that compared with the method based on Vector Space Model （VSM）， the SMRI-based ranked search scheme has lower computational complexity， saves time and space cost， and has higher search efficiency. It is suitable for fast and secure retrieval of massive ciphertext data.

Key words：

ciphertext retrieval; ranked search; Simhash; privacy-preserving; Secure k-Nearest Neighbors （SkNN）

0 引言

隨著云存儲(chǔ)的發(fā)展，越來(lái)越多的企業(yè)和個(gè)人將數(shù)據(jù)存儲(chǔ)到云服務(wù)器。云服務(wù)器不是完全可信的，為保護(hù)敏感數(shù)據(jù)，用戶常將數(shù)據(jù)加密后存儲(chǔ)至云服務(wù)器，加密后的數(shù)據(jù)失去了明文特征，用戶無(wú)法高效地進(jìn)行檢索。對(duì)海量加密數(shù)據(jù)進(jìn)行高效檢索并保障數(shù)據(jù)的隱私成為一個(gè)亟待解決的問(wèn)題[1]。

Song等[2]提出了對(duì)稱可搜索加密方案，為解決密文檢索的問(wèn)題提供了思路，引起了學(xué)術(shù)界的普遍關(guān)注。Goh等[3]將關(guān)鍵詞信息映射在布隆過(guò)濾器中，通過(guò)布隆過(guò)濾器判斷關(guān)鍵詞的有無(wú)，實(shí)現(xiàn)密文快速檢索。Kuzu[4]、Krishna等[5]基于倒排索引，提出了根據(jù)關(guān)鍵詞相關(guān)分進(jìn)行排序的密文檢索方案，這些方案只適用于單關(guān)鍵詞搜索。Wang等[6]將改進(jìn)的計(jì)數(shù)布隆過(guò)濾器直接作為向量計(jì)算內(nèi)積進(jìn)行排序，但是該方案沒(méi)有構(gòu)建搜索索引，不適用于海量密文檢索。Yao等[7]、Li等[8]基于布隆過(guò)濾器，改進(jìn)了傳統(tǒng)的倒排索引結(jié)構(gòu)，結(jié)合“TF×IDF（Term Frequency-Inverse Document Frequency）”規(guī)則進(jìn)行相關(guān)分排序，這些方案都需要授權(quán)用戶在客戶端對(duì)結(jié)果倒排表進(jìn)行解密和排序，再向服務(wù)器發(fā)送請(qǐng)求才能得到top-k密文文檔，增加了網(wǎng)絡(luò)通信量和計(jì)算量。

Cao等[9]提出了MRSE多關(guān)鍵詞密文排序檢索方案，基于向量空間模型（Vector Space Model， VSM）將每篇文檔處理成空間向量，通過(guò)計(jì)算向量夾角余弦值可以直接在云端完成排序操作，但是該方案沒(méi)有保證關(guān)鍵詞的隱私安全。后來(lái)許多研究學(xué)者，如Li等[10]采用安全k近鄰（Secure k-Nearest Neighbors， SkNN）[11]算法加密向量，將向量與“TF×IDF”規(guī)則結(jié)合，既保證了安全性，又提高了排序精度。Xia等[12]、Zhu等[13]根據(jù)加密向量構(gòu)建了平衡二叉樹(shù)，Chen等[14]、楊宏宇等[15]基于MRSE框架，采用動(dòng)態(tài)K-means聚類算法構(gòu)建了層次索引樹(shù)。這些方案都是基于VSM，通過(guò)計(jì)算高維特征向量的內(nèi)積進(jìn)行檢索和排序，時(shí)間復(fù)雜度高，計(jì)算量大。

Simhash算法由Charikar[16]提出，Manku等[17]將該技術(shù)運(yùn)用于海量網(wǎng)頁(yè)的去重。楊旸等[18]基于Simhash的思想，利用n-gram分詞技術(shù)將單個(gè)詞處理成哈希指紋，構(gòu)建指紋索引樹(shù)，該方案只適用于單關(guān)鍵詞，無(wú)法進(jìn)行多關(guān)鍵詞的相關(guān)分排序。

針對(duì)密文多關(guān)鍵詞檢索存在的計(jì)算量大、檢索效率不高的問(wèn)題，本文提出了一種基于Simhash的安全密文排序檢索方案。采用AES算法加密文檔，通過(guò)帶密鑰的Simhash函數(shù)Sim（hk，·） 將文檔處理成Simhash指紋。基于SkNN算法生成加密向量，將分段指紋與加密向量構(gòu)成的二元組作為葉子節(jié)點(diǎn)構(gòu)建多關(guān)鍵詞密文排序檢索索引（Simhash-based Secure Multi-keyword Ranked search Index， SMRI）。根據(jù)用戶的檢索關(guān)鍵詞生成查詢陷門，通過(guò)分段指紋的匹配進(jìn)行快速檢索，得到候選結(jié)果集，通過(guò)計(jì)算查詢指紋與候選集中指紋的漢明距離，以及查詢向量與候選集中向量的內(nèi)積完成結(jié)果排序，相對(duì)于已有方案減少了檢索排序計(jì)算量。

1 相關(guān)定義

本方案主要涉及3個(gè)主體：

1）數(shù)據(jù)擁有者（Data Owner， DO），主要負(fù)責(zé)文檔指紋和文檔特征向量的生成、SMRI索引的構(gòu)建，以及文檔的加密。

2）云服務(wù)器（Cloud Server， CS），負(fù)責(zé)密文多關(guān)鍵詞的檢索和排序工作，并將排序后的top-k加密文檔發(fā)送給授權(quán)用戶。

3）授權(quán)用戶（Data User， DU），提交查詢請(qǐng)求，并根據(jù)云端返回的top-k密文結(jié)果進(jìn)行解密，最終得到符合需求的明文文件。

為了方便描述，本方案定義如下符號(hào)：

1）F：明文文檔集，規(guī)模為n，表示為F={f1， f2，…， fn};

2）EF：密文文檔集，表示為EF={d1，d2，…，dn}，di對(duì)應(yīng)于fi;

3）S：文檔指紋集，表示為S={S1，S2，…，Sn}，Si對(duì)應(yīng)于fi;

4）W：關(guān)鍵詞詞典，規(guī)模為m，表示為W={w1，w2，…，wm};

5）V：明文文檔向量集，表示為V={dv1，dv2，…，dvn}，dvi對(duì)應(yīng)于fi;

6）FV：擴(kuò)展文檔向量集，表示為FV={DV1，DV2，…，DVn}，DVi對(duì)應(yīng)于dvi;

7）EV：加密文檔向量集，表示為EV={ev1，ev2，…，evn}，evi對(duì)應(yīng)于DVi;

8）Doc：文檔指紋與文檔向量構(gòu)成的二元組集，表示為Doc={doci=（Si，evi）|i=1，2，…，n}，doci對(duì)應(yīng)于fi;

9）Tq：查詢陷門，表示為Tq={Sq，eq}，其中Sq表示查詢指紋，eq表示加密的查詢向量。

2 基于Simhash的密文排序檢索方案

本方案采用“過(guò)濾精化”思想，先通過(guò)分段指紋匹配進(jìn)行初步排序得到候選結(jié)果集，縮小目標(biāo)結(jié)果集范圍，減少排序計(jì)算量，再通過(guò)計(jì)算漢明距離和向量?jī)?nèi)積進(jìn)行精確化排序，得到與查詢關(guān)鍵詞相關(guān)分最高的top-k結(jié)果集。

2.1 SMRI索引的構(gòu)建

1）文檔預(yù)處理。數(shù)據(jù)擁有者利用AES算法將明文文檔集合F加密得到密文文檔集合EF，抽取文檔集關(guān)鍵詞得到關(guān)鍵詞詞典W，詞典規(guī)模為m。然后將每篇文檔處理成64位的Simhash指紋Si，利用VSM將每篇文檔處理成m維文檔向量，文檔向量的每個(gè)維度是對(duì)應(yīng)關(guān)鍵詞的權(quán)重值TF，若文檔中不存在該對(duì)應(yīng)位的關(guān)鍵詞，則TF的值為0，TF采用式（1）計(jì)算：

TFwi=TFf，wi′∑wi∈w（TFf，wi′）2（1）

其中：TFwi是文件f中的關(guān)鍵字wi的詞頻值，TFf，wi′=1+ln Nf，wi，Nf，wi是文件f中關(guān)鍵詞wi的數(shù)量。

2）向量加密?；谖墨I(xiàn)[11]中SkNN加密算法的思想，數(shù)據(jù)擁有者隨機(jī)生成一個(gè)（m+u）維{0，1}指示向量P和兩個(gè)（m+u）×（m+u）維可逆矩陣M1、M2，記為sk={P， M1， M2}，sk是加密密鑰，并發(fā)送給授權(quán)的數(shù)據(jù)使用者。對(duì)于每個(gè)文檔向量dvi，首先擴(kuò)展文檔向量得到DVi={dvi，r1，r2，…，ru}，其中r1～ru是隨機(jī)數(shù)。然后利用P分割擴(kuò)展向量：當(dāng)P[j]=0時(shí)，DV′[j]=DV″[j]=DV[j];當(dāng)P[j]=1時(shí)，將DV′[j]設(shè)置為一個(gè)隨機(jī)數(shù)，DV″[j]=DV[j]-DV′[j]。最后通過(guò)矩陣變換加密文檔向量得到evi={MlT×DV′， M2T×DV″}。

3）構(gòu)建B+樹(shù)。本文利用分段指紋和加密向量構(gòu)建搜索索引樹(shù)，B+樹(shù)的葉子節(jié)點(diǎn)結(jié)構(gòu)如式（2）所示：

leafNode=〈segKey，docList〉（2）

其中：segkey指分段指紋，docList指具有相同分段指紋的doc集合。例如，指紋S3和S4的第一個(gè)分段都是001011，則插入B+樹(shù)后即為葉子節(jié)點(diǎn)〈001011， {（S1， ev1）， （S2， ev2）}〉。

B+樹(shù)的非葉節(jié)點(diǎn)結(jié)構(gòu)如式（3）所示：

Node=〈segKeyList，child[t]〉（3）

其中：segkeyList指分段指紋集合，分段指紋是二進(jìn)制序列，可以進(jìn)行大小排序;child[t]是指向孩子節(jié)點(diǎn)的指針，t是B+樹(shù)的階數(shù)。

對(duì)于64位的哈希指紋，當(dāng)指紋之間的漢明距離不大于3時(shí)，文檔被定義為相似的[17]。為了快速找到漢明距離不大于3的指紋，將Simhash指紋分成4段，根據(jù)抽屜原理，則必有1段是相等的。為了方便講解索引樹(shù)的構(gòu)建和檢索排序過(guò)程，將指紋簡(jiǎn)化為16位。假設(shè)有4篇文檔，如圖1所示，將每個(gè)指紋分為4段，前面兩位表示分段位置。具體的索引構(gòu)簡(jiǎn)算法如算法1所示。

算法1 SMRI索引構(gòu)建算法。

輸入：Doc集合;

輸出：SMRI索引。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

1）

for each doc in Doc do

2）

splitSimhash=split（doc.Si）;//將doc中的Simhash指紋分為4段

3）

for each Si， j in splitSimhash// j=1，2，3，4

4）

if（不存在segKey等于Si， j的葉節(jié)點(diǎn)）

5）

if（沒(méi)有節(jié)點(diǎn)需要分裂）

6）

newLeafNode.insert（〈Si， j， {doc}〉//直接插入新的葉子節(jié)點(diǎn)

7）

else

8）

按照B+樹(shù)結(jié)構(gòu)進(jìn)行節(jié)點(diǎn)分裂;

9）

newLeafNode.insert（〈Si， j， {doc}〉）;

10）

end if

11）

else

12）

leaf = findLeafNode（Si， j）;// 找到segkey等于Si， j的葉節(jié)點(diǎn)leaf;

13）

leaf.insert（doc）;// 將doc添加至leaf的docList

14）

end if

15）

end for

16）

end for

17）

return SMRI

程序后

2.2 基于SMRI的多關(guān)鍵詞檢索

1）生成查詢陷門Tq。授權(quán)用戶提交查詢關(guān)鍵詞Wq，將Wq處理成64位查詢指紋Sq并將指紋分成四段，然后利用VSM生成查詢向量q，查詢向量的每個(gè)維度是對(duì)應(yīng)的關(guān)鍵詞的IDF值，IDF的值采用式（2）計(jì)算：

IDFwi=IDFwi′∑wi∈w（IDFwi′）2（4）

其中：IDFwi′是關(guān)鍵字wi的逆文檔頻率，IDFwi′=ln（1+N/Nwi），Nwi是包含關(guān)鍵字wi的文件數(shù)量，N是總文件數(shù)。

授權(quán)用戶根據(jù)數(shù)據(jù)擁有者發(fā)送的加密密鑰sk加密查詢向量。首先擴(kuò)展查詢向量q得到Q={R*q， R1， R2， …， Ru}，從R1～Ru中隨機(jī)選取v位置為1，其余u-v位置為0。然后利用P分割擴(kuò)展向量：當(dāng)P[j]=0時(shí)，將Q′[j]設(shè)置為一個(gè)隨機(jī)數(shù)，Q″[j]=Q[j]-Q′[j];當(dāng)P[j]=1時(shí)，Q′[j]=Q″[j]=Q[j]。最后通過(guò)矩陣變換得到加密查詢向量eq={Ml-1×Q′， M2-1×Q″}。查詢陷門Tq記為Tq = （Sq， eq），授權(quán)用戶將分段指紋和查詢陷門提交給云服務(wù)器。

2）基于SMRI的分段指紋匹配檢索。云服務(wù)器根據(jù)分段查詢指紋在SMRI索引中進(jìn)行檢索，找到所有segKey等于分段指紋的葉子節(jié)點(diǎn)，得到候選結(jié)果集CR。如圖2所示，假設(shè)分段指紋Sq=1011001101010110，以第一個(gè)分段查詢指紋Sq1=001011為例，由根節(jié)點(diǎn)Node0開(kāi)始搜索，在Node0的segKeyList中進(jìn)行二分查找找到100011，由于001011小于100011，于是向左邊查找到Node1，在Node1的segKeyList中進(jìn)行二分查找得到010010，由于001011小于010010，繼續(xù)向左邊查找到Node4，在Node4的segKeyList中進(jìn)行二分查找找到與Sq1相等的二進(jìn)制序列001011，從而得到葉子節(jié)點(diǎn)leafNode3，將leafNode3中的docList={（S3，ev3），（S4，ev4）}添加至CR。Sq2、Sq3、Sq4以同樣的方式進(jìn)行查找，分別得到{（S3，ev3）}、{（S3， ev3）， （S4， ev4）}、{（S3，ev3）， （S3， ev3）， （S4， ev4）}，最后將所有結(jié)果取并集得到CR={（S2， ev2）， （S3， ev3）， （S4，ev4）}。

2.3 top-k檢索結(jié)果排序

通過(guò)2.2節(jié)的分段指紋查找已經(jīng)過(guò)濾了大量不相關(guān)文檔，完成了初步排序，即漢明距離大于3的文檔。漢明距離用式（4）計(jì)算：

Hd（Sm，Sn）=∑64i=1Sm[i]⊕Sn[i]（5）

其中：Sm、Sn都是n位的Simhash指紋，⊕表示異或運(yùn)算。

相關(guān)性分?jǐn)?shù)是用來(lái)度量文檔與查詢關(guān)鍵字的匹配程度。根據(jù)“TF×IDF”規(guī)則，原始文檔向量與查詢向量的相關(guān)性分?jǐn)?shù)由式（5）計(jì)算：

Score（dv，q）=dv·q=∑wi∈wqTFwi×IDFwi（6）

擴(kuò)展向量的相關(guān)分計(jì)算如下：

Score（DV，Q）=Score（dv，q）+∑ui=1ri×Ri=

Score（dv，q）+ε（7）

直接將明文向量部署到云服務(wù)器上，攻擊者可以根據(jù)向量每個(gè)維度的詞頻值進(jìn)行統(tǒng)計(jì)攻擊，對(duì)照詞頻字典攻擊關(guān)鍵詞信息，引起隱私泄漏等安全問(wèn)題。因此在云服務(wù)器端計(jì)算的是加密向量的相關(guān)分，加密文檔向量與加密查詢向量的相關(guān)分計(jì)算如式（8）：

Score（ev，eq）=（M1TDV′）·（M1-1Q′）+（M2TDV″）·（M2-1Q″）=

（M1TDV′）TM1-1Q′+（M2TDV″）T·M2-1Q″=

DV′TM1M1-1Q′+DV″M2M2-1Q″=

DV′·Q′+DV″·Q″=DV·Q（8）

由式（8）可得，加密向量的相關(guān)分與擴(kuò)展向量相關(guān)分保持一致。按照這種方法便可以在云服務(wù)器計(jì)算各個(gè)文檔與多關(guān)鍵詞查詢陷門的相關(guān)分并進(jìn)行排序。

對(duì)于2.2節(jié)中得到的候選集CR，排序過(guò)程如圖3所示。假設(shè)用戶要求返回文檔數(shù)為2，首先計(jì)算查詢指紋與候選文檔指紋的漢明距離Hd，根據(jù)漢明距離排序得到對(duì)應(yīng)的排序向量集合VR，再計(jì)算加密查詢向量與VR的向量?jī)?nèi)積score，根據(jù)內(nèi)積進(jìn)行排序，得到最后的top-k結(jié)果并返回給用戶。

3 安全性分析

1）文檔隱私保障。對(duì)文檔集采用AES算法加密。由于文檔和索引向量采用不同的方式進(jìn)行加密，增加了攻擊者的攻擊難度。對(duì)文件的檢索、插入和刪除操作都是基于哈希指紋，不會(huì)涉及到文件的內(nèi)容，因此不會(huì)泄露文檔信息。

2）關(guān)鍵詞隱私保障。假設(shè)u=0，如果要解出文檔向量，就要構(gòu)建方程組C′=M1T×DV′和C″=M2T×DV″，在n篇文檔向量中有2n×（m+1）個(gè)未知量，在可逆矩陣（M1， M2）中有2（m+1）2個(gè)未知量，由于只有2n×（m+1）個(gè)等式，少于未知量的個(gè)數(shù)，對(duì)于查詢向量同理，所以沒(méi)有足夠的信息推斷出向量或者密鑰矩陣（M1， M2），攻擊者無(wú)法得到關(guān)鍵詞有關(guān)信息。

3）相關(guān)分隱私保障。根據(jù)式（7），在相關(guān)分中引入隨機(jī)值ε。如果ε有2ω種可能性，則兩兩相等的概率是1/2ω。本文將查詢向量擴(kuò)展u位，隨機(jī)選取v位設(shè)為1，那么ε就有Cvu種不同的組合，取v=u/2時(shí)，ε能取得最多的可能性。即隨機(jī)選擇一半的擴(kuò)展位置為1生成擴(kuò)展查詢向量。設(shè)置每個(gè)擴(kuò)展位服從均勻分布U（μ′-， μ′+），根據(jù)中心極限定理可得，ε服從正態(tài)分布N（u，σ2），并且μ=0.5uμ′，σ=（1/6）u·。由此可見(jiàn)，詞頻統(tǒng)計(jì)的特殊性被打破，保障了關(guān)鍵詞的相關(guān)分隱私安全。

4）索引隱私保障。指紋索引樹(shù)中含有指紋及加密后的文檔向量，2）中已經(jīng)分析了文檔向量的隱私安全性。文檔指紋是基于單向密鑰Simhash函數(shù)生成的，定義如下：

Sim（hk，data）：{0，1}nhk{0，1}m（9）

假設(shè)Sim（hk，data）在選擇明文攻擊中，不具有不可區(qū)分性，那么敵手A可以構(gòu)建一個(gè)算法A′，并利用該算法區(qū)分一些函數(shù)Sim′（·）是偽隨機(jī)函數(shù)還是真實(shí)的隨機(jī)函數(shù)。當(dāng)A′訪問(wèn)預(yù)言機(jī)OSim′（·）時(shí)，輸入一個(gè)參數(shù)a，OSim′（·）返回結(jié)果值Sim′（a）。敵手A收到指紋生成請(qǐng)求后，通過(guò)詢問(wèn)OSim′（·）進(jìn)行應(yīng)答。然后敵手輸出兩個(gè)長(zhǎng)度相同的挑戰(zhàn)c1和c2，A′選擇一個(gè)隨機(jī)數(shù)b （0

5）查詢無(wú)關(guān)聯(lián)性。數(shù)據(jù)使用者根據(jù)數(shù)據(jù)擁有者發(fā)送的密鑰sk，通過(guò)添加u個(gè)虛位擴(kuò)展查詢向量的維度，并將擴(kuò)展向量拆分成兩個(gè)向量。向量分割是隨機(jī)的，因此對(duì)于相同的查詢，每次產(chǎn)生的查詢陷門也不相同，實(shí)現(xiàn)了查詢的無(wú)關(guān)聯(lián)性。

4 實(shí)驗(yàn)結(jié)果與分析

選擇百度學(xué)術(shù)上6000篇英文論文作為測(cè)試數(shù)據(jù)，實(shí)驗(yàn)環(huán)境：Windows 7 （64位），CPU為Intel Core i7-7700HQ@（2.80GHz），內(nèi)存4GB，使用Java語(yǔ)言編程。

4.1 索引構(gòu)建效率

本文方案與文獻(xiàn)[12]中的EDMRS（Enhanced Dynamic Multi-keyword Ranked Search）方案和文獻(xiàn)[13]中的EASMS（Efficient and Accurate Secure Multi-keyword Search）方案進(jìn)行比較。假設(shè)文檔數(shù)量為n，構(gòu)建B+樹(shù)的時(shí)間復(fù)雜度為O（n（logt n）（t是B+樹(shù)的階數(shù)，本方案中取t=8），3種方案的索引時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果如圖4所示。

圖4（a）詞典規(guī)模固定m=4000的情況下，EASMS方案和EDMRS方案都是直接構(gòu)造了一個(gè)帶有高維加密向量作為數(shù)據(jù)節(jié)點(diǎn)的索引樹(shù)，時(shí)間復(fù)雜度為O（n·（m+u）2），m不變時(shí)隨著文檔規(guī)模的增大，索引構(gòu)建時(shí)間呈線性增長(zhǎng)。而本文SMRI方案是以維度很低的18位Simhash分段指紋為數(shù)據(jù)節(jié)點(diǎn)，通過(guò)比較二進(jìn)制串的大小構(gòu)建B+樹(shù)，文檔規(guī)模增大時(shí)，索引構(gòu)建時(shí)間呈線性增長(zhǎng)，但是由于主要的時(shí)間消耗在密鑰矩陣的生成上，而當(dāng)詞典規(guī)模固定時(shí)，隨著文檔數(shù)量的增加，整體時(shí)間增長(zhǎng)緩慢。圖4（b）文檔規(guī)模固定n=1000，影響3種方案構(gòu)建索引的主要因素是向量維數(shù)。向量加密的復(fù)雜度為O（（m+u）2），隨著詞典大小的增加，向量維數(shù)增加，加密向量耗時(shí)呈平方級(jí)增長(zhǎng)，3種方案的索引構(gòu)建時(shí)間都呈現(xiàn)迅速增長(zhǎng)。但是由于EDMRS和EASMS方案是通過(guò)計(jì)算高維向量?jī)?nèi)積生成索引樹(shù)的，而SMRI方案是通過(guò)分段指紋構(gòu)建B+樹(shù)，雖然都呈現(xiàn)平方增長(zhǎng)，但是SMRI方案總體耗時(shí)較少，增長(zhǎng)速度相對(duì)緩慢，而且隨著詞典規(guī)模的逐步增加，優(yōu)勢(shì)愈發(fā)明顯，前兩個(gè)方案可能造成高維空間的“維度災(zāi)難”。

設(shè)定文件數(shù)n=1000，不同詞典規(guī)模下三種方案的索引空間開(kāi)銷如表1所示。當(dāng)葉節(jié)點(diǎn)的數(shù)量相同時(shí)，B+樹(shù)具有比二叉樹(shù)更少的節(jié)點(diǎn)個(gè)數(shù)，并且內(nèi)部節(jié)點(diǎn)是低維散列指紋，高維向量?jī)H存儲(chǔ)在葉節(jié)點(diǎn)中，相比EDMRS方案和EASMS方案，本方案降低了空間存儲(chǔ)代價(jià)。

4.2 索引檢索效率

如圖5所示，假設(shè)包含關(guān)鍵詞的葉節(jié)點(diǎn)數(shù)為θ，在EDMRS方案中，索引樹(shù)的高度為lb n，相關(guān)分計(jì)算復(fù)雜度為O（m+u），整體檢索時(shí)間復(fù)雜度為O（θ·（m+u）（lb n），EASMS方案具有與EDMRS相同的時(shí)間復(fù)雜度。EASMS方案構(gòu)建了層次化聚類索引樹(shù)，先找到聚類中心再計(jì)算聚類向量的內(nèi)積，檢索時(shí)間接近EDMRS方案的一半。在本方案中，t階B+樹(shù)的最大高度為logt/2（n/2）+1，二分查找的時(shí)間復(fù)雜度為lb t，因此檢索的時(shí)間復(fù)雜度為O（lb t·（logt/2（n/2）+1）+θ·（1+m+u））。在實(shí)際檢索中時(shí)間一定小于lb t·（logt/2（n/2）+1）+θ·（1+m+u），因?yàn)橐恍┕?jié)點(diǎn)具有共同的祖先并且具有相同的訪問(wèn)路徑，不需要每次都從根節(jié)點(diǎn)重新搜索。而且本方案在檢索過(guò)程中是對(duì)哈希指紋進(jìn)行異或操作，EASMS和EDMRS方案是通過(guò)計(jì)算高維向量的內(nèi)積進(jìn)行檢索，因此本方案的實(shí)際檢索耗時(shí)很少。

圖5（a） 固定詞典規(guī)模m=4000，返回結(jié)果數(shù)k=20，用戶輸入檢索詞個(gè)數(shù)Wq=10，隨著文檔規(guī)模的增加，EASMS和EDMRS需要計(jì)算的向量個(gè)數(shù)也隨之增加，檢索時(shí)間隨文檔規(guī)模的增加而呈對(duì)數(shù)增長(zhǎng)。對(duì)于本方案來(lái)講，在指紋匹配階段可能對(duì)比的節(jié)點(diǎn)數(shù)會(huì)增加，也是呈現(xiàn)對(duì)數(shù)級(jí)增長(zhǎng)，但是增長(zhǎng)趨勢(shì)緩慢。

圖5（b） 詞典規(guī)模固定m=4000，文檔規(guī)模固定n=1000，用戶輸入檢索詞個(gè)數(shù)Wq=10，隨著返回結(jié)果數(shù)k的增加，EASMS和EDMRS需要計(jì)算的向量數(shù)增加，檢索時(shí)間隨之增加，本方案只需要通過(guò)指紋匹配找到候選集，然后計(jì)算陷門與候選集中每個(gè)元素之間的相關(guān)性，復(fù)雜度為O（m+u），這樣減少了向量?jī)?nèi)積的計(jì)算，節(jié)省了大量時(shí)間并顯著地提高檢索效率。

圖5（c）當(dāng)檢索關(guān)鍵詞數(shù)量增加時(shí)，EDMRS和EASMS方案深度遍歷二叉樹(shù)計(jì)算向量?jī)?nèi)積進(jìn)行排序的時(shí)間復(fù)雜度和時(shí)間不會(huì)受到影響，SMRI方案進(jìn)行分段指紋和向量?jī)?nèi)積計(jì)算的時(shí)間復(fù)雜度和耗時(shí)也不會(huì)受到影響，由于SMRI方案前期通過(guò)二進(jìn)制字符串的匹配檢索和初步排序，后期計(jì)算內(nèi)積的向量個(gè)數(shù)相比前兩個(gè)方案大大減少，因此整體檢索時(shí)間較少。

5 結(jié)語(yǔ)

保證數(shù)據(jù)的機(jī)密性和檢索的高效性是密文檢索的重點(diǎn)，目前基于VSM的多關(guān)鍵詞排序檢索方案存在計(jì)算量大、檢索速度慢的問(wèn)題。本文提出了一種基于SMRI的密文多關(guān)鍵詞排序檢索方案，該方案基于“過(guò)濾精化”策略，利用Simhash的降維思想構(gòu)建搜索索引，減少了索引的計(jì)算和存儲(chǔ)開(kāi)銷，提高了檢索排序效率，使用單向密鑰哈希算法和SkNN算法保證了檢索過(guò)程的安全，實(shí)驗(yàn)結(jié)果證明了該方案的高效性。下一步研究工作將集中在多關(guān)鍵詞模糊檢索方面，提高方案的實(shí)用性。

參考文獻(xiàn)

[1]馮登國(guó)，張敏，張妍，等.云計(jì)算安全研究[J].軟件學(xué)報(bào)，2011，22（1）：71-83.（FENG D G， ZHANG M， ZHANG Y， et al. Study on cloud computing security [J]. Journal of Software， 2011， 22（1）： 71-83.）

[2]SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data [C]// Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE，? 2000： 44-55.

[3]GOH E. Secure indexes [EB/OL]. [2018-12-16]. https：//eprint.iacr.org/2003/216.pdf.

[4]KUZU M， ISLAM M S， KANTARCIOGLU M. Efficient similarity search over encrypted data [C]// Proceedings of the IEEE? 28th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2012： 1156-1167.

[5]KRISHNA C R， MITTAL S A. Privacy preserving synonym based fuzzy multi-keyword ranked search over encrypted cloud data [C]// Proceedings of the 2016 International Conference on Computing， Communication and Automation. Piscataway， NJ： IEEE， 2016： 1187-1194.

[6]WANG J， YU X， ZHAO M. Privacy-preserving ranked multi-keyword fuzzy search on cloud encrypted data supporting range query [J]. Arabian Journal for Science and Engineering， 2015， 40（8）： 2375-2388.

[7]YAO H， XING N， ZHOU J， et al. Secure index for resource-constraint mobile devices in cloud computing [J]. IEEE Access， 2016， 4： 9119-9128.

[8]LI X， CUI Y， ZHOU M， et al. Efficient multi-keyword fuzzy search on encrypted data in cloud storage [C]// Proceedings of the 2017 4th International Conference on Information Science and Control Engineering. Washington， DC： IEEE Computer Society， 2017， 1： 288-294.

[9]CAO N， WANG C， LI M， et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data [J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（1）： 222-233.

[10]LI H， YANG Y， LUAN T H， et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data [J]. IEEE Transactions on Dependable and Secure Computing， 2016， 13（3）： 312-325.

[11]WONG W K， CHEUNG D W， KAO B， et al. Secure kNN computation on encrypted databases[C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 139-152.

[12]XIA Z， WANG X， SUN X， et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data [J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（2）： 340-352.

[13]ZHU X， DAI H， YI X， et al. MUSE： an efficient and accurate verifiable privacy-preserving multi-keyword text search over encrypted cloud data [J]. Security and Communication Networks， 2017， 2017（2）：? No.1923476.

[14]CHEN L， SUN X， XIA Z， et al. An efficient and privacy-preserving semantic multi-keyword ranked search over encrypted cloud data [J]. International Journal of Security and its Applications， 2014， 8（2）： 323-332.

[15]楊宏宇，王玥.云存儲(chǔ)環(huán)境下的多關(guān)鍵字密文搜索方法[J].計(jì)算機(jī)應(yīng)用，2018，38（2）：343-347.（YANG H Y， WANG Y. Multi-keyword ciphertext search method in cloud storage environment [J]. Journal of Computer Applications， 2018， 38（2）： 343-347.）

[16]CHARIKAR M S. Similarity estimation techniques from rounding algorithms[C]// Proceedings of the 34th Annual ACM Symposium on Theory of Computing. New York： ACM， 2002： 380-388.

[17]MANKU G S， JAIN A， das SARMA A. Detecting near-duplicates for Web crawling [C]// Proceedings of the 16th International Conference on World Wide Web. New York： ACM， 2007： 141-150.

[18]楊旸，楊書(shū)略，柯閩.加密云數(shù)據(jù)下基于Simhash的模糊排序搜索方案[J].計(jì)算機(jī)學(xué)報(bào)，2017，40（2）：431-444.（YANG Y， YANG S L， KE M. Ranked fuzzy keyword search based on Simhash over encrypted cloud data [J]. Chinese Journal of Computers， 2017， 40（2）： 431-444.）

This work is partially supported by the Fund of Hubei Key Laboratory of Inland Shipping Technology （NHHY2017003）， the Fund of Hubei Key Laboratory of Transportation Internet of Things （2017Ⅲ028-002）.

LI Zhen， born in 1994， M. S. candidate. Her research interests include information security.

YAO Hanbing， born in 1976， Ph. D.， associate professor. His research interests include information security.

MU Yicheng， born in 1998， B. S. candidate. His research interests include information security.