徐光偉 史春紅 王文濤 潘 喬 李 鋒
(東華大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620)
現(xiàn)今,云存儲給數(shù)據(jù)用戶(個人和企業(yè))提供了一個第三方服務(wù)平臺.為了節(jié)省本地存儲成本和管理成本,用戶可以將自己的數(shù)據(jù)外包到云服務(wù)器[1].但是,將數(shù)據(jù)(特別是敏感數(shù)據(jù))直接上傳到云服務(wù)器中,使得數(shù)據(jù)擁有者將數(shù)據(jù)的管理權(quán)限完全給予云服務(wù)提供商,數(shù)據(jù)安全性不能得到保證[2].為了保證上傳數(shù)據(jù)的隱私性,目前最常用的方法是數(shù)據(jù)擁有者將數(shù)據(jù)加密后再上傳到云服務(wù)器,這帶來了新的問題:傳統(tǒng)的檢索技術(shù)不再適用[3].為了能夠使用戶有效地獲取加密數(shù)據(jù),研究人員提出了可搜索加密技術(shù)(searchable encryption, SE)[4].首先,數(shù)據(jù)擁有者在上傳數(shù)據(jù)文件之前,根據(jù)數(shù)據(jù)文件來抽取關(guān)鍵詞,并建立索引.然后,將索引和數(shù)據(jù)文件加密并上傳到云服務(wù)器.當(dāng)數(shù)據(jù)使用者想要獲取加密文件時,數(shù)據(jù)使用者輸入相關(guān)關(guān)鍵詞并使用相應(yīng)的加密算法進(jìn)行加密生成安全陷門,然后將安全陷門發(fā)送給云服務(wù)器,云服務(wù)器接收安全陷門并和索引進(jìn)行匹配,最后返回相關(guān)加密文件給用戶,用戶在本地進(jìn)行解密,獲得所需文件.
最近,許多研究者提出了一系列的可搜索加密算法.Song等人[4]提出了一種實現(xiàn)密文搜索的可搜索加密算法,但是他的算法只支持單關(guān)鍵詞搜索;Li等人[5]確定了有效模糊關(guān)鍵詞搜索加密數(shù)據(jù)的問題,利用編輯距離和通配符的方法構(gòu)建模糊關(guān)鍵詞集;隨后,Cao等人[6]提出了一種安全的多關(guān)鍵詞可搜索加密算法(multi-keyword ranked search over encrypted cloud data, MRSE),利用空間向量模型和向量內(nèi)積實現(xiàn)高效檢索;Wang等人[7]將局部敏感Hash(locally sensitive Hash, LSH)和布隆過濾器結(jié)合解決了基于多關(guān)鍵詞的模糊搜索問題;沿著這個方向,文獻(xiàn)[8-9]研究者提出了驗證返回結(jié)果正確性的算法.這些算法提出了不同的搜索功能,例如單關(guān)鍵詞搜索、多關(guān)鍵詞搜索和模糊搜索等;除了在功能上多樣化之外,還有一些研究者[10-11]從提高檢索密文文件的效率和準(zhǔn)確性出發(fā)提出了基于TF-IDF算法的可搜索加密算法,并為了節(jié)省傳輸成本只返回top-k個文檔.
雖然上述算法有效解決了可搜索加密問題,但它們也存在一定的局限性.1)現(xiàn)有工作中大多將搜索關(guān)鍵詞視為同等重要,忽略了關(guān)鍵詞的差異性,導(dǎo)致關(guān)鍵詞擴(kuò)展后返回的結(jié)果不能滿足用戶的搜索意圖;2)現(xiàn)有工作沒有考慮索引之間的關(guān)聯(lián)性,關(guān)鍵詞搜索必須遍歷所有索引,使得搜索效率較低.
因此,為了解決上述問題,我們研究了關(guān)鍵詞之間的關(guān)系,提出一種基于語義擴(kuò)展的多關(guān)鍵詞可搜索加密算法(multi-keyword searchable encryption algorithm based on semantic extension, SEMSE),以搜索出滿足用戶意圖的數(shù)據(jù)文檔.此外,在搜索階段,利用凝聚層次聚類和關(guān)鍵詞平衡二叉樹的思想將相似度高的索引聚類在同一個子樹下,從而構(gòu)建了一個新的索引樹結(jié)構(gòu),并通過引入剪枝參數(shù)和相關(guān)性得分閾值對索引樹進(jìn)行剪枝來過濾掉大量不相關(guān)的子樹,從而大大減少了搜索時間.最后,所提算法可抵御2種不同的安全威脅.本文的主要貢獻(xiàn)有3個方面:
1) 考慮不同搜索關(guān)鍵詞之間的關(guān)系,提出一種關(guān)鍵詞權(quán)重算法,以區(qū)分不同搜索關(guān)鍵詞之間的重要性,利用關(guān)鍵詞權(quán)重來選出需要擴(kuò)展的關(guān)鍵詞,而不是查詢中的所有關(guān)鍵詞來進(jìn)行多關(guān)鍵詞排序搜索;
2) 利用凝聚層次聚類和關(guān)鍵詞平衡二叉樹思想將相似索引聚類在同一個子樹下,從而構(gòu)建一種新的索引結(jié)構(gòu).然后設(shè)置剪枝參數(shù)和相關(guān)性得分閾值對索引樹進(jìn)行剪枝來過濾掉大量不相關(guān)的子樹,從而大大減少搜索時間;
3) 應(yīng)用真實數(shù)據(jù)集的實驗表明,與現(xiàn)有算法相比,我們所提的算法在保證隱私的前提下,提高了搜索效率和準(zhǔn)確性.
近些年,可搜索加密算法獲得了長足的發(fā)展,許多算法都在基于文檔的可搜索加密中提供了豐富的搜索功能.此外,可搜索加密算法分為2類:1)非對稱可搜索加密(asymmetric searchable encryption, ASE);2)可搜索對稱加密(searchable symmetric encryption, SSE).這里,我們只關(guān)注后者.
Song等人[4]第1次提出了對稱可搜索加密算法,該算法使用順序掃描密文文檔,這是首次定義了對稱可搜索加密問題并給出了解決算法,對后續(xù)研究起到極大的推動作用.但是,該算法只接收固定長度的關(guān)鍵詞且存儲復(fù)雜度比較高.Goh[12]定義了一種安全索引結(jié)構(gòu),并為自適應(yīng)選擇攻擊的語義安全性建立了一種安全模型;Curtmola等人[13]針對對稱可搜索加密算法給出了安全性定義,并基于倒排索引結(jié)構(gòu)提出了一種新的與文檔相關(guān)聯(lián)的索引結(jié)構(gòu);Cash等人[14]提出了一種新的支持大型數(shù)據(jù)庫的動態(tài)SSE算法;Stefanov等人[15]首次針對動態(tài)搜索加密問題提出了一種在次線性時間進(jìn)行更新和搜索的解決算法,雖然該算法搜索時間是非線性的,但是隨著索引數(shù)量的增加,實際搜索時間還是非常大;通過陷門置換的方式,Bost[16]首次實現(xiàn)了支持前向隱私的可搜索加密算法,并推廣到任意基于索引的SSE算法中;Kim等人[17]提出了一種稱為雙字典的數(shù)據(jù)結(jié)構(gòu),該字典是一種包含前向和倒置索引的鏈接字典.為了實現(xiàn)前向安全性,該算法采用與前向搜索令牌無關(guān)的新密鑰來加密新添加的數(shù)據(jù)文件;文獻(xiàn)[17-18]提出了一些支持前向和后向安全的SSE算法,然而這些算法都支持單關(guān)鍵詞搜索.
Fig. 1 Keyword balanced binary tree圖1 關(guān)鍵詞平衡二叉樹
另一方面,為了豐富搜索表達(dá),大量研究工作集中在設(shè)計多關(guān)鍵詞可搜索加密算法.文獻(xiàn)[19-21]中提出的解決算法著重于如何在提供隱私保護(hù)的同時對加密數(shù)據(jù)進(jìn)行多關(guān)鍵詞聯(lián)合搜索,這些算法的時間開銷和文件集的大小成線性關(guān)系.Cash等人[22]提出了一種具有可擴(kuò)展性的對稱搜索加密算法,該算法將計算開銷減少到子線性,并將搜索模式擴(kuò)展到布爾查詢.Cao等人[6]基于文獻(xiàn)[23]提出的安全kNN技術(shù)解決了支持搜索結(jié)果排序的多關(guān)鍵詞搜索問題,提出了基于向量空間模型和向量內(nèi)積計算的可搜索加密算法,該算法支持2種安全威脅.為了解決多關(guān)鍵詞搜索和搜索結(jié)果排序問題,Sun等人[24]提出了一種基于詞頻的索引和余弦相似度建立的向量空間模型,以提高搜索的準(zhǔn)確性.為了消除預(yù)定義字典的存儲開銷,Wang等人[25]通過在Bloom Filter中使用局部敏感Hash構(gòu)建文件索引,并實現(xiàn)了文件更新,F(xiàn)u等人[26]提出了支持并行計算的加密云數(shù)據(jù)的多關(guān)鍵詞排序搜索算法.Xia等人[27]在文獻(xiàn)[6]的基礎(chǔ)上提出了一種支持多關(guān)鍵詞排序搜索和動態(tài)更新的加密搜索算法,該算法利用向量空間模型和TF-IDF來實現(xiàn)多關(guān)鍵詞排序搜索并構(gòu)建了基于樹的特殊索引結(jié)構(gòu)來降低搜索的時間復(fù)雜度.
在算法中,未考慮搜索關(guān)鍵詞之間的關(guān)系和索引之間的關(guān)聯(lián)性,導(dǎo)致搜索結(jié)果不能滿足用戶需求,搜索的效率還有待改善.
為了安全高效地獲得索引向量和搜索陷門之間的相關(guān)性得分,在2009年Wong等人[23]提出了一種迄今為止使用最廣泛的安全kNN算法.安全kNN的目標(biāo)是將數(shù)據(jù)集中的k個最近點(diǎn)進(jìn)行安全地識別、匹配給定的點(diǎn),而不需要使用服務(wù)器來獲取數(shù)據(jù)集的內(nèi)容.該算法通過計算2個向量之間的向量內(nèi)積來獲得它們之間的相關(guān)性得分.文獻(xiàn)[6]提出了基于安全kNN算法的多關(guān)鍵詞排序搜索加密算法,并給出了安全性證明.在安全kNN算法中,首先,需要設(shè)置一個用來加密向量的安全密鑰(S,M1,M2).其中S是m位的二進(jìn)制向量,由{0,1}組成,用于將向量分割成2部分,M1和M2是2個用于加密向量的可逆矩陣.
2015年Xia等人[27]設(shè)計了一種基于關(guān)鍵詞平衡二叉樹索引結(jié)構(gòu)(keyword balanced binary tree, KBB-Tree)的多關(guān)鍵詞排序搜索算法,并設(shè)計了一種貪婪深度優(yōu)先遍歷算法,其算法的時間復(fù)雜度基本上保持為對數(shù)級,能夠?qū)崿F(xiàn)高效的多關(guān)鍵詞排序搜索.關(guān)鍵詞平衡二叉樹的索引結(jié)構(gòu)采用TF-IDF表示文檔關(guān)鍵詞的權(quán)重值,并采用向量空間模型構(gòu)造一個索引向量,最后通過安全kNN算法進(jìn)行加密計算相關(guān)性得分,從而返回top-k個排序結(jié)果.
如圖1所示為基于關(guān)鍵詞平衡二叉樹的索引結(jié)構(gòu).KBB-Tree的節(jié)點(diǎn)標(biāo)識為u=(ID,I,Pl,Pr,FID).其中,ID表示節(jié)點(diǎn)的唯一編碼;I表示文檔向量;Pl和Pr分別表示節(jié)點(diǎn)u指向左孩子的節(jié)點(diǎn)和指向右孩子的節(jié)點(diǎn);對于FID來說,如果節(jié)點(diǎn)是葉子節(jié)點(diǎn),則FID表示文檔編號,如果節(jié)點(diǎn)是中間節(jié)點(diǎn),則FID為空.在構(gòu)建關(guān)鍵詞平衡二叉樹時,從葉子節(jié)點(diǎn)進(jìn)行構(gòu)建生成中間節(jié)點(diǎn),比較2個葉子節(jié)點(diǎn)中的文檔向量I,將向量中取值較大的值作為中間節(jié)點(diǎn)中I對應(yīng)向量的取值.根據(jù)這一原則逐步構(gòu)建中間節(jié)點(diǎn),直到生成根節(jié)點(diǎn)為止.
其中,N表示索引樹的中間節(jié)點(diǎn),F(xiàn)表示文檔所在的葉子節(jié)點(diǎn),中間節(jié)點(diǎn)的向量值為其左右孩子節(jié)點(diǎn)對應(yīng)位向量的最大值.在搜索過程中,通過基于KBB-Tree的索引結(jié)構(gòu)和貪婪深度優(yōu)先遍歷算法能夠極大地節(jié)省搜索的時間開銷,提高搜索效率.但是當(dāng)輸入關(guān)鍵詞字典中不存在關(guān)鍵詞時,該索引結(jié)構(gòu)會線性地執(zhí)行遍歷操作,致使搜索效率大大降低.
依存句法(dependency grammar)的主要用途是分析句子的句法結(jié)構(gòu),從而更好地理解句子的含義[28].依存句法具有一個一般性的假設(shè),即句法結(jié)構(gòu)本質(zhì)上包含詞和詞的關(guān)系,這種關(guān)系被稱為依存關(guān)系(dependency relations)[29].在依存句法中,能夠準(zhǔn)確識別出關(guān)鍵詞的詞性以及句子中關(guān)鍵詞之間的支配和從屬的關(guān)系,其中屬于支配地位的關(guān)鍵詞稱為支配詞(head),處于被支配地位的關(guān)鍵詞稱為從屬詞(dependency)[28].句子中各關(guān)鍵詞之間的關(guān)系是單向的,并通過語義弧鏈接它們之間的依賴關(guān)系.對于句子中關(guān)鍵詞的依存關(guān)系,需符合4條公理.
1) 句子中有且僅有一個關(guān)鍵詞是獨(dú)立的;
2) 其他關(guān)鍵詞必須依存于另一個關(guān)鍵詞;
3) 任何關(guān)鍵詞不能同時與2個關(guān)鍵詞之間存在依存關(guān)系;
4) 如果2個關(guān)鍵詞A和B之間存在依存關(guān)系,而這2個關(guān)鍵詞之間還有其他關(guān)鍵詞C,則該關(guān)鍵詞C只能依存于關(guān)鍵詞A或B,或者依存于A和B之間的其他關(guān)鍵詞.
與短語結(jié)構(gòu)句法不同,依存句法中不存在短語節(jié)點(diǎn),只考慮句子各成分之間的依賴關(guān)系,如圖2所示為以“Information security is very important”為例的依存句法結(jié)構(gòu)依賴關(guān)系圖.
Fig. 2 Dependency grammar structure圖2 依存句法結(jié)構(gòu)
其中,root表示根節(jié)點(diǎn)關(guān)系,compound表示補(bǔ)語關(guān)系,nsubj表示名詞主語關(guān)系,cop表示系動詞關(guān)系,advmod表示狀語關(guān)系.
如圖3所示,本系統(tǒng)模型主要分為3個不同實體:數(shù)據(jù)擁有者、數(shù)據(jù)使用者和云服務(wù)器.
1) 數(shù)據(jù)擁有者.在數(shù)據(jù)文檔F={F1,F2,…,Fn}外包給云服務(wù)器之前,首先對數(shù)據(jù)文件提取關(guān)鍵詞W={w1,w2,…,wm} 并采用安全密鑰SK加密關(guān)鍵詞構(gòu)建安全索引I={I1,I2,…,Im}.然后,采用對稱加密算法加密數(shù)據(jù)文檔生成加密數(shù)據(jù)集C={c1,c2,…,cn}.最后,將加密數(shù)據(jù)集C和安全索引I一同上傳至云服務(wù)器并將對稱密鑰sk和安全密鑰SK發(fā)送給數(shù)據(jù)使用者.
2) 數(shù)據(jù)使用者.首先,接收從數(shù)據(jù)擁有者發(fā)送的對稱密鑰和安全密鑰;然后,在本地輸入一定的關(guān)鍵詞進(jìn)行搜索,使用安全密鑰生成安全陷門T并將安全陷門T發(fā)送給云服務(wù)器;最后,獲取云服務(wù)器返回的加密數(shù)據(jù)文件,并利用對稱密鑰進(jìn)行解密.
3) 云服務(wù)器.云服務(wù)器存儲數(shù)據(jù)擁有者發(fā)送的加密數(shù)據(jù)集和安全索引,并為數(shù)據(jù)使用者提供數(shù)據(jù)搜索服務(wù)等.當(dāng)數(shù)據(jù)使用者發(fā)送安全陷門給云服務(wù)器時,云服務(wù)器利用指定算法將安全陷門和安全索引進(jìn)行匹配,并返回top-k個密文給數(shù)據(jù)使用者.
Fig. 3 System model圖3 系統(tǒng)模型
為了便于描述多關(guān)鍵詞可搜索加密算法,表1給出本文使用到的符號定義.
Table 1 Symbol Definition表1 符號定義
系統(tǒng)模型包括5個多項式時間算法SSE={KeyGen,BuildIndex,TrapdoorGen,Search,Decrypt},具體過程為:
1) 初始化KenGen(1λ)→(SK,sk).是一個由數(shù)據(jù)擁有者執(zhí)行的概率密鑰生成算法,該算法將安全參數(shù)λ作為輸入,然后輸出密鑰SK={S,M1,M2}和對稱密鑰sk.
2) 索引構(gòu)建BuildIndex(sk,SK,F)→(I,C).是一個概率算法,將密鑰SK和外包文檔集F作為輸入,對文檔集進(jìn)行關(guān)鍵詞提取,生成關(guān)鍵詞字典W,并構(gòu)建關(guān)鍵詞索引,然后使用密鑰SK加密索引向量和使用對稱密鑰sk加密文檔集F.算法輸出安全索引I和密文集C.
3) 陷門生成TrapdoorGen(Wq,SK)→T.是一個概率算法,該算法將密鑰SK和搜索關(guān)鍵詞Wq作為輸入,利用密鑰SK對搜索關(guān)鍵詞進(jìn)行加密生成安全陷門T,算法返回安全陷門T.
4) 搜索Search(I,T,k)→Ck.是一個由云服務(wù)器執(zhí)行的確定性算法,該算法將安全索引I、安全陷門T和需要返回文檔的個數(shù)k作為輸入,計算安全陷門和安全索引的向量內(nèi)積作為相關(guān)性得分,并對相關(guān)性得分進(jìn)行排序.云服務(wù)器返回包含top-k個密文的文檔集Ck給數(shù)據(jù)使用者.
5) 解密Decrypt(Ck,sk)→Fk.是一個確定性算法,該算法將密文文檔Ck和密鑰sk作為輸入,數(shù)據(jù)使用者通過對稱密鑰sk對加密文檔集Ck進(jìn)行解密,算法返回明文數(shù)據(jù)集Fk.
采用文獻(xiàn)[6,25,27]中提出的安全威脅,假設(shè)數(shù)據(jù)擁有者和數(shù)據(jù)使用者是可靠的,而云服務(wù)器是“誠實且好奇的”,即它會“誠實地”根據(jù)算法的指定協(xié)議存儲數(shù)據(jù)擁有者的數(shù)據(jù)文檔,但對存儲的數(shù)據(jù)“感到好奇”,即云服務(wù)器想通過推斷或分析加密數(shù)據(jù)和安全陷門信息來獲取數(shù)據(jù)所有者的數(shù)據(jù)信息.
2) 已知背景模型.在已知背景模型中,云服務(wù)器能夠獲取比已知密文模型更多的數(shù)據(jù)信息,比如與安全陷門相關(guān)的信息或者數(shù)據(jù)集之間的統(tǒng)計信息等.因此,云服務(wù)器具有更強(qiáng)的攻擊能力.云服務(wù)器可以根據(jù)已知的陷門信息,并借助一些統(tǒng)計信息來推斷,分析上傳的安全陷門、安全索引和搜索結(jié)果等來確定搜索中的某些關(guān)鍵詞的明文信息.
1) 現(xiàn)有的算法都是將搜索關(guān)鍵詞彼此之間視為同等重要,忽略了關(guān)鍵詞的重要性的不同,導(dǎo)致關(guān)鍵詞擴(kuò)展后搜索準(zhǔn)確率較低.
2) 現(xiàn)有多關(guān)鍵詞可搜索加密算法在構(gòu)建索引的過程中沒有考慮索引之間的關(guān)聯(lián)性,關(guān)鍵詞搜索必須遍歷所有索引,使得搜索效率較低.
本文提出一種多關(guān)鍵詞陷門生成方法,以區(qū)分不同關(guān)鍵詞權(quán)重,然后詳細(xì)描述了多關(guān)鍵詞排序搜索過程,最后給出了SEMRS算法的具體實現(xiàn).
1) 關(guān)鍵詞權(quán)重計算
用戶進(jìn)行搜索時,輸入的關(guān)鍵詞存在一定的句法關(guān)系,即關(guān)鍵詞之間存在修飾和被修飾的關(guān)系.因此,關(guān)鍵詞之間的句法關(guān)系一定程度上反映出關(guān)鍵詞的重要性.此外,如果一個關(guān)鍵詞和不止一個關(guān)鍵詞之間具有句法關(guān)系,則該關(guān)鍵詞具有更大的重要性.
因此,將搜索關(guān)鍵詞之間的句法關(guān)系視為關(guān)鍵詞重要性的表現(xiàn)形式.對搜索關(guān)鍵詞之間的句法關(guān)系進(jìn)行分析,如果存在句法關(guān)系,則增加關(guān)鍵詞權(quán)重.
定義1.關(guān)鍵詞關(guān)系.對于每個關(guān)鍵詞來說,設(shè)初始關(guān)鍵詞關(guān)系為1,如果該關(guān)鍵詞和其他關(guān)鍵詞之間具有句法關(guān)系,則其權(quán)重變?yōu)?+R,其中R表示2個關(guān)鍵詞之間的句法關(guān)系.
(1)
Fig. 4 Keyword phrase structure tree圖4 關(guān)鍵詞短語結(jié)構(gòu)樹
然后將結(jié)構(gòu)樹轉(zhuǎn)換為依存句法結(jié)構(gòu),獲取關(guān)鍵詞之間的句法關(guān)系,如圖5所示:
Fig. 5 Keyword dependence relations圖5 關(guān)鍵詞句法關(guān)系
其中,“root”表示依存句法結(jié)構(gòu)的根節(jié)點(diǎn)關(guān)系,“amod”表示形容詞修飾語,“compound”表示名詞復(fù)合修飾語,“dep”表示依賴關(guān)系,“NP”表示名詞短語,“NN”表示常用名詞單數(shù)形式,“JJ”表示形容詞、數(shù)字和序號等.我們采用關(guān)鍵詞之間的句法關(guān)系和短語結(jié)構(gòu)樹中關(guān)鍵詞之間的距離來衡量關(guān)鍵詞的權(quán)重,例如“encryption”和“multiple”的距離為5,則它們之間的句法關(guān)系為R(amod)=1ln 5.根據(jù)上述規(guī)則,可以得出總的關(guān)鍵詞關(guān)系為4+1ln 4+1ln 4+1ln 4+1ln 5=6.785,而“multiple”的關(guān)系為1+1ln 4+35ln 5=2.094,然后利用關(guān)鍵詞權(quán)重式(1)可知,“multiple”的關(guān)鍵詞權(quán)重為KW(multiple)=1.23.同理,其他關(guān)鍵詞的權(quán)重分別為KW(search)=0.81,KW(keyword)=1.01,KW(encryption)=0.95.
2) 多關(guān)鍵詞的語義擴(kuò)展
對關(guān)鍵詞進(jìn)行擴(kuò)展,不是對所有關(guān)鍵詞進(jìn)行擴(kuò)展,而是通過關(guān)鍵詞權(quán)重計算方法選出權(quán)重最大的關(guān)鍵詞作為待擴(kuò)展關(guān)鍵詞,然后根據(jù)WordNet[31]獲取關(guān)鍵詞的同義詞,這樣對于每個待擴(kuò)展的關(guān)鍵詞都構(gòu)建了一個同義詞集,最后通過2個關(guān)鍵詞概念之間的最大語義相似度近似2個關(guān)鍵詞的語義相似度,即:
(2)
其中,S(wi),S(wj)是關(guān)鍵詞wi和wj所包含概念的集合.這里,采用基于信息內(nèi)容(IC)的David算法[32]來衡量2個概念之間的相似度.
3) 陷門生成
為了更好地反映關(guān)鍵詞和文檔的關(guān)系,在關(guān)鍵詞權(quán)重中引入了TF-IDF技術(shù),對于每個文檔關(guān)鍵詞w,如果其在關(guān)鍵詞詞典中,則將關(guān)鍵詞權(quán)重設(shè)置為關(guān)鍵詞權(quán)重值和該關(guān)鍵詞在文檔中的逆文本頻率IDF的乘積,即KW×IDF,代替基于原關(guān)鍵詞權(quán)重值,將擴(kuò)展關(guān)鍵詞的權(quán)重值設(shè)置為其語義相似度得分、對應(yīng)的搜索關(guān)鍵詞的權(quán)重和逆文本頻率IDF三者的乘積,即KW×sim×IDF.
1) 基于凝聚層次聚類的索引構(gòu)建
Fig. 6 Index tree construction process圖6 索引樹構(gòu)建過程
在對文檔加密之前,需要構(gòu)建文檔的索引,Xia等人[27]提出了基于KBB-Tree的索引結(jié)構(gòu),相比于線性掃描的MRSE算法[6],通過構(gòu)建索引樹的方式確實大幅提升了搜索效率,但是該算法沒有考慮索引之間的關(guān)聯(lián)性,使得相似度高的索引隨機(jī)分布在索引樹的各個子樹中,導(dǎo)致多關(guān)鍵詞搜索必須遍歷所有索引才能最終確定搜索結(jié)果.因此,基于凝聚層次聚類(agglomerative hierarchical clustering)[32]的思想將相似索引進(jìn)行聚類為一個平衡二叉樹索引結(jié)構(gòu).凝聚層次聚類通常是指將每個對象都作為一個單獨(dú)的聚類簇,然后每一次聚類最相關(guān)的2個簇,直至將所有簇聚類為一個簇為止.由于每次僅聚類2個最相關(guān)的簇,使得構(gòu)成樹的高度非常大,不利于遍歷整棵樹.因此,在每一輪的聚類操作中,根據(jù)簇集合中簇中心向量的歐幾里德距離兩兩合并,從而構(gòu)成平衡二叉樹形式,其中簇中心向量指簇集合中各節(jié)點(diǎn)的均值,如圖6所示為索引樹構(gòu)建過程.為了便于描述索引樹的構(gòu)建,先給出了索引樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu).
定義2.索引樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu).設(shè)索引樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)由四元組FID,NV,NL,NR組成.其中,FID表示文檔的唯一標(biāo)識符,NV表示該節(jié)點(diǎn)的節(jié)點(diǎn)向量,NL表示該節(jié)點(diǎn)的左孩子,NR表示該節(jié)點(diǎn)的右孩子.如果節(jié)點(diǎn)u是葉子節(jié)點(diǎn),則FID是文檔的唯一標(biāo)識,NV是文檔的索引向量,NL和NR為空;如果節(jié)點(diǎn)u是中間節(jié)點(diǎn),則FID為空,NL和NR表示節(jié)點(diǎn)的左孩子和右孩子,左孩子NL和右孩子NR的簇向量最大值為
NVi=max{NL.NVi,NR.NVi}.
(3)
如圖6所示為索引樹構(gòu)建過程,索引樹的構(gòu)建的基本思想是:首先,根據(jù)定義4索引樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu),創(chuàng)建葉子節(jié)點(diǎn);然后根據(jù)凝聚層次聚類生成中間節(jié)點(diǎn)直至根節(jié)點(diǎn),具體過程為:
假設(shè)8個文檔向量{F1,F2,…,F8},根據(jù)定義4構(gòu)建索引樹的葉子節(jié)點(diǎn){u4,1,u4,2,…,u4,8},SV表示簇中心,N表示節(jié)點(diǎn)u包含的節(jié)點(diǎn)個數(shù),則簇中心為
(4)
(1) 計算葉子節(jié)點(diǎn)簇中心之間的歐幾里德距離為
(5)
將歐幾里德距離最小的2個節(jié)點(diǎn)進(jìn)行聚類生成一個簇,該節(jié)點(diǎn)的節(jié)點(diǎn)向量NV的計算如式(3),簇中心的計算如式(4).然后再計算剩余節(jié)點(diǎn)簇中心的歐幾里德距離,并聚類最小的2個簇,直至聚類所有節(jié)點(diǎn).聚類后的簇為Cu3,1={F2,F4},Cu3,2={F5,F7},Cu3,3={F1,F3}和Cu3,4={F6,F8}.
(2) 根據(jù)步驟1的過程,依次對階段1生成的簇進(jìn)行聚類,聚類之后的簇為Cu2,1={F2,F4,F5,F7}和Cu2,2={F1,F3,F6,F8}.
(3) 根據(jù)步驟2的過程,對階段2生成的簇進(jìn)行聚類,生成索引樹的根節(jié)點(diǎn).
2) 多關(guān)鍵詞的排序搜索
由于通過凝聚層次聚類構(gòu)建索引樹使得相關(guān)的索引位于同一個子樹中,在索引遍歷過程中只需根據(jù)搜索關(guān)鍵詞和索引的相關(guān)性得分找出對應(yīng)的簇就能實現(xiàn)整個遍歷過程,而無需遍歷整個索引樹.因此,設(shè)置一個剪枝參數(shù)PT和一個相關(guān)性得分閾值sysp來過濾不相關(guān)的子樹,其中剪枝參數(shù)可以根據(jù)用戶不同偏好設(shè)置,相關(guān)性得分閾值是結(jié)果集中相關(guān)性得分最小的取值.通過索引樹的構(gòu)建可知,中間節(jié)點(diǎn)的節(jié)點(diǎn)向量是該節(jié)點(diǎn)的左孩子和右孩子的節(jié)點(diǎn)向量的最大值,即如果中間節(jié)點(diǎn)的節(jié)點(diǎn)向量和搜索關(guān)鍵詞的相關(guān)性得分小于剪枝參數(shù)PT和相關(guān)性得分閾值sysp,則以該節(jié)點(diǎn)為根節(jié)點(diǎn)的索引樹的所有節(jié)點(diǎn)與搜索關(guān)鍵詞的相關(guān)性得分都小于剪枝參數(shù)PT和相關(guān)性得分閾值sysp,對該索引樹進(jìn)行剪枝.
如圖7所示為關(guān)鍵詞搜索過程,設(shè)索引樹包含8個文檔,返回的文檔個數(shù)為5,搜索向量為Q=(0.3,0.6,0,0.1),關(guān)鍵詞搜索路徑為虛線箭頭所指方向.首先,搜索葉子節(jié)點(diǎn)u4,1,并計算搜索向量Q和葉子節(jié)點(diǎn)簇向量的相關(guān)性得分.然后判斷相關(guān)性得分Score(Q,u4,1.NV) 是否大于剪枝參數(shù)PT,如果大于剪枝參數(shù),則F2插入結(jié)果集中.繼續(xù)遍歷葉子節(jié)點(diǎn)u4,2,相關(guān)性得分Score(Q,u4,1.NV)>PT,將F4插入結(jié)果集Rlist中.繼續(xù)遍歷其他子樹,當(dāng)結(jié)果集Rlist={u4,1,u4,2,u4,3,u4,4}時,結(jié)果集中節(jié)點(diǎn)個數(shù)為4,小于需要返回的文檔數(shù),繼續(xù)判斷剩余節(jié)點(diǎn)得出Score(Q,u4,1.NV) Fig. 7 Keyword search圖7 關(guān)鍵詞搜索過程 由于剪枝參數(shù)和相關(guān)性得分閾值的設(shè)置并沒有返回數(shù)據(jù)使用者想要返回的5個文檔而是返回了最為相關(guān)的4個文檔,且在進(jìn)行關(guān)鍵詞搜索過程中并沒有遍歷所有節(jié)點(diǎn),而是對于中間節(jié)點(diǎn)的相關(guān)性得分較小的子樹進(jìn)行剪枝,這樣極大地節(jié)省了遍歷時間. 本節(jié)基于語義擴(kuò)展的多關(guān)鍵詞排序搜索算法主要包括6個部分:GenKey,BuildIndexTree,Query-Extension,GenTrapdoor,Search和Decrypt. 1) 初始化GenKey(k)→(SK,sk) 3) 關(guān)鍵詞擴(kuò)展QueryExtension→We 首先,根據(jù)關(guān)鍵詞權(quán)重計算方法計算搜索關(guān)鍵詞Wq的權(quán)重,并選出需要擴(kuò)展的關(guān)鍵詞.然后,根據(jù)基于語義相似度的關(guān)鍵詞擴(kuò)展算法提取關(guān)鍵詞的同義詞集,將關(guān)鍵詞轉(zhuǎn)換為概念,并構(gòu)建概念層次樹,計算關(guān)鍵詞之間的語義相似度.最后,選出相似度最大的若干關(guān)鍵詞作為擴(kuò)展關(guān)鍵詞,并將擴(kuò)展關(guān)鍵詞和搜索關(guān)鍵詞一起作為搜索關(guān)鍵詞We. Score=·=(MT1I′)TM-11Q′+ 6) 解密Decrypt(C,sk)→F 數(shù)據(jù)使用者接收到云服務(wù)器返回的密文文件,使用對稱密鑰sk對密文文件C進(jìn)行解密來恢復(fù)原文件的內(nèi)容. 基于語義擴(kuò)展的多關(guān)鍵詞排序搜索算法具體如算法1所示. 算法1.SEMRS算法. 輸入:剪枝閾值PT、相關(guān)性得分閾值sysn、需要返回的文檔個數(shù)k; 輸出:明文F. ① 初始化密鑰參數(shù)x; ②SK,sk←Getkey(x); ③ fori=1;i≤n;i++ do ④u←createNode(Fi,SK); ⑥ end for ⑦We←queryExtension(Q); ⑨ for the nodeudo 在算法1中,行①是生成密鑰的過程,行②~⑤是構(gòu)建索引的過程,行⑥~⑦是生成安全陷門,行⑧~是多關(guān)鍵詞搜索,如果中間節(jié)點(diǎn)的相關(guān)性得分小于剪枝參數(shù)和得分閾值,則進(jìn)行剪枝,行~是對服務(wù)器返回的結(jié)果集進(jìn)行解密. 本節(jié)將分別從已知密文模型和已知背景模型來分析所提算法的安全性. 1) 已知密文模型中的安全性 (7) 其中,Ip包含2×n×|Ip|個未知數(shù),可逆矩陣M1和M2分別包含n×n個未知數(shù).通過式(7)可以得出方程組中僅包含2×n×|Ip|個方程式.根據(jù)行列式的性質(zhì)可知,當(dāng)未知數(shù)的數(shù)量大于方程式的數(shù)量時,不能計算出方程式的解,即根據(jù)式(7)得不到可逆矩陣M1和M2.同理,通過安全陷門也得不到可逆矩陣M1和M2.因此,本算法采用的拆分索引和搜索向量的加密機(jī)制能夠保證數(shù)據(jù)的隱私性. 2) 已知背景模型中的安全性 在已知背景模型中,數(shù)據(jù)加密和索引及陷門的加密使用的是相同的加密方法.此外,在已知背景模型中引入了虛擬關(guān)鍵詞.因此,SEMRS算法保證了數(shù)據(jù)的安全性與索引和陷門的安全性. 為了進(jìn)一步驗證算法的性能,本節(jié)分別從算法的各主要階段:1)系統(tǒng)初始化;2)索引構(gòu)建;3)陷門生成;4)搜索等方面進(jìn)行分析.假設(shè)加密算法采用傳統(tǒng)的對稱加密算法,文檔關(guān)鍵詞的數(shù)量為n,文檔集中包含文檔的個數(shù)為m,搜索關(guān)鍵詞個數(shù)為x,擴(kuò)展的關(guān)鍵詞個數(shù)為y,分析: 系統(tǒng)初始化階段,僅進(jìn)行密鑰生成,因此該階段的時間復(fù)雜度為O(1). 索引構(gòu)建階段,主要時間消耗為索引加密,先采用的安全kNN算法對索引進(jìn)行分割,然后使用2個可逆矩陣相乘進(jìn)行加密,其安全索引構(gòu)建的時間復(fù)雜度為O(me2),其中e是關(guān)鍵詞向量的長度. 陷門生成階段,安全陷門的生成與安全索引構(gòu)建過程相似,主要時間消耗都是關(guān)鍵詞加密和關(guān)鍵詞擴(kuò)展,其時間復(fù)雜度也是O((x+y)e2). 此外,由于擴(kuò)展關(guān)鍵詞個數(shù)y應(yīng)小于搜索關(guān)鍵詞個數(shù)x,且x+y?m.在陷門生成時,無論搜索關(guān)鍵詞集合中有多少關(guān)鍵詞,陷門長度始終等于所提取文檔關(guān)鍵詞字典長度.算法主要的網(wǎng)絡(luò)通信開銷是傳輸安全陷門T到云服務(wù)器的開銷,由于在本地?zé)o論輸入多少關(guān)鍵詞,使用安全密鑰生成陷門T的大小|T|始終是固定的,因此,即使面對大規(guī)模數(shù)據(jù)集合,陷門傳輸?shù)耐ㄐ砰_銷始終為|T|. 實驗采用Java語言編寫,并在AMD5 CPU 2.0 GHz的Windows 10環(huán)境執(zhí)行.數(shù)據(jù)集為聯(lián)邦能源監(jiān)管委員會發(fā)布的包含517 000多條郵件的Enron email dataset[33]. 為了表現(xiàn)擴(kuò)展關(guān)鍵詞數(shù)量的影響,設(shè)擴(kuò)展關(guān)鍵詞和原搜索關(guān)鍵詞之間的比率參數(shù)為ρ,其中ρ∈[0,1].即最少關(guān)鍵詞擴(kuò)展數(shù)量為0,最多關(guān)鍵詞擴(kuò)展為原關(guān)鍵詞的個數(shù).如圖8(a)所示,橫坐標(biāo)為擴(kuò)展關(guān)鍵詞和原搜索關(guān)鍵詞之間的比率參數(shù)ρ,步長為0.1,縱坐標(biāo)為搜索準(zhǔn)確率.設(shè)返回的文檔數(shù)為50,數(shù)據(jù)使用者搜索相關(guān)的文檔數(shù)量為80,則從圖8(a)中,可以得出隨著比率參數(shù)ρ的增加,搜索準(zhǔn)確率逐漸上升,直至比率參數(shù)為0.4時,準(zhǔn)確率和召回率達(dá)到最大值,隨后準(zhǔn)確率和召回率開始逐漸降低,即在基于多關(guān)鍵詞擴(kuò)展的排序搜索算法中當(dāng)比率參數(shù)為0.4時,搜索性能達(dá)到最優(yōu). Fig. 8 Accuracy and recall圖8 準(zhǔn)確率和召回率 圖8(b)所示為隨著搜索關(guān)鍵詞的變化,準(zhǔn)確率和召回率的變化趨勢.隨著搜索關(guān)鍵詞的不斷增加,SEMRS的準(zhǔn)確率和召回率也不斷提高,即搜索關(guān)鍵詞的數(shù)量越多,則搜索結(jié)果越能夠滿足需求. Fig. 9 Precision change under standard deviation圖9 在不標(biāo)準(zhǔn)差下準(zhǔn)確率變化趨勢 Fig. 10 Index building time comparison圖10 索引構(gòu)建時間比較 索引構(gòu)建階段主要執(zhí)行索引構(gòu)建和索引加密.其中索引構(gòu)建的計算成本主要取決于數(shù)據(jù)集中的文檔個數(shù),而索引加密又與關(guān)鍵詞字典包含的關(guān)鍵詞數(shù)量有關(guān).此外,索引構(gòu)建過程是一個一次性過程,即只在初始階段進(jìn)行索引構(gòu)建,除非后續(xù)對數(shù)據(jù)集進(jìn)行了更新操作,才重新構(gòu)建索引.圖10(a)顯示了本算法和EDMRS算法[27]在給定不同文檔數(shù)量情況下,索引構(gòu)建時間開銷的變化趨勢.由于關(guān)鍵詞數(shù)量越大,則索引向量的維度也就越大,因此通過觀察可以發(fā)現(xiàn),隨著關(guān)鍵詞數(shù)量的增加,索引構(gòu)建時間也越來越大.圖10(b)為在給定關(guān)鍵詞數(shù)量的情況下,索引構(gòu)建時間隨著文檔數(shù)量的變化趨勢.隨著文檔數(shù)量的不斷增加,索引構(gòu)建時間也在增加,但SEMRS采用將索引向量分塊的方式減少計算復(fù)雜性,大大減少了索引加密時間和索引創(chuàng)建時間. Fig. 11 Trapdoor generation time圖11 陷門生成時間 陷門生成是關(guān)鍵詞搜索的重要步驟,如圖11所示為陷門生成關(guān)鍵詞數(shù)量的變化趨勢.不難發(fā)現(xiàn),陷門生成時間趨向于一個常數(shù),不會隨著搜索關(guān)鍵詞的數(shù)量增長而增長,這是因為陷門生成時間主要取決于字典中關(guān)鍵詞的數(shù)量,算法中陷門生成操作的主要耗時是搜索向量的加密.由于本文采用分塊的方式加密搜索向量,因此總的陷門生成時間要小于MRSE算法和EDMRS算法的時間.通過圖11(b)可以看出,生成陷門的時間成本主要取決于關(guān)鍵詞字典中包含的關(guān)鍵詞數(shù)量,并隨著關(guān)鍵詞數(shù)量的增大而變大. 搜索時間是權(quán)衡算法性能的重要指標(biāo).圖12(a)所示為在給定文檔關(guān)鍵詞數(shù)量的情況下,搜索時間隨文檔個數(shù)的變化趨勢,由于文檔向量和索引向量的計算時間相同,因此,搜索時間隨文檔數(shù)量的增加而增加.圖12(b)為給定文檔數(shù)量的情況下,搜索時間隨文檔關(guān)鍵詞數(shù)量的變化趨勢,通過上文可知,文檔關(guān)鍵詞數(shù)量越大,則索引向量和陷門向量的維度也越大,因此,隨著文檔關(guān)鍵詞數(shù)量的增加,搜索時間也越來越多.此外,SEMRS算法基于凝聚層次聚類構(gòu)建索引樹結(jié)構(gòu),該索引樹是平衡二叉樹,并設(shè)計了一種高效的索引遍歷算法,因此,SEMRS的搜索時間要小于MRSE和EDMRS算法的搜索時間. Fig. 12 Search time圖12 搜索時間 在分析查詢關(guān)鍵詞之間的關(guān)系基礎(chǔ)上,提出了一種安全高效的支持語義擴(kuò)展的多關(guān)鍵詞排序搜索算法,解決可搜索加密中的語義檢索問題.我們設(shè)計了一種基于語義關(guān)系的關(guān)鍵詞權(quán)重算法,并對權(quán)重較大的關(guān)鍵詞進(jìn)行語義擴(kuò)展.為提高查詢效率,構(gòu)造了一種關(guān)鍵詞平衡二叉樹作為文檔的索引結(jié)構(gòu),并在查詢時,根據(jù)查詢向量和樹節(jié)點(diǎn)的向量內(nèi)積,進(jìn)行“剪枝”操作.此外,為更好地表達(dá)查詢關(guān)鍵詞和文檔之間的相關(guān)性,在構(gòu)建索引和陷門時引入了TF-IDF算法,并在陷門中加入關(guān)鍵詞權(quán)重值.最后,通過使用安全kNN,使得所提算法能夠?qū)?種不同安全威脅.4.3 算法具體實現(xiàn)
(MT2I″)TM-12Q″=I′Q′+I″Q″=
(I′,I″)(Q′,Q″)=rI·Q+Σεvi5 安全性和性能分析
5.1 安全性分析
5.2 性能分析
6 實驗分析
6.1 準(zhǔn)確率和召回率
6.2 索引創(chuàng)建時間
6.3 陷門生成時間
6.4 搜索時間
7 總 結(jié)