基于語義擴(kuò)展的多關(guān)鍵詞可搜索加密算法

徐光偉 史春紅 王文濤 潘 喬 李 鋒

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620)

現(xiàn)今，云存儲給數(shù)據(jù)用戶(個(gè)人和企業(yè))提供了一個(gè)第三方服務(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í)，數(shù)據(jù)使用者輸入相關(guān)關(guān)鍵詞并使用相應(yīng)的加密算法進(jìn)行加密生成安全陷門，然后將安全陷門發(fā)送給云服務(wù)器，云服務(wù)器接收安全陷門并和索引進(jìn)行匹配，最后返回相關(guān)加密文件給用戶，用戶在本地進(jìn)行解密，獲得所需文件.

最近，許多研究者提出了一系列的可搜索加密算法.Song等人[4]提出了一種實(shí)現(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)積實(shí)現(xiàn)高效檢索;Wang等人[7]將局部敏感Hash(locally sensitive Hash， LSH)和布隆過濾器結(jié)合解決了基于多關(guān)鍵詞的模糊搜索問題;沿著這個(gè)方向，文獻(xiàn)[8-9]研究者提出了驗(yàn)證返回結(jié)果正確性的算法.這些算法提出了不同的搜索功能，例如單關(guān)鍵詞搜索、多關(guān)鍵詞搜索和模糊搜索等；除了在功能上多樣化之外，還有一些研究者[10-11]從提高檢索密文文件的效率和準(zhǔn)確性出發(fā)提出了基于TF-IDF算法的可搜索加密算法，并為了節(jié)省傳輸成本只返回top-k個(gè)文檔.

雖然上述算法有效解決了可搜索加密問題，但它們也存在一定的局限性.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è)子樹下，從而構(gòu)建了一個(gè)新的索引樹結(jié)構(gòu)，并通過引入剪枝參數(shù)和相關(guān)性得分閾值對索引樹進(jìn)行剪枝來過濾掉大量不相關(guān)的子樹，從而大大減少了搜索時(shí)間.最后，所提算法可抵御2種不同的安全威脅.本文的主要貢獻(xiàn)有3個(gè)方面:

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è)子樹下，從而構(gòu)建一種新的索引結(jié)構(gòu).然后設(shè)置剪枝參數(shù)和相關(guān)性得分閾值對索引樹進(jìn)行剪枝來過濾掉大量不相關(guān)的子樹，從而大大減少搜索時(shí)間；

3) 應(yīng)用真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)表明，與現(xiàn)有算法相比，我們所提的算法在保證隱私的前提下，提高了搜索效率和準(zhǔn)確性.

1 相關(guān)工作

近些年，可搜索加密算法獲得了長足的發(fā)展，許多算法都在基于文檔的可搜索加密中提供了豐富的搜索功能.此外，可搜索加密算法分為2類：1)非對稱可搜索加密(asymmetric searchable encryption, ASE);2)可搜索對稱加密(searchable symmetric encryption， SSE).這里，我們只關(guān)注后者.

Song等人[4]第1次提出了對稱可搜索加密算法，該算法使用順序掃描密文文檔，這是首次定義了對稱可搜索加密問題并給出了解決算法，對后續(xù)研究起到極大的推動(dòng)作用.但是，該算法只接收固定長度的關(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ù)庫的動(dòng)態(tài)SSE算法;Stefanov等人[15]首次針對動(dòng)態(tài)搜索加密問題提出了一種在次線性時(shí)間進(jìn)行更新和搜索的解決算法，雖然該算法搜索時(shí)間是非線性的，但是隨著索引數(shù)量的增加，實(shí)際搜索時(shí)間還是非常大;通過陷門置換的方式，Bost[16]首次實(shí)現(xiàn)了支持前向隱私的可搜索加密算法，并推廣到任意基于索引的SSE算法中;Kim等人[17]提出了一種稱為雙字典的數(shù)據(jù)結(jié)構(gòu)，該字典是一種包含前向和倒置索引的鏈接字典.為了實(shí)現(xiàn)前向安全性，該算法采用與前向搜索令牌無關(guān)的新密鑰來加密新添加的數(shù)據(jù)文件;文獻(xiàn)[17-18]提出了一些支持前向和后向安全的SSE算法，然而這些算法都支持單關(guān)鍵詞搜索.

Fig. 1 Keyword balanced binary tree圖1 關(guān)鍵詞平衡二叉樹

另一方面，為了豐富搜索表達(dá)，大量研究工作集中在設(shè)計(jì)多關(guān)鍵詞可搜索加密算法.文獻(xiàn)[19-21]中提出的解決算法著重于如何在提供隱私保護(hù)的同時(shí)對加密數(shù)據(jù)進(jìn)行多關(guān)鍵詞聯(lián)合搜索，這些算法的時(shí)間開銷和文件集的大小成線性關(guān)系.Cash等人[22]提出了一種具有可擴(kuò)展性的對稱搜索加密算法，該算法將計(jì)算開銷減少到子線性，并將搜索模式擴(kuò)展到布爾查詢.Cao等人[6]基于文獻(xiàn)[23]提出的安全kNN技術(shù)解決了支持搜索結(jié)果排序的多關(guān)鍵詞搜索問題，提出了基于向量空間模型和向量內(nèi)積計(jì)算的可搜索加密算法，該算法支持2種安全威脅.為了解決多關(guān)鍵詞搜索和搜索結(jié)果排序問題，Sun等人[24]提出了一種基于詞頻的索引和余弦相似度建立的向量空間模型，以提高搜索的準(zhǔn)確性.為了消除預(yù)定義字典的存儲開銷，Wang等人[25]通過在Bloom Filter中使用局部敏感Hash構(gòu)建文件索引，并實(shí)現(xiàn)了文件更新，F(xiàn)u等人[26]提出了支持并行計(jì)算的加密云數(shù)據(jù)的多關(guān)鍵詞排序搜索算法.Xia等人[27]在文獻(xiàn)[6]的基礎(chǔ)上提出了一種支持多關(guān)鍵詞排序搜索和動(dòng)態(tài)更新的加密搜索算法，該算法利用向量空間模型和TF-IDF來實(shí)現(xiàn)多關(guān)鍵詞排序搜索并構(gòu)建了基于樹的特殊索引結(jié)構(gòu)來降低搜索的時(shí)間復(fù)雜度.

在算法中，未考慮搜索關(guān)鍵詞之間的關(guān)系和索引之間的關(guān)聯(lián)性，導(dǎo)致搜索結(jié)果不能滿足用戶需求，搜索的效率還有待改善.

2 預(yù)備知識

2.1 安全kNN

為了安全高效地獲得索引向量和搜索陷門之間的相關(guān)性得分，在2009年Wong等人[23]提出了一種迄今為止使用最廣泛的安全kNN算法.安全kNN的目標(biāo)是將數(shù)據(jù)集中的k個(gè)最近點(diǎn)進(jìn)行安全地識別、匹配給定的點(diǎn)，而不需要使用服務(wù)器來獲取數(shù)據(jù)集的內(nèi)容.該算法通過計(jì)算2個(gè)向量之間的向量內(nèi)積來獲得它們之間的相關(guān)性得分.文獻(xiàn)[6]提出了基于安全kNN算法的多關(guān)鍵詞排序搜索加密算法，并給出了安全性證明.在安全kNN算法中，首先，需要設(shè)置一個(gè)用來加密向量的安全密鑰(S,M1,M2).其中S是m位的二進(jìn)制向量，由{0，1}組成，用于將向量分割成2部分，M1和M2是2個(gè)用于加密向量的可逆矩陣.

2.2 關(guān)鍵詞平衡二叉樹

2015年Xia等人[27]設(shè)計(jì)了一種基于關(guān)鍵詞平衡二叉樹索引結(jié)構(gòu)(keyword balanced binary tree， KBB-Tree)的多關(guān)鍵詞排序搜索算法，并設(shè)計(jì)了一種貪婪深度優(yōu)先遍歷算法，其算法的時(shí)間復(fù)雜度基本上保持為對數(shù)級，能夠?qū)崿F(xiàn)高效的多關(guān)鍵詞排序搜索.關(guān)鍵詞平衡二叉樹的索引結(jié)構(gòu)采用TF-IDF表示文檔關(guān)鍵詞的權(quán)重值，并采用向量空間模型構(gòu)造一個(gè)索引向量，最后通過安全kNN算法進(jìn)行加密計(jì)算相關(guān)性得分，從而返回top-k個(gè)排序結(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)鍵詞平衡二叉樹時(shí)，從葉子節(jié)點(diǎn)進(jìn)行構(gòu)建生成中間節(jié)點(diǎn)，比較2個(gè)葉子節(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é)省搜索的時(shí)間開銷，提高搜索效率.但是當(dāng)輸入關(guān)鍵詞字典中不存在關(guān)鍵詞時(shí)，該索引結(jié)構(gòu)會(huì)線性地執(zhí)行遍歷操作，致使搜索效率大大降低.

2.3 依存句法

依存句法(dependency grammar)的主要用途是分析句子的句法結(jié)構(gòu)，從而更好地理解句子的含義[28].依存句法具有一個(gè)一般性的假設(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) 句子中有且僅有一個(gè)關(guān)鍵詞是獨(dú)立的；

2) 其他關(guān)鍵詞必須依存于另一個(gè)關(guān)鍵詞；

3) 任何關(guān)鍵詞不能同時(shí)與2個(gè)關(guān)鍵詞之間存在依存關(guān)系；

4) 如果2個(gè)關(guān)鍵詞A和B之間存在依存關(guān)系，而這2個(gè)關(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表示系動(dòng)詞關(guān)系，advmod表示狀語關(guān)系.

3 模型與問題描述

3.1 系統(tǒng)模型

如圖3所示，本系統(tǒng)模型主要分為3個(gè)不同實(shí)體：數(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ù)器時(shí)，云服務(wù)器利用指定算法將安全陷門和安全索引進(jìn)行匹配，并返回top-k個(gè)密文給數(shù)據(jù)使用者.

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

為了便于描述多關(guān)鍵詞可搜索加密算法，表1給出本文使用到的符號定義.

Table 1 Symbol Definition表1 符號定義

系統(tǒng)模型包括5個(gè)多項(xiàng)式時(shí)間算法SSE={KeyGen,BuildIndex,TrapdoorGen,Search,Decrypt}，具體過程為：

1) 初始化KenGen(1λ)→(SK,sk).是一個(gè)由數(shù)據(jù)擁有者執(zhí)行的概率密鑰生成算法，該算法將安全參數(shù)λ作為輸入，然后輸出密鑰SK={S,M1,M2}和對稱密鑰sk.

2) 索引構(gòu)建BuildIndex(sk,SK,F)→(I,C).是一個(gè)概率算法，將密鑰SK和外包文檔集F作為輸入，對文檔集進(jìn)行關(guān)鍵詞提取，生成關(guān)鍵詞字典W，并構(gòu)建關(guān)鍵詞索引，然后使用密鑰SK加密索引向量和使用對稱密鑰sk加密文檔集F.算法輸出安全索引I和密文集C.

3) 陷門生成TrapdoorGen(Wq,SK)→T.是一個(gè)概率算法，該算法將密鑰SK和搜索關(guān)鍵詞Wq作為輸入，利用密鑰SK對搜索關(guān)鍵詞進(jìn)行加密生成安全陷門T，算法返回安全陷門T.

4) 搜索Search(I,T,k)→Ck.是一個(gè)由云服務(wù)器執(zhí)行的確定性算法，該算法將安全索引I、安全陷門T和需要返回文檔的個(gè)數(shù)k作為輸入，計(jì)算安全陷門和安全索引的向量內(nèi)積作為相關(guān)性得分，并對相關(guān)性得分進(jìn)行排序.云服務(wù)器返回包含top-k個(gè)密文的文檔集Ck給數(shù)據(jù)使用者.

5) 解密Decrypt(Ck,sk)→Fk.是一個(gè)確定性算法，該算法將密文文檔Ck和密鑰sk作為輸入，數(shù)據(jù)使用者通過對稱密鑰sk對加密文檔集Ck進(jìn)行解密，算法返回明文數(shù)據(jù)集Fk.

3.2 安全威脅

采用文獻(xiàn)[6,25,27]中提出的安全威脅，假設(shè)數(shù)據(jù)擁有者和數(shù)據(jù)使用者是可靠的，而云服務(wù)器是“誠實(shí)且好奇的”，即它會(huì)“誠實(shí)地”根據(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)計(jì)信息等.因此，云服務(wù)器具有更強(qiáng)的攻擊能力.云服務(wù)器可以根據(jù)已知的陷門信息，并借助一些統(tǒng)計(jì)信息來推斷，分析上傳的安全陷門、安全索引和搜索結(jié)果等來確定搜索中的某些關(guān)鍵詞的明文信息.

3.3 問題描述

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)鍵詞搜索必須遍歷所有索引，使得搜索效率較低.

4 基于語義擴(kuò)展的多關(guān)鍵詞可搜索加密

本文提出一種多關(guān)鍵詞陷門生成方法，以區(qū)分不同關(guān)鍵詞權(quán)重，然后詳細(xì)描述了多關(guān)鍵詞排序搜索過程，最后給出了SEMRS算法的具體實(shí)現(xiàn).

4.1 多關(guān)鍵詞陷門生成

1) 關(guān)鍵詞權(quán)重計(jì)算

用戶進(jìn)行搜索時(shí)，輸入的關(guān)鍵詞存在一定的句法關(guān)系，即關(guān)鍵詞之間存在修飾和被修飾的關(guān)系.因此，關(guān)鍵詞之間的句法關(guān)系一定程度上反映出關(guān)鍵詞的重要性.此外，如果一個(gè)關(guān)鍵詞和不止一個(gè)關(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)系.對于每個(gè)關(guān)鍵詞來說，設(shè)初始關(guān)鍵詞關(guān)系為1，如果該關(guān)鍵詞和其他關(guān)鍵詞之間具有句法關(guān)系，則其權(quán)重變?yōu)?+R，其中R表示2個(gè)關(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)重計(jì)算方法選出權(quán)重最大的關(guān)鍵詞作為待擴(kuò)展關(guān)鍵詞，然后根據(jù)WordNet[31]獲取關(guān)鍵詞的同義詞，這樣對于每個(gè)待擴(kuò)展的關(guān)鍵詞都構(gòu)建了一個(gè)同義詞集，最后通過2個(gè)關(guān)鍵詞概念之間的最大語義相似度近似2個(gè)關(guān)鍵詞的語義相似度，即:

(2)

其中，S(wi)，S(wj)是關(guān)鍵詞wi和wj所包含概念的集合.這里，采用基于信息內(nèi)容(IC)的David算法[32]來衡量2個(gè)概念之間的相似度.

3) 陷門生成

為了更好地反映關(guān)鍵詞和文檔的關(guān)系，在關(guān)鍵詞權(quán)重中引入了TF-IDF技術(shù)，對于每個(gè)文檔關(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.

4.2 多關(guān)鍵詞排序搜索

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)建索引樹的方式確實(shí)大幅提升了搜索效率，但是該算法沒有考慮索引之間的關(guān)聯(lián)性，使得相似度高的索引隨機(jī)分布在索引樹的各個(gè)子樹中，導(dǎo)致多關(guān)鍵詞搜索必須遍歷所有索引才能最終確定搜索結(jié)果.因此，基于凝聚層次聚類(agglomerative hierarchical clustering)[32]的思想將相似索引進(jìn)行聚類為一個(gè)平衡二叉樹索引結(jié)構(gòu).凝聚層次聚類通常是指將每個(gè)對象都作為一個(gè)單獨(dú)的聚類簇，然后每一次聚類最相關(guān)的2個(gè)簇，直至將所有簇聚類為一個(gè)簇為止.由于每次僅聚類2個(gè)最相關(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個(gè)文檔向量{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)個(gè)數(shù)，則簇中心為

(4)

(1) 計(jì)算葉子節(jié)點(diǎn)簇中心之間的歐幾里德距離為

(5)

將歐幾里德距離最小的2個(gè)節(jié)點(diǎn)進(jìn)行聚類生成一個(gè)簇，該節(jié)點(diǎn)的節(jié)點(diǎn)向量NV的計(jì)算如式(3)，簇中心的計(jì)算如式(4).然后再計(jì)算剩余節(jié)點(diǎn)簇中心的歐幾里德距離，并聚類最小的2個(gè)簇，直至聚類所有節(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)的索引位于同一個(gè)子樹中，在索引遍歷過程中只需根據(jù)搜索關(guān)鍵詞和索引的相關(guān)性得分找出對應(yīng)的簇就能實(shí)現(xiàn)整個(gè)遍歷過程，而無需遍歷整個(gè)索引樹.因此，設(shè)置一個(gè)剪枝參數(shù)PT和一個(gè)相關(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個(gè)文檔，返回的文檔個(gè)數(shù)為5，搜索向量為Q=(0.3,0.6,0,0.1)，關(guān)鍵詞搜索路徑為虛線箭頭所指方向.首先，搜索葉子節(jié)點(diǎn)u4,1，并計(jì)算搜索向量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}時(shí)，結(jié)果集中節(jié)點(diǎn)個(gè)數(shù)為4，小于需要返回的文檔數(shù)，繼續(xù)判斷剩余節(jié)點(diǎn)得出Score(Q,u4,1.NV)

Fig. 7 Keyword search圖7 關(guān)鍵詞搜索過程

由于剪枝參數(shù)和相關(guān)性得分閾值的設(shè)置并沒有返回?cái)?shù)據(jù)使用者想要返回的5個(gè)文檔而是返回了最為相關(guān)的4個(gè)文檔，且在進(jìn)行關(guān)鍵詞搜索過程中并沒有遍歷所有節(jié)點(diǎn)，而是對于中間節(jié)點(diǎn)的相關(guān)性得分較小的子樹進(jìn)行剪枝，這樣極大地節(jié)省了遍歷時(shí)間.

4.3 算法具體實(shí)現(xiàn)

本節(jié)基于語義擴(kuò)展的多關(guān)鍵詞排序搜索算法主要包括6個(gè)部分：GenKey，BuildIndexTree，Query-Extension，GenTrapdoor，Search和Decrypt.

1) 初始化GenKey(k)→(SK,sk)

3) 關(guān)鍵詞擴(kuò)展QueryExtension→We

首先，根據(jù)關(guān)鍵詞權(quán)重計(jì)算方法計(jì)算搜索關(guān)鍵詞Wq的權(quán)重，并選出需要擴(kuò)展的關(guān)鍵詞.然后，根據(jù)基于語義相似度的關(guān)鍵詞擴(kuò)展算法提取關(guān)鍵詞的同義詞集，將關(guān)鍵詞轉(zhuǎn)換為概念，并構(gòu)建概念層次樹，計(jì)算關(guān)鍵詞之間的語義相似度.最后，選出相似度最大的若干關(guān)鍵詞作為擴(kuò)展關(guān)鍵詞，并將擴(kuò)展關(guān)鍵詞和搜索關(guān)鍵詞一起作為搜索關(guān)鍵詞We.

Score=·=(MT1I′)TM-11Q′+
(MT2I″)TM-12Q″=I′Q′+I″Q″=
(I′,I″)(Q′,Q″)=rI·Q+Σεvi

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、需要返回的文檔個(gè)數(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)行解密.

5 安全性和性能分析

5.1 安全性分析

本節(jié)將分別從已知密文模型和已知背景模型來分析所提算法的安全性.

1) 已知密文模型中的安全性

(7)

其中,Ip包含2×n×|Ip|個(gè)未知數(shù)，可逆矩陣M1和M2分別包含n×n個(gè)未知數(shù).通過式(7)可以得出方程組中僅包含2×n×|Ip|個(gè)方程式.根據(jù)行列式的性質(zhì)可知，當(dāng)未知數(shù)的數(shù)量大于方程式的數(shù)量時(shí)，不能計(jì)算出方程式的解，即根據(jù)式(7)得不到可逆矩陣M1和M2.同理，通過安全陷門也得不到可逆矩陣M1和M2.因此，本算法采用的拆分索引和搜索向量的加密機(jī)制能夠保證數(shù)據(jù)的隱私性.

2) 已知背景模型中的安全性

在已知背景模型中，數(shù)據(jù)加密和索引及陷門的加密使用的是相同的加密方法.此外，在已知背景模型中引入了虛擬關(guān)鍵詞.因此，SEMRS算法保證了數(shù)據(jù)的安全性與索引和陷門的安全性.

5.2 性能分析

為了進(jìn)一步驗(yàn)證算法的性能，本節(jié)分別從算法的各主要階段：1)系統(tǒng)初始化;2)索引構(gòu)建;3)陷門生成;4)搜索等方面進(jìn)行分析.假設(shè)加密算法采用傳統(tǒng)的對稱加密算法，文檔關(guān)鍵詞的數(shù)量為n，文檔集中包含文檔的個(gè)數(shù)為m，搜索關(guān)鍵詞個(gè)數(shù)為x，擴(kuò)展的關(guān)鍵詞個(gè)數(shù)為y，分析:

系統(tǒng)初始化階段，僅進(jìn)行密鑰生成，因此該階段的時(shí)間復(fù)雜度為O(1).

索引構(gòu)建階段，主要時(shí)間消耗為索引加密，先采用的安全kNN算法對索引進(jìn)行分割，然后使用2個(gè)可逆矩陣相乘進(jìn)行加密，其安全索引構(gòu)建的時(shí)間復(fù)雜度為O(me2)，其中e是關(guān)鍵詞向量的長度.

陷門生成階段，安全陷門的生成與安全索引構(gòu)建過程相似，主要時(shí)間消耗都是關(guān)鍵詞加密和關(guān)鍵詞擴(kuò)展，其時(shí)間復(fù)雜度也是O((x+y)e2).

此外，由于擴(kuò)展關(guān)鍵詞個(gè)數(shù)y應(yīng)小于搜索關(guān)鍵詞個(gè)數(shù)x，且x+y?m.在陷門生成時(shí)，無論搜索關(guān)鍵詞集合中有多少關(guān)鍵詞，陷門長度始終等于所提取文檔關(guān)鍵詞字典長度.算法主要的網(wǎng)絡(luò)通信開銷是傳輸安全陷門T到云服務(wù)器的開銷，由于在本地?zé)o論輸入多少關(guān)鍵詞，使用安全密鑰生成陷門T的大小|T|始終是固定的，因此，即使面對大規(guī)模數(shù)據(jù)集合，陷門傳輸?shù)耐ㄐ砰_銷始終為|T|.

6 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用Java語言編寫，并在AMD5 CPU 2.0 GHz的Windows 10環(huán)境執(zhí)行.數(shù)據(jù)集為聯(lián)邦能源監(jiān)管委員會(huì)發(fā)布的包含517 000多條郵件的Enron email dataset[33].

6.1 準(zhǔn)確率和召回率

為了表現(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)鍵詞的個(gè)數(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時(shí)，準(zhǔn)確率和召回率達(dá)到最大值，隨后準(zhǔn)確率和召回率開始逐漸降低，即在基于多關(guān)鍵詞擴(kuò)展的排序搜索算法中當(dāng)比率參數(shù)為0.4時(shí)，搜索性能達(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)建時(shí)間比較

6.2 索引創(chuàng)建時(shí)間

索引構(gòu)建階段主要執(zhí)行索引構(gòu)建和索引加密.其中索引構(gòu)建的計(jì)算成本主要取決于數(shù)據(jù)集中的文檔個(gè)數(shù)，而索引加密又與關(guān)鍵詞字典包含的關(guān)鍵詞數(shù)量有關(guān).此外，索引構(gòu)建過程是一個(gè)一次性過程，即只在初始階段進(jìn)行索引構(gòu)建，除非后續(xù)對數(shù)據(jù)集進(jìn)行了更新操作，才重新構(gòu)建索引.圖10(a)顯示了本算法和EDMRS算法[27]在給定不同文檔數(shù)量情況下，索引構(gòu)建時(shí)間開銷的變化趨勢.由于關(guān)鍵詞數(shù)量越大，則索引向量的維度也就越大，因此通過觀察可以發(fā)現(xiàn)，隨著關(guān)鍵詞數(shù)量的增加，索引構(gòu)建時(shí)間也越來越大.圖10(b)為在給定關(guān)鍵詞數(shù)量的情況下，索引構(gòu)建時(shí)間隨著文檔數(shù)量的變化趨勢.隨著文檔數(shù)量的不斷增加，索引構(gòu)建時(shí)間也在增加，但SEMRS采用將索引向量分塊的方式減少計(jì)算復(fù)雜性，大大減少了索引加密時(shí)間和索引創(chuàng)建時(shí)間.

6.3 陷門生成時(shí)間

Fig. 11 Trapdoor generation time圖11 陷門生成時(shí)間

陷門生成是關(guān)鍵詞搜索的重要步驟，如圖11所示為陷門生成關(guān)鍵詞數(shù)量的變化趨勢.不難發(fā)現(xiàn)，陷門生成時(shí)間趨向于一個(gè)常數(shù)，不會(huì)隨著搜索關(guān)鍵詞的數(shù)量增長而增長，這是因?yàn)橄蓍T生成時(shí)間主要取決于字典中關(guān)鍵詞的數(shù)量，算法中陷門生成操作的主要耗時(shí)是搜索向量的加密.由于本文采用分塊的方式加密搜索向量，因此總的陷門生成時(shí)間要小于MRSE算法和EDMRS算法的時(shí)間.通過圖11(b)可以看出，生成陷門的時(shí)間成本主要取決于關(guān)鍵詞字典中包含的關(guān)鍵詞數(shù)量，并隨著關(guān)鍵詞數(shù)量的增大而變大.

6.4 搜索時(shí)間

搜索時(shí)間是權(quán)衡算法性能的重要指標(biāo).圖12(a)所示為在給定文檔關(guān)鍵詞數(shù)量的情況下，搜索時(shí)間隨文檔個(gè)數(shù)的變化趨勢，由于文檔向量和索引向量的計(jì)算時(shí)間相同，因此，搜索時(shí)間隨文檔數(shù)量的增加而增加.圖12(b)為給定文檔數(shù)量的情況下，搜索時(shí)間隨文檔關(guān)鍵詞數(shù)量的變化趨勢，通過上文可知，文檔關(guān)鍵詞數(shù)量越大，則索引向量和陷門向量的維度也越大，因此，隨著文檔關(guān)鍵詞數(shù)量的增加，搜索時(shí)間也越來越多.此外，SEMRS算法基于凝聚層次聚類構(gòu)建索引樹結(jié)構(gòu)，該索引樹是平衡二叉樹，并設(shè)計(jì)了一種高效的索引遍歷算法，因此，SEMRS的搜索時(shí)間要小于MRSE和EDMRS算法的搜索時(shí)間.

Fig. 12 Search time圖12 搜索時(shí)間

7 總 結(jié)

在分析查詢關(guān)鍵詞之間的關(guān)系基礎(chǔ)上，提出了一種安全高效的支持語義擴(kuò)展的多關(guān)鍵詞排序搜索算法，解決可搜索加密中的語義檢索問題.我們設(shè)計(jì)了一種基于語義關(guān)系的關(guān)鍵詞權(quán)重算法，并對權(quán)重較大的關(guān)鍵詞進(jìn)行語義擴(kuò)展.為提高查詢效率，構(gòu)造了一種關(guān)鍵詞平衡二叉樹作為文檔的索引結(jié)構(gòu)，并在查詢時(shí)，根據(jù)查詢向量和樹節(jié)點(diǎn)的向量內(nèi)積，進(jìn)行“剪枝”操作.此外，為更好地表達(dá)查詢關(guān)鍵詞和文檔之間的相關(guān)性，在構(gòu)建索引和陷門時(shí)引入了TF-IDF算法，并在陷門中加入關(guān)鍵詞權(quán)重值.最后，通過使用安全kNN，使得所提算法能夠?qū)?種不同安全威脅.