云存儲(chǔ)環(huán)境下的多關(guān)鍵字密文搜索方法

楊宏宇，王　玥

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)(*通信作者電子郵箱yhyxlx@hotmail.com)

0　引言

隨著大數(shù)據(jù)和云計(jì)算技術(shù)的日益發(fā)展，隱私保護(hù)問(wèn)題愈發(fā)重要。在云存儲(chǔ)環(huán)境下，數(shù)據(jù)擁有者向云服務(wù)器上傳數(shù)據(jù)及用戶搜索所需數(shù)據(jù)時(shí)，都涉及隱私保護(hù)。目前，云存儲(chǔ)環(huán)境下的傳統(tǒng)密文搜索算法搜索效率低，針對(duì)多關(guān)鍵字的搜索方法還不完善，高效的多關(guān)鍵字密文搜索方法已經(jīng)成為目前的研究熱點(diǎn)。

文獻(xiàn)[1]提出加密的云數(shù)據(jù)多關(guān)鍵字排序搜索(Multi-keyword Ranked Search over Encrypted cloud data， MRSE)，通過(guò)坐標(biāo)匹配的方法衡量關(guān)鍵字與文件之間的相似性，由內(nèi)積相似性評(píng)估坐標(biāo)匹配方法。由于該方法的索引采用布爾量化表示，具有相同數(shù)量關(guān)鍵字的文件其相關(guān)性分?jǐn)?shù)相同，導(dǎo)致該方法對(duì)于多關(guān)鍵字搜索的精確度低。文獻(xiàn)[2]提出一種在公共信道傳輸?shù)幕诠€加密的多關(guān)鍵字搜索方法，但該方法在模糊匹配關(guān)鍵字和公鑰加密時(shí)時(shí)間開銷較大，導(dǎo)致該方法效率較低。文獻(xiàn)[3]針對(duì)文件關(guān)鍵字的相似性對(duì)文件聚類并形成聚類索引，在離線的階段完成聚類和聚類索引的生成；但用戶無(wú)法根據(jù)自己需要調(diào)節(jié)關(guān)鍵字權(quán)重值，導(dǎo)致實(shí)際應(yīng)用時(shí)缺乏自適應(yīng)能力。文獻(xiàn)[4]在密文搜索方法中加入加密搜索插件，基于詞頻-逆向文件頻率(Term Frequency-Inverse Document Frequency， TF-IDF)方法對(duì)即將上傳的關(guān)鍵字排序，在一定程度上減少了云服務(wù)器的搜索時(shí)間，但該方法要求用戶與數(shù)據(jù)擁有者必須使用指定加密搜索軟件。文獻(xiàn)[5]提出一種基于層次聚類索引的加密數(shù)據(jù)多關(guān)鍵字排序搜索(Multi-keyword Ranked Search over Encrypted data based on Hierarchical Clustering Index， MRSE-HCI)方法，該搜索方法在構(gòu)建索引時(shí)需要擴(kuò)展維度，導(dǎo)致計(jì)算開銷過(guò)多。

針對(duì)上述方法搜索準(zhǔn)確度較低、搜索效率低且不支持用戶自定義關(guān)鍵字權(quán)重等問(wèn)題，本文首先提出一種改進(jìn)質(zhì)量層次聚類(Improved Quality Hierarchical Clustering，IQHC)算法，并在此基礎(chǔ)上提出一種基于IQHC的加密云數(shù)據(jù)多關(guān)鍵字排序搜索(Multi-keyword Ranked Search over Encrypted cloud data based on IQHC， MRSE-IQHC)方法來(lái)提高多關(guān)鍵字密文搜索時(shí)的搜索效率和準(zhǔn)確性。

云存儲(chǔ)環(huán)境下多關(guān)鍵字密文搜索方法的研究目的是在加密數(shù)據(jù)上進(jìn)行多關(guān)鍵字密文搜索并保護(hù)隱私，通過(guò)MRSE-IQHC方法主要實(shí)現(xiàn)以下目標(biāo)：

1)支持多關(guān)鍵字密文搜索。在云存儲(chǔ)中，可支持多關(guān)鍵字的密文搜索，并將符合用戶要求的前k個(gè)最佳匹配結(jié)果返回給用戶。

2)提高搜索效率。通過(guò)TF-IDF[4]與向量空間模型(Vector Space Model，VSM)[6]的結(jié)合，以及IQHC算法聚類，提高搜索效率，縮短搜索時(shí)間。

3)滿足用戶對(duì)關(guān)鍵字權(quán)重的定義[7]。通過(guò)用戶對(duì)關(guān)鍵字賦予的權(quán)重值，在搜索時(shí)根據(jù)用戶需求進(jìn)行多關(guān)鍵字搜索，優(yōu)先返回符合用戶要求的文件，提高搜索準(zhǔn)確性。

4)隱私保護(hù)。保護(hù)數(shù)據(jù)擁有者和用戶的隱私，攻擊者和云服務(wù)器無(wú)法獲取明文數(shù)據(jù)。

1　系統(tǒng)模型

MRSE-IQHC方法涉及三個(gè)實(shí)體：數(shù)據(jù)擁有者、用戶和云服務(wù)器。這三個(gè)實(shí)體和密文搜索方法組成一個(gè)系統(tǒng)模型，其中，數(shù)據(jù)擁有者和用戶是誠(chéng)實(shí)可信的，云服務(wù)器是半可信的。系統(tǒng)模型的結(jié)構(gòu)如圖1所示。

圖1　系統(tǒng)模型Fig. 1　System model

數(shù)據(jù)擁有者是擁有文件的實(shí)體，能夠提取文件關(guān)鍵字，采用本文提出的IQHC算法對(duì)文件向量聚類生成聚類索引和文件索引，然后將索引和文件加密后上傳至云服務(wù)器。

用戶身份是經(jīng)過(guò)認(rèn)證的，其身份真實(shí)可信，是執(zhí)行搜索操作的實(shí)體。用戶搜索時(shí)定義關(guān)鍵字的權(quán)值并產(chǎn)生搜索請(qǐng)求，在數(shù)據(jù)擁有者的協(xié)助下生成加密的搜索向量(即陷門)。將陷門上傳至云服務(wù)器，等待云服務(wù)器返回搜索結(jié)果。

云服務(wù)器是半可信的服務(wù)器，可存儲(chǔ)數(shù)據(jù)擁有者加密后的文件和索引，并根據(jù)用戶發(fā)送的陷門執(zhí)行搜索操作，向用戶返回所需搜索結(jié)果。

本文研究的密文搜索方法主要針對(duì)系統(tǒng)模型中的三個(gè)實(shí)體。在該系統(tǒng)模型中，對(duì)密文的搜索可分為兩個(gè)階段：離線階段和在線階段。在離線階段，數(shù)據(jù)擁有者采用IQHC算法對(duì)文件向量聚類，根據(jù)聚類結(jié)果產(chǎn)生文件索引和聚類索引。在在線階段，數(shù)據(jù)擁有者采用不同加密方式對(duì)文件索引、聚類索引和文件加密后上傳至云服務(wù)器。用戶根據(jù)需求產(chǎn)生搜索請(qǐng)求，通過(guò)搜索控制機(jī)制將搜索請(qǐng)求發(fā)送給數(shù)據(jù)擁有者。數(shù)據(jù)擁有者由搜索請(qǐng)求構(gòu)建搜索向量，加密后生成陷門并通過(guò)搜索控制機(jī)制將陷門返回給用戶；用戶上傳陷門至云服務(wù)器等待搜索結(jié)果；云服務(wù)器經(jīng)計(jì)算后返回給用戶滿足要求的加密文件；用戶通過(guò)搜索控制機(jī)制從數(shù)據(jù)擁有者處獲得解密密鑰并對(duì)文件解密，完成整個(gè)密文搜索過(guò)程。系統(tǒng)模型中的搜索控制機(jī)制和訪問(wèn)控制機(jī)制均不在本文的研究范圍之內(nèi)。

2　質(zhì)量層次聚類算法的改進(jìn)

2.1　TF-IDF與VSM

以往的密文搜索算法MRSE-HCI[5]僅根據(jù)關(guān)鍵字是否存在構(gòu)建文件向量，沒(méi)有考慮關(guān)鍵字出現(xiàn)的頻率及其重要性，在進(jìn)行多關(guān)鍵字密文搜索時(shí)只能返回給用戶存在該關(guān)鍵字的文件，卻無(wú)法根據(jù)該關(guān)鍵字在文件中出現(xiàn)的頻率及整個(gè)文件集合中的重要性排序后返回給用戶，導(dǎo)致搜索結(jié)果與用戶期望有很大偏差。因此，本文將TF-IDF和VSM相融合構(gòu)建文件向量，可有效解決上述問(wèn)題。

TF-IDF是一種常用于信息檢索與數(shù)據(jù)挖掘的統(tǒng)計(jì)方法，能夠衡量一個(gè)關(guān)鍵字對(duì)于一個(gè)文件或一個(gè)文件集合的重要程度。在TF-IDF中：TF為詞頻，表示某個(gè)關(guān)鍵字在某個(gè)文件中出現(xiàn)的頻率大?。籌DF為逆文件頻率，表示某個(gè)關(guān)鍵字在整個(gè)文件集合中出現(xiàn)的頻率大小，是關(guān)鍵字普遍重要性的度量。TF-IDF方法可計(jì)算每個(gè)關(guān)鍵字的權(quán)值，在密文搜索時(shí)可通過(guò)關(guān)鍵字權(quán)值計(jì)算出用戶所需的文件。在本文研究中，選取關(guān)鍵字作為特征，采用TF與IDF的乘積作為關(guān)鍵字的權(quán)值，在構(gòu)建文件向量時(shí)表示出每個(gè)關(guān)鍵字在文件中出現(xiàn)的次數(shù)及在文件集合中的重要程度，以提升改進(jìn)算法的聚類效果。

VSM是一種文本表示方法，常用于信息檢索領(lǐng)域。假設(shè)文件由多個(gè)不相關(guān)的特征組成，該特征可以是字、詞、短語(yǔ)等，每個(gè)特征之間沒(méi)有先后順序關(guān)系，VSM通過(guò)一些方法對(duì)每個(gè)特征賦予權(quán)值，以權(quán)值作為坐標(biāo)值將一個(gè)文件轉(zhuǎn)化為空間中的向量[6]。VSM將文件向量化，把文本語(yǔ)義處理的問(wèn)題轉(zhuǎn)化為向量之間的數(shù)學(xué)運(yùn)算問(wèn)題。通過(guò)向量之間的數(shù)學(xué)運(yùn)算，如向量距離、向量夾角等方法可精確衡量文件內(nèi)容的相似度。本文算法選取向量距離作為相似度的衡量標(biāo)準(zhǔn)，將VSM應(yīng)用于改進(jìn)算法中，以提高文本聚類效果。本文方法中，通過(guò)TF-IDF與VSM的結(jié)合，可將密文搜索結(jié)果排序，提升搜索的準(zhǔn)確性。

2.2　IQHC算法

在云存儲(chǔ)環(huán)境下的多關(guān)鍵字密文搜索方法中，文件向量的向量維度高、冗余維度多，且數(shù)據(jù)分布稀疏，導(dǎo)致計(jì)算開銷大、密文搜索效率低。本文將主成分分析(Principal Component Analysis， PCA)[8]與質(zhì)量層次聚類(Quality Hierarchical Clustering， QHC)[5]算法相結(jié)合，通過(guò)降低文件向量在向量空間模型中的維度，保留其中最重要的多個(gè)特征再聚類，在此基礎(chǔ)上對(duì)QHC算法進(jìn)行改進(jìn)，提出IQHC算法。IQHC算法的步驟設(shè)計(jì)如下：

步驟1由TF-IDF和VSM生成樣本數(shù)量為n的文件向量D1,D2,…,Dn，其中Di=(d1,d2,…,dp)T(i=1,2,…,n)為p維向量，當(dāng)n>p時(shí)，構(gòu)造樣本矩陣，對(duì)矩陣元素作如下變換得到標(biāo)準(zhǔn)化樣本矩陣Z:

(1)

步驟2求Z的協(xié)方差矩陣C,公式如下：

C=(ZTZ)/(n-1)

(2)

其中ZT是矩陣Z的轉(zhuǎn)置矩陣。

步驟3使用奇異值分解(Singular Value Decomposition, SVD)法求解樣本協(xié)方差矩陣C的特征方程|C-λIp|=0，得到p個(gè)特征根，將p個(gè)特征根按照從大到小排列，并依據(jù)式(3)中貢獻(xiàn)率η確定主成分個(gè)數(shù)，即m可由以下公式計(jì)算：

(3)

選取η的值，由m個(gè)主成分代表η以上的原始信息。針對(duì)每個(gè)特征根λj(j=1,2,…,m)，求解方程組Rb=λjb得到m個(gè)單位特征向量bj(j=1,2,…,m)。

步驟4將標(biāo)準(zhǔn)化后的數(shù)據(jù)變量轉(zhuǎn)換為主成分：

Ul=zlTbj;j=1,2,…,m,l=1,2,…,m

(4)

其中:U1稱為第一主成分，U2稱為第二主成分，……，Um稱為第m主成分。將文件向量用新的主成分表示出來(lái)，得到降維后的文件向量。

步驟5設(shè)定每個(gè)聚類中文件的最大數(shù)量，記為TH，相關(guān)性值的最小值閾值記為min(S)，采用歐氏距離衡量文件間的相關(guān)性以及文件和聚類中心之間的相關(guān)性。

步驟6由K-means[9]聚類算法對(duì)降維后的文件向量聚類。當(dāng)聚類個(gè)數(shù)k值不穩(wěn)定時(shí)，添加一個(gè)新的聚類中心，則隨機(jī)產(chǎn)生k+1個(gè)新的聚類中心進(jìn)行聚類。分別取每個(gè)聚類中最小相關(guān)性分?jǐn)?shù)min(St)(t=1,2,…,k,…)與相關(guān)性值最小值閾值min(S)相比較，若min(St)

步驟7將步驟6中產(chǎn)生的聚類中心集合作為第一級(jí)聚類中心C0，依次檢查每個(gè)聚類中文件的數(shù)量，若文件數(shù)量超過(guò)了預(yù)先設(shè)定的閾值TH，則劃分該聚類為多個(gè)子聚類；否則，不再劃分子聚類。新劃分的子聚類作為下一級(jí)聚類，重復(fù)步驟7直到所有聚類中的樣本數(shù)量都滿足閾值TH的限制。

步驟8重復(fù)上述步驟，直至所有聚類均滿足聚類相關(guān)性和數(shù)量的要求，完成聚類過(guò)程。

3　密文搜索方法

3.1　符號(hào)定義與說(shuō)明

本文提出的MRSE-IQHC方法中首先定義了下列符號(hào)：

Dw：表示由所有關(guān)鍵字構(gòu)成的字典，記為Dw={w1,w2,…,wm}。

Dw′：表示經(jīng)過(guò)IQHC算法聚類后產(chǎn)生的字典，記為Dw′={w1,w2,…,wu}。

wi:表示第i個(gè)關(guān)鍵字。

D:表示所有文件向量的集合，記為D={D1,D2,…,Dn}。

Di:表示第i個(gè)文件。

De:表示加密后文件向量的集合。

n:表示文件向量的個(gè)數(shù)。

r:表示字典中關(guān)鍵字的數(shù)量。

S:表示一個(gè)ubit的隨機(jī)向量，記為S={0,1}u。

M1、M2：均為u×u的可逆矩陣。

Ic:表示加密之后的聚類中心的索引。

Id:表示加密之后文件向量的索引。

V:表示數(shù)據(jù)擁有者生成的聚類索引向量。

Q:表示搜索向量。

Tw:表示陷門。

k:表示用戶要求云服務(wù)器返回的文件數(shù)量。

3.2　MRSE-IQHC方法

基于IQHC算法，本文提出了MRSE-IQHC方法。首先由VSM和TF-IDF構(gòu)造文件向量，然后采用IQHC算法對(duì)文件向量作降維和聚類處理，之后采用K最近鄰(K-Nearest Neighbors，KNN)[10]查詢算法加密索引向量和搜索向量，由用戶定義關(guān)鍵字的權(quán)值構(gòu)建搜索請(qǐng)求加密后進(jìn)行密文搜索。在云存儲(chǔ)環(huán)境下，MRSE-IQHC方法的密文搜索過(guò)程設(shè)計(jì)如下：

步驟1文件向量生成。數(shù)據(jù)擁有者取TF與IDF乘積作為關(guān)鍵字權(quán)重，在VSM中對(duì)即將上傳的文件以向量形式表示，文件向量的每個(gè)維度分別由該位置上關(guān)鍵字的權(quán)重值表示，同時(shí)生成字典Dw并構(gòu)建文件向量集合D。

步驟2索引構(gòu)建。數(shù)據(jù)擁有者使用IQHC算法對(duì)文件向量進(jìn)行聚類，聚類后產(chǎn)生ubit的字典Dw′,根據(jù)聚類的結(jié)果構(gòu)建聚類索引和文件索引。文件索引向量和聚類索引向量長(zhǎng)度均為ubit。

步驟3索引加密。數(shù)據(jù)擁有者通過(guò)KNN[10]查詢算法隨機(jī)生成一個(gè)ubit的隨機(jī)向量S={0,1}u和兩個(gè)規(guī)模為u×u的可逆矩陣M1、M2作為密鑰。分割向量S的每一位由0或1隨機(jī)組成，S中的0、1數(shù)量大致相同，矩陣M1、M2的每一位均為隨機(jī)生成的整數(shù)。分割向量S作為分裂指示器用于分割文件索引及聚類索引，數(shù)據(jù)擁有者根據(jù)S將聚類索引向量V隨機(jī)拆分成兩個(gè)向量V′和V″，向量V′和V″中的第i位分別表示為Vi′和Vi″(i=1,2,…,u)。可逆矩陣M1、M2的轉(zhuǎn)置矩陣M1T、M2T用于加密分割之后的向量V′和V″。當(dāng)S中的第i位為0時(shí)，令Vi″=Vi′=Vi(i=1,2,…,u)；當(dāng)S中的第i位為1時(shí)，令Vi′=Vi-Vi″(i=1,2,…,u)。聚類索引被加密為Ic={M1TV′,M2TV″}，加密的文件索引Id的生成過(guò)程相同。

步驟4文件加密。數(shù)據(jù)擁有者選擇一種安全的對(duì)稱加密算法對(duì)文件加密，并將加密后的文件集合De同之前生成的加密文件索引Id、加密聚類索引Ic發(fā)送至云服務(wù)器。

步驟5陷門生成。用戶選擇要搜索的關(guān)鍵字，按照需求對(duì)關(guān)鍵字賦予不同的權(quán)值并要求返回滿足條件的前k個(gè)文件，構(gòu)造搜索請(qǐng)求，將搜索請(qǐng)求發(fā)送給數(shù)據(jù)擁有者。數(shù)據(jù)擁有者收到搜索請(qǐng)求后，根據(jù)字典Dw′在被請(qǐng)求的關(guān)鍵字位置上賦予用戶已定義的權(quán)重值，產(chǎn)生ubit的搜索向量Q，并用M1-1、M2-1矩陣加密Q。同樣，數(shù)據(jù)擁有者根據(jù)S將搜索向量Q隨機(jī)拆分成兩個(gè)向量Q′和Q″，向量Q′和Q″中的第i位分別表示為Qi′和Qi″(i=1,2,…,u)。當(dāng)S中的第i位為0時(shí)，Qi′=Qi-Qi″(i=1,2,…,u)；當(dāng)S中的第i位為1時(shí)，Qi″=Qi′=Qi(i=1,2,…,u)。搜索請(qǐng)求Q被拆分為Q′和Q″后被矩陣M1-1、M2-1加密得到陷門Tw={M1-1Q′,M2-1Q″}，數(shù)據(jù)擁有者將Tw發(fā)送給用戶。

步驟6搜索過(guò)程。用戶將陷門Tw上傳至云服務(wù)器，云服務(wù)器端采用計(jì)算內(nèi)積方式計(jì)算相關(guān)性分?jǐn)?shù)Score[5]:

Score=Ic·Tw=

{M1TV′,M2TV″}·{M1-1Q′,M2-1Q″}=

V′Q′+V″Q″=VQ

(5)

由式(5)可知，加密后的聚類索引向量Ic和陷門Tw的內(nèi)積運(yùn)算結(jié)果與未加密的聚類索引向量V和搜索向量Q的內(nèi)積運(yùn)算結(jié)果相等,因此在密文狀態(tài)下搜索和明文狀態(tài)下搜索結(jié)果一致，加密并不影響搜索結(jié)果的準(zhǔn)確性。

云服務(wù)器首先計(jì)算陷門Tw和加密聚類索引向量Ic中第一級(jí)聚類中心的內(nèi)積，找到得分最高的第一級(jí)聚類中心。然后，將陷門Tw與該聚類中心的子聚類中心計(jì)算內(nèi)積找到得分最高的第二級(jí)聚類中心。以此類推，直至找到最后一級(jí)得分最高的聚類中心。最后，計(jì)算陷門Tw與加密文件索引向量Id的內(nèi)積，找到得分最高的前k個(gè)加密文件并將結(jié)果反饋給用戶。

步驟7解密過(guò)程。用戶向數(shù)據(jù)擁有者發(fā)送解密請(qǐng)求，得到數(shù)據(jù)擁有者的解密密鑰后對(duì)文件解密。

4　安全性分析

4.1　安全威脅模型

在數(shù)據(jù)擁有者、用戶、云服務(wù)器間的通信過(guò)程中，攻擊者可攔截通信，從所攔截的信息中推導(dǎo)出額外信息。根據(jù)攻擊者獲取的信息，多關(guān)鍵字密文搜索過(guò)程包括兩個(gè)安全威脅模型：已知密文模型和已知背景知識(shí)模型。

已知密文模型攻擊者掌握數(shù)據(jù)擁有者的加密文件、加密后的文件索引和聚類索引，以及用戶提交的加密后的搜索向量。

已知背景知識(shí)模型在已知背景知識(shí)模型中，攻擊者知道關(guān)于數(shù)據(jù)集中更多的統(tǒng)計(jì)知識(shí)信息，比如某些關(guān)鍵字的詞頻信息、關(guān)鍵字和數(shù)據(jù)的對(duì)應(yīng)信息以及陷門的關(guān)聯(lián)信息等。

4.2　方法的安全性分析

在云存儲(chǔ)環(huán)境下，攻擊者攔截?cái)?shù)據(jù)擁有者與云服務(wù)器、用戶與云服務(wù)器之間的通信數(shù)據(jù)，可截獲的信息包括：加密后的聚類索引Ic、加密后的文件索引Id、加密的文件集合De、陷門Tw和相關(guān)性分?jǐn)?shù)Score。

在本文提出的MRSE-IQHC方法中，加密之后的聚類索引Ic、文件索引Id和用戶生成的陷門Tw均是由KNN查詢算法加密之后發(fā)送的，每個(gè)索引向量和陷門在加密時(shí)都被隨機(jī)拆分成兩個(gè)向量，相同關(guān)鍵字的搜索請(qǐng)求生成的陷門不同，因此攻擊者無(wú)法推導(dǎo)出原始向量和搜索請(qǐng)求的明文信息。上傳至云服務(wù)器的文件由數(shù)據(jù)擁有者使用對(duì)稱加密算法加密，密鑰保存在數(shù)據(jù)擁有者處，攻擊者無(wú)法通過(guò)密文獲取文件明文。由于索引和文件均采用不同的加密方式，在一定程度上提高了搜索方法的抗攻擊能力。在搜索階段，攻擊者僅根據(jù)相關(guān)性分?jǐn)?shù)也無(wú)法獲取關(guān)鍵字信息，提高了對(duì)關(guān)鍵字隱私的保護(hù)能力。上述分析表明，在已知密文模型和背景知識(shí)模型條件下，本文方法可保證搜索數(shù)據(jù)的安全性。

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

5.1　實(shí)驗(yàn)數(shù)據(jù)和環(huán)境配置

為了便于文本聚類與效果測(cè)試，本實(shí)驗(yàn)采用復(fù)旦大學(xué)的中文語(yǔ)料庫(kù)[11]，該庫(kù)包含藝術(shù)、歷史、能源、電子、交通等20個(gè)種類的文本共9 804個(gè)文件，且該語(yǔ)料庫(kù)訓(xùn)練集中每一個(gè)文件都已分類。實(shí)驗(yàn)的軟硬件環(huán)境配置為：Intel Core i5- 3570 CPU @ 3.40 GHz CPU, 4.0 GB RAM，Windows 7(64位)操作系統(tǒng), 使用Python語(yǔ)言編程。在相同實(shí)驗(yàn)環(huán)境下，對(duì)MRSE-IQHC、MRSE和MRSE-HCI這三種方法進(jìn)行對(duì)比。

5.2　搜索文件數(shù)量對(duì)搜索時(shí)間的影響測(cè)試

實(shí)驗(yàn)數(shù)據(jù)分為5組,分別選取100、200、300、400、500個(gè)文件，選取的文件大小均在1～50 KB。字典中關(guān)鍵字的數(shù)量r=5 000，搜索請(qǐng)求由10個(gè)關(guān)鍵字組成，每個(gè)關(guān)鍵字賦予1～3的權(quán)值，用戶要求返回10個(gè)文件。針對(duì)不同文件數(shù)量測(cè)試三種方法的搜索時(shí)間，結(jié)果如圖2所示。從圖2可見(jiàn)，在初始時(shí)，本文方法MRSE-IQHC和MRSE方法的搜索時(shí)間比較接近，但本文方法的搜索時(shí)間均小于另外兩種方法。隨著文件數(shù)量的增加，MRSE-HCI方法和MRSE-IQHC方法的搜索時(shí)間基本呈現(xiàn)線性增加，MRSE方法的搜索時(shí)間則呈指數(shù)型增長(zhǎng)，本文方法的搜索時(shí)間明顯小于其他兩種方法。

圖2　搜索文件數(shù)量與搜索時(shí)間的關(guān)系Fig. 2　Relationship between the number of search documents and the search time

5.3　返回文件數(shù)量對(duì)搜索時(shí)間的影響測(cè)試

選取500個(gè)文件，文件大小均在1～50 KB，r=5 000，搜索請(qǐng)求由10個(gè)關(guān)鍵字組成，為每個(gè)關(guān)鍵字賦予1～3的權(quán)值。當(dāng)用戶要求返回5、10、15、20、25個(gè)文件時(shí)，測(cè)試搜索時(shí)間，結(jié)果如圖3所示。由圖3可見(jiàn)，MRSE-IQHC方法的搜索時(shí)間明顯小于其他兩種方法，當(dāng)用戶要求返回的文件數(shù)量改變時(shí)，對(duì)MRSE-IQHC方法的搜索時(shí)間并無(wú)太大影響。MRSE-IQHC方法在進(jìn)行密文搜索時(shí)，需要比較陷門和每一級(jí)聚類中心的相似度，找到最相似的聚類后將陷門與該聚類中的每個(gè)文件進(jìn)行相似度的計(jì)算，然后選取最相似的前k個(gè)文件。因此，當(dāng)返回文件的數(shù)量即k值增加時(shí)，搜索計(jì)算量相同，返回文件數(shù)量對(duì)搜索時(shí)間不會(huì)有太大影響。

圖3　返回文件數(shù)量與搜索時(shí)間的關(guān)系Fig. 3　Relationship between the number of retrieved documents and search time

5.4　搜索關(guān)鍵字?jǐn)?shù)量對(duì)搜索時(shí)間的影響測(cè)試

仍選取500個(gè)文件，文件大小均在1～50 KB，r=5 000，用戶要求返回10個(gè)文件。分別測(cè)試用戶請(qǐng)求1、2、3、4、5個(gè)關(guān)鍵字時(shí)的搜索時(shí)間，結(jié)果如圖4所示。從圖4可見(jiàn)：MRSE-IQHC的搜索時(shí)間遠(yuǎn)小于其他兩種方法；隨著搜索請(qǐng)求中關(guān)鍵字?jǐn)?shù)量的增加，MRSE方法搜索時(shí)間比較穩(wěn)定，MRSE-HCI方法和MRSE-IQHC方法的搜索時(shí)間均呈線性增加。因?yàn)镸RSE-IQHC方法根據(jù)搜索關(guān)鍵字?jǐn)?shù)量構(gòu)建搜索請(qǐng)求時(shí)，需要在關(guān)鍵字相對(duì)應(yīng)位置上賦予權(quán)值，關(guān)鍵字?jǐn)?shù)量改變時(shí)，陷門的向量維數(shù)沒(méi)有減少，但搜索的計(jì)算量會(huì)隨著關(guān)鍵字?jǐn)?shù)量的增加而增加，因此搜索時(shí)間會(huì)呈線性增加的趨勢(shì)。

圖4　搜索關(guān)鍵字?jǐn)?shù)量與搜索時(shí)間的關(guān)系Fig. 4　Relationship between the number of search keywords and search time

5.5　搜索準(zhǔn)確性測(cè)試

還是選取500個(gè)文件，文件大小均為1～50 KB，r=5 000，用戶請(qǐng)求搜索10個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字權(quán)值在1～3，分別測(cè)試在返回不同數(shù)量文件時(shí)三種方法的搜索準(zhǔn)確性，結(jié)果如表1所示。從表1可見(jiàn)，MRSE-IQHC方法的搜索準(zhǔn)確性明顯高于其他兩種方法。因?yàn)镸RSE-IQHC方法將TF-IDF與VSM相結(jié)合構(gòu)建文件向量，搜索階段由用戶自定義關(guān)鍵字權(quán)值，因此可優(yōu)先選出含有重要關(guān)鍵字的文件，提升了密文搜索的準(zhǔn)確率；而另外兩種方法只考慮文件是否包含關(guān)鍵字，并未考慮用戶需求，所以準(zhǔn)確率低于本文方法。

表1　搜索準(zhǔn)確率對(duì)比　%Tab. 1　Comparison of search accuracy　%

6　結(jié)語(yǔ)

本文提出一種基于改進(jìn)質(zhì)量層次聚類的加密云數(shù)據(jù)多關(guān)鍵字排序搜索方法MRSE-IQHC。該方法首先通過(guò)TF-IDF與VSM的結(jié)合構(gòu)建文件向量，可有效考慮關(guān)鍵字在文件集合中出現(xiàn)頻率和重要性；其次，利用IQHC算法對(duì)文件向量聚類，根據(jù)聚類結(jié)果構(gòu)造聚類索引和文件索引，在搜索時(shí)可有效提高密文搜索效率；最后，用戶在搜索時(shí)自定義關(guān)鍵字權(quán)值，增強(qiáng)了方法的自適應(yīng)能力并提高了檢索結(jié)果的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明，本文方法在搜索效率和準(zhǔn)確性方面優(yōu)于MRSE和MRSE-HCI方法。

參考文獻(xiàn):

[1]CAO N, WANG C, LI M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data [C]// IEEE INFOCOM 2011: Proceedings of the 30th IEEE International Conference on Computer Communications. Piscataway, NJ: IEEE, 2011: 829-837.

[2]秦志光,包文意,趙洋,等.云存儲(chǔ)中一種模糊關(guān)鍵字搜索加密方案[J].信息網(wǎng)絡(luò)安全,2015(6):7-12. (QIN Z G, BAO W Y, ZHAO Y, et al. A fuzzy keyword search scheme with encryption in cloud storage [J]. Netinfo Security, 2015(6): 7-12.)

[3]HANDA R, CHALLA R K. A cluster based multi-keyword search on outsourced encrypted cloud data [C]// INDIACom 2015： Proceedings of the 2nd International Conference on Computing for Sustainable Global Development. Piscataway, NJ: IEEE, 2015: 115-120.

[4]王雅山.云存儲(chǔ)平臺(tái)中加密數(shù)據(jù)的多關(guān)鍵字排序搜索技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2015:12-38. (WANG Y S. Secure rank-ordered search of multi-keyword in cloud storage platform [D]. Harbin: Harbin Institute of Technology, 2015: 12-38.)

[5]CHEN C, ZHU X, SHEN P, et al. An efficient privacy-preserving ranked keyword search method [J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(4): 951-963.

[6]孔振.基于VSM的文本分類系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[D].哈爾濱:哈爾濱工業(yè)大學(xué),2014:15-17. (KONG Z. The design and implementation of text classification system based on VSM [D]. Harbin: Harbin Institute of Technology, 2014: 15-17.)

[7]郭文杰,張應(yīng)輝,鄭東.云存儲(chǔ)中支持詞頻和用戶喜好的密文模糊檢索[J].深圳大學(xué)學(xué)報(bào)(理工版),2015,32(5):532-537. (GUO W J, ZHANG Y H, ZHENG D. Fuzzy search over encrypted data supporting word frequencies and user preferences in cloud storage [J]. Journal of Shenzhen University (Science and Engineering), 2015, 32(5): 532-537.)

[8]楊宏宇,常媛.基于K均值多重主成分分析的App-DDoS檢測(cè)方法[J].通信學(xué)報(bào),2014,35(5):16-24. (YANG H Y, CHANG Y. App-DDoS detection method based on K-means multiple principal component analysis [J]. Journal on Communications, 2014, 35(5): 16-24.)

[9]彭長(zhǎng)生.基于Fisher判別的分布式K-Means聚類算法[J].江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(4):422-427. (PENG C S. Distributed K-Means clustering algorithm based on Fisher discriminant ratio [J]. Journal of Jiangsu University (Natural Science Edition), 2014, 35(4): 422-427.)

[10]WONG W K, CHEUNG D W-L, KAO B, et al. Secure kNN computation on encrypted databases [C]// SIGMOD ’09: Proceedings of the 2009 ACM Special Interest Group on Management of Data International Conference on Management of Data. New York: ACM, 2009: 139-152.

[11]李榮陸.文本分類語(yǔ)料庫(kù)(復(fù)旦)測(cè)試語(yǔ)料[EB/OL]. [2017- 07- 06]. http://www.nlpir.org/?action-viewnews-itemid-103. (LI R L. Text categorization corpus (Fudan) test corpus [EB/OL]. [2017- 07- 06]. http://www.nlpir.org/?action-viewnews-itemid-103.)

[12]JOY E C, KALIANNAN I. Multi keyword ranked search over encrypted cloud data [J]. International Journal of Applied Engineering Research, 2014, 9: 7149-7176.

[13]FU Z, SUN X, LIU Q, et al. Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing [J]. IEICE Transactions on Communications, 2015, 98(1): 190-200.

[14]YAO L, GU J, GAO Y. Optimized ciphertext retrieval for cloud computing based on dynamic clustering [C]// Proceedings of the 3rd ACM Workshop on Mobile Sensing, Computing and Communication. New York: ACM, 2016: 35-39.

[15]KRISHNA C R, HANDA R. Dynamic cluster based privacy-preserving multi-keyword search over encrypted cloud data [C]// Proceedings of the 2016 6th Conference on Cloud System and Big Data Engineering. Piscataway, NJ: IEEE, 2016: 146-151.