閆璽璽，趙 強，湯永利，李瑩瑩，李靜然

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454003)

目前，云服務(wù)已經(jīng)成為數(shù)據(jù)外包和共享的一個普遍和經(jīng)濟的平臺，大多數(shù)用戶(包括企業(yè)用戶和個人用戶)都使用云服務(wù)對數(shù)據(jù)進行存儲和管理。但是當(dāng)數(shù)據(jù)遷移到云服務(wù)器后，用戶會失去對數(shù)據(jù)的直接控制。為了保護數(shù)據(jù)的安全，在外包之前對數(shù)據(jù)進行加密以確保數(shù)據(jù)的隱私。然而，通過加密的形式外包數(shù)據(jù)，如何有效地訪問數(shù)據(jù)成為了新的難題，從而催生了可搜索加密。文獻[1]首次提出可搜索加密概念，將文件劃分為單詞并逐個加密，在檢索時單詞與密文進行掃描對比，查看密文中是否包含要查詢的關(guān)鍵字，但隨著文件數(shù)量的增加，服務(wù)器的計算開銷也會增大。為了解決與密文進行比對的問題，文獻[2]通過布隆過濾器將加密之后的關(guān)鍵字映射為比特到索引表中，搜索時只需將陷門同樣也映射成比特與索引表匹配即可。之后，可搜索加密方案對于檢索方式的研究得到飛速的發(fā)展。文獻[3]實現(xiàn)了多關(guān)鍵字查詢，并通過雙關(guān)鍵字索引結(jié)構(gòu)提高了搜索效率。文獻[4]采用潛在狄利克雷分布(Latent Dirichlet Allocation，LDA)模型實現(xiàn)了基于語義的多關(guān)鍵字搜索，改進了TF-IDF(Term Frequency-Inverse Document Frequency)模型中忽略了關(guān)鍵字與文檔之間的語義關(guān)聯(lián)的缺點。文獻[5]實現(xiàn)了模糊關(guān)鍵字搜索，解決了精確搜索中無法接受關(guān)鍵字具有輕微拼寫錯誤和格式不一致的問題。

檢索方式的多樣性使檢索效率和精確率都得到了提升，但仍然無法避免在檢索過程中陷門與所有加密索引進行對比。文獻[6]通過提取關(guān)鍵字，根據(jù)關(guān)鍵字的相似性將相似文檔聚類在一起，列出簇中所有的關(guān)鍵字，并通過安全散列算法計算得到關(guān)鍵字的哈希值發(fā)送給數(shù)據(jù)擁有者。在檢索時，比較簇索引的哈希值和陷門哈希值‘0’的位置來找到匹配的簇。該方案解決了檢索文件時陷門與所有索引比較時開銷過大的問題，但是它忽略了關(guān)鍵字在文檔中的比重和每個簇的主題分布。文獻[7]使用k均值聚類(k-means clustering，k-means)算法對文檔進行聚類，通過計算其他文檔與質(zhì)心的歐氏距離來進行聚類，提高了相同簇中文檔的相似性。文獻[8]首次提出使用潛在狄利克雷分布模型和k均值算法來解決隱私保護問題。

在實際應(yīng)用場景中，可搜索加密機制需要為用戶提供相應(yīng)的搜索權(quán)限，以使不同的用戶可以訪問不同的文件。最基本的解決方案是數(shù)據(jù)所有者使用不同的密鑰加密不同的文件。之后，數(shù)據(jù)所有者給每個用戶授權(quán)搜索的所有文件的加密/解密密鑰，顯然這個方法是繁瑣且低效的。文獻[9-10]提出了一個基于屬性的可搜索加密的方案，將私鑰、密文與屬性和訪問結(jié)構(gòu)相關(guān)聯(lián)，陷門由用戶私鑰生成。在檢索過程中，當(dāng)文檔的關(guān)鍵字索引和訪問結(jié)構(gòu)與陷門中的關(guān)鍵字和屬性同時滿足時，用戶才可以從云服務(wù)器中獲得密文并解密。為了進一步提升效率，采用對稱加密的思想對文件和索引進行加密。文獻[11]添加了一個對稱密鑰進行加密。用戶在執(zhí)行查詢操作時，需要先解密對稱密鑰才能生成陷門。在上述兩種方案中，密鑰的大小取決于數(shù)據(jù)擁有者的訪問控制策略中涉及的屬性總數(shù)。文獻[12]通過賦予授權(quán)證書來控制用戶的搜索權(quán)限，每當(dāng)新用戶加入時，會為該用戶提供一個具有關(guān)鍵字列表的授權(quán)證書并結(jié)合聯(lián)合查詢使用戶只能對授權(quán)證書上的關(guān)鍵字進行查詢。但是該方案采用了布爾查詢，每次檢索返回所有匹配的文檔，可返回的文檔中有很多是用戶不需要的，且是無序的。由于下載了許多不必要的文件，且需要從檢索的結(jié)果中刪除不相關(guān)的文件，會導(dǎo)致通信成本的增加。文獻[13]采用廣播加密的方式，為每組用戶提供可訪問的加密文件，并允許用戶在被授權(quán)訪問的文件的子集內(nèi)進行搜索關(guān)鍵字，但該方案不支持多關(guān)鍵字搜索。

為了滿足云環(huán)境下數(shù)據(jù)共享時靈活的訪問控制需求，且提高搜索效率，筆者提出了一種具有訪問控制功能的高效可搜索加密方案。主要貢獻如下：(1)為了減少搜索時間和保證搜索的精確率，使用k均值聚類算法將文檔集分為若干個簇，并結(jié)合文獻[8]中的文檔主題提取技術(shù)為每個簇生成主題，計算每個關(guān)鍵字的權(quán)重以及關(guān)鍵字在該主題的分布概率，對每個主題用關(guān)鍵字集合進行表示，減小搜索集的大小，從而提高搜索效率。(2)采用廣播加密體制在加密階段為每組用戶提供相應(yīng)的訪問權(quán)限，進而縮短每個用戶的密鑰長度，達到常數(shù)大小。(3)構(gòu)造多關(guān)鍵字搜索方案，對索引隱私、文件隱私和標(biāo)識符隱私進行保護，減少搜索操作中陷門與索引的對比次數(shù)。與其他方案進行對比表明，這種方案同時支持靈活的訪問控制、多關(guān)鍵字搜索以及多客戶端設(shè)置，并通過實驗表明該方案在保證搜索精確率的情況下對搜索效率進行了優(yōu)化。

1 預(yù)備知識

1.1 判定線性假設(shè)

1.3 廣播加密的概念模型

廣播加密方案的概念模型一般由以下4部分構(gòu)成。

(1) 系統(tǒng)建立Setup(λ，n)：將安全參數(shù)λ和接收廣播消息用戶的最大數(shù)量n作為輸入，輸出系統(tǒng)主密鑰K0和系統(tǒng)公鑰集合K1，其中K0被私鑰生成中心秘密保存。

(2) 私鑰提取Extract(K1，K0，di)：將公鑰K1、主密鑰K0和用戶身份di作為輸入，輸出用戶對應(yīng)的私鑰Yi。

(4) 廣播解密Decrypt(S，d，Yi，hk，K1)：將密文頭(hk，S)、公鑰K1、接收方身份d及其私鑰Yi作為輸入。如果d∈S，則輸出會話密鑰K2。當(dāng)接收方要對密文主體Ck解密時，使用上述獲得的會話密鑰K2對Ck進行解密，輸出消息明文M。

2 算法與安全模型定義

2.1 系統(tǒng)模型

該方案基于主題提取和聚類來減少搜索外包加密數(shù)據(jù)所需的比較次數(shù)，通過廣播加密控制數(shù)據(jù)用戶的訪問權(quán)限。模型包含3個實體，分別是數(shù)據(jù)擁有者、用戶和云服務(wù)器。

2.2 算法定義

Setup(n，λ)：算法將用戶數(shù)量n和安全參數(shù)λ作為輸入，輸出(K1，{Y1，…，Yn})。K1是系統(tǒng)公鑰集合，Yi是用戶i的私鑰。

Enc(K1，Wt，Sk，Mk，I(wi))：數(shù)據(jù)擁有者將文件Mk、簇的標(biāo)識符Wt、公鑰K1、用戶集合Sk和關(guān)鍵字集合I(wi)作為輸入，輸出標(biāo)識符密文Ck、文件密文C′k和加密關(guān)鍵字索引I′(wi)，上傳到云服務(wù)器。

Trap(Yi，search query)：用戶將私鑰Yi和搜索查詢作為輸入，輸出用戶i對于搜索查詢的陷門ti，W，發(fā)送給云服務(wù)器。

Test(K1，Sk，ti，W，Ck)：云服務(wù)器將標(biāo)識符密文Ck、陷門ti，W、用戶集合Sk、公鑰K1作為輸入，輸出β∈{0，1}。如果i∈Sk且陷門中的關(guān)鍵字集合所對應(yīng)的簇屬于Ck，則輸出β=1；否則，輸出β=0。

Search(ti，W，I′(wi))：當(dāng)β=1時，云服務(wù)器執(zhí)行搜索算法，將相關(guān)性得分最高的前k個加密文件返回給用戶；當(dāng)β=0時，則返回⊥。

Dec(K1，Yi，C′k，Sk)：用戶接收到加密文件，將公鑰K1、私鑰Yi和文件密文C′k作為輸入，輸出明文Mk。

2.3 安全模型

定義1(索引隱私) 如果敵手得到了一些加密的關(guān)鍵字索引和相關(guān)的私鑰，敵手無法在多項式時間內(nèi)學(xué)習(xí)到關(guān)于關(guān)鍵詞的任何信息，則稱滿足索引隱私。

定義2(文件隱私) 通過挑戰(zhàn)者C和敵手A之間的游戲，為本方案中的文件隱私定義靜態(tài)語義安全。

初始化：A接收參數(shù)(n，λ)并且選擇想要挑戰(zhàn)的用戶集合S0，明文消息M0，M1。

設(shè)置：C運行Setup(n，λ)算法獲得公鑰K1，然后將公鑰K1發(fā)送給A。

問詢：A自適應(yīng)地發(fā)出對用戶j?S0的私鑰查詢。C將用戶j的私鑰Yj發(fā)送給A。

挑戰(zhàn)：C選擇一個隨機數(shù)b∈{0，1}，運行加密算法Enc(S0，K1，Mb)獲得密文C′，并將密文發(fā)送給A。

猜測：A要輸出一個猜測b′∈{0，1}。當(dāng)b=b′時，宣布敵手在游戲中獲勝。

文件隱私游戲如果對所有攻擊|Pr[b=b′]-1/2|≤Nnegl(λ，n)，則滿足選擇明文攻擊(Chosen-Plaintext Attack，CPA)安全。

定義3(標(biāo)識符隱私) 在本方案中，通過敵手A和挑戰(zhàn)者C之間的游戲來定義標(biāo)識符隱私的靜態(tài)語義安全。敵手A和挑戰(zhàn)者C將參數(shù)(n，λ)作為輸入。

初始化：A接收安全參數(shù)λ，并輸出希望挑戰(zhàn)的用戶集合S0和簇對應(yīng)的標(biāo)識符W0，W1。

設(shè)置：C運行Setup(n，λ)算法去獲得公鑰K1和一組私鑰Y1，…，Yn，然后將公鑰K1發(fā)送給A。

問詢：A自適應(yīng)地發(fā)出查詢q1，…，qλ，其中qk是對用戶i和關(guān)鍵字集合W的陷門查詢。A進行陷門問詢時，當(dāng)且僅當(dāng)i?S0，且詢問的關(guān)鍵字集合所對應(yīng)簇的標(biāo)識符Wk滿足Wk≠Wb，b∈{0，1} 。對陷門查詢，挑戰(zhàn)者C運行陷門生成算法Trap(Yi，search query)→ti，Wt，獲取ti，Wt發(fā)送給A。

猜測：C選擇一個隨機數(shù)b∈{0，1}，運行加密算法Enc(K1，Wb，S0)，輸出(C0，S0)，其中Wb是簇的標(biāo)識符。A要輸出一個猜測b′∈{0，1}，當(dāng)b=b′時，宣布敵手在游戲中獲勝。

如果不存在多項式時間內(nèi)A以不可忽略的優(yōu)勢區(qū)分不同簇下加密的標(biāo)識符密文，則本方案滿足標(biāo)識符隱私。

3 方案構(gòu)造

(1) 密鑰生成

(1)

通過安全信道將私鑰發(fā)送給用戶i，私鑰Yi=(di，1，…，di，14，u，v)。

(2) 語義聚類

聚類用于在創(chuàng)建索引之前將文檔分為不同的簇。對文檔進行聚類應(yīng)減少每個簇的文檔數(shù)量，以提高搜索過程的效率。為了執(zhí)行聚類，數(shù)據(jù)擁有者將所有文檔收集到一個數(shù)據(jù)集F={f1，f2，…，fA}中。然后，數(shù)據(jù)擁有者在F上應(yīng)用k均值算法，生成k個簇，即L={l1，l2，…，lk}。lt是一組相似文檔的集合，其中t=1，2，…，k。這意味著同一簇中的所有文檔應(yīng)盡可能地相似，并且不同簇中的文檔應(yīng)與所有其他簇中的文檔盡可能不相似。

k均值算法作為劃分式聚類算法，對于大部分數(shù)據(jù)都有較強的適用性。算法相對可伸縮，且計算簡單、高效；空間復(fù)雜度較低，為線性復(fù)雜度。相對于同為劃分式聚類算法的Single-Pass增量聚類算法，其對數(shù)據(jù)輸入時的順序十分敏感；基于層次的聚類算法相較于k均值算法，時間復(fù)雜度較高。文獻[8]中的實驗表明，k均值算法的搜索效率要高于層次聚類算法的；基于密度的聚類算法魯棒性很強，但是結(jié)果的精度與參數(shù)設(shè)置關(guān)系密切，實用性不強。

具體流程如下：① 隨機選擇k個文檔作為質(zhì)心。② 計算各個文檔到各個質(zhì)心的歐氏距離。③ 將文檔分配到距其最近的簇中。④ 分配完成后重新計算各類的質(zhì)心，觀察聚類是否收斂。若收斂，則完成聚類算法；否則，繼續(xù)執(zhí)行②至④步。

(3) 提取聚類主題和簇索引

主題建模是從文檔集合中生成關(guān)鍵字。采用潛在狄利克雷分布算法為L={l1，l2，…，lk}中的每個簇生成關(guān)鍵字，這些關(guān)鍵字將作為每個簇的索引。

使用潛在狄利克雷分布算法進行文本收集的主題建模分4個步驟執(zhí)行：① 從帶有參數(shù)β的狄利克雷分布中選擇多項式θt作為每個主題t的主題分布，其中β為每個主題詞分布上的狄利克雷參數(shù)；② 對于每個文檔f，從帶有參數(shù)α的狄利克雷分布中選擇一個多項式文檔分布θd，其中α為每個文檔主題分布上的狄利克雷參數(shù)；③ 為文檔中的每個單詞w選擇來自θd的主題t；④ 從θt中選擇一個單詞w來代表文本文檔的主題。生成主題的概率為

(2)

其中，K是主題的數(shù)量，θp是文檔f的主題分布，β是在每個主題詞分布上的狄利克雷參數(shù)，N是文檔集中關(guān)鍵字的總數(shù)量，α是每個文檔主題分布上的狄利克雷參數(shù)，ti是文檔中第i個單詞的主題，θ是文檔的主體分布，wi是文檔第i個關(guān)鍵字，φ是一個主題的單詞分布。經(jīng)過潛在狄利克雷分布算法處理后，每個簇會有該簇的關(guān)鍵字列表來表示該簇內(nèi)文檔的主要信息。定義該關(guān)鍵字列表為Wt={w1，w2，…，wk}，1≤t≤k，并將該關(guān)鍵字列表作為該簇的索引。

(4) 生成關(guān)鍵字索引

聚類結(jié)束后，數(shù)據(jù)擁有者使用潛在狄利克雷分布算法為每個簇創(chuàng)建一個索引，然后為每個簇內(nèi)的文檔創(chuàng)建關(guān)鍵字索引。本方案構(gòu)造關(guān)鍵字索引時使用文獻[14]中提出的索引技術(shù)，用排名功能來計算匹配文件與給定搜索請求的相關(guān)性得分。評估相關(guān)性分數(shù)使用的統(tǒng)計測量方法是TF-IDF規(guī)則。關(guān)鍵字索引創(chuàng)建步驟如下：

① 數(shù)據(jù)擁有者從文檔集合F={f1，f2，…，fA}中對每個文檔fi提取出對應(yīng)的關(guān)鍵詞集合wj={w1，w2，…，wm}，數(shù)據(jù)擁有者建立關(guān)鍵字索引I(wj)=d(fij)，1≤i≤p，1≤j≤m。

③ 將關(guān)鍵字的相關(guān)性得分添加到索引中，即I(wj)=(d(fij)‖(sij))。

(5) 加密階段

(3)

(6) 陷門生成

Trap(ski，search query)→ti，Wt，用戶i選取r，r′∈Zp計算(tr，1，tr，2，…，tr，5)。

(4)

(7) 權(quán)限控制

Test(K1，Sk，ti，Wt，Ck)→β，云服務(wù)器接收到陷門之后，檢查下面的等式是否成立：

(5)

其中，T=e(hk，3，tr，3)e(hk，2，tr，2)e(hk，4，tr，3)。當(dāng)該用戶屬于用戶集合Sk中，且陷門中的簇標(biāo)識符Wt與Ck中的簇標(biāo)識符Wt相同時，等式成立，返回測試值β=1；否則，返回β=0。驗證過程如下：

同理，可得

(8) 排名搜索

(9) 解密階段

4 方案分析

4.1 安全性分析

定理1基于定義1，本方案滿足索引的隱私保護。

綜上所述，這種方法抵抗選擇密文攻擊是安全的?；趯﹃P(guān)鍵字的加密方法及其對內(nèi)部和外部敵手攻擊的安全強度，以及選擇密文攻擊，本方案滿足索引的隱私保護。

定理2主要構(gòu)造在判定性-BDHE假設(shè)下具有文件隱私性。

初始化：A接收參數(shù)(n，λ)并且向C發(fā)送選擇挑戰(zhàn)的用戶集合S0，明文消息M0，M1。

聲明：當(dāng)Z=e(g，v)時(即C的輸入是從PBDHE采樣的-BDHE元組中的)，μ=0。此外因此對A才是一個有效的挑戰(zhàn)，如同在真實攻擊中一樣。另一方面，當(dāng)Z是群G1中的一個隨機元素(即C的輸入是從RBDHE采樣的)時，和只是G1中的隨機獨立元素。

猜測：A輸出對于b的猜測b′。如果b=b′，則C輸出μ′=0，表示Z=e(g，v)；否則，輸出μ′=1，表示Z是群G1一個隨機元素。

當(dāng)(g，v，yg，α，，Z)是來自RBDHE的采樣時，A不能獲得Mb的有效密文，A只能純粹猜測b的值，因此而當(dāng)b≠b′時，C輸出μ′=1，所以

當(dāng)(g，v，yg，α，，Z)是來自PBDHE的采樣時，A可以獲得Mb的有效密文。由前面的假設(shè)可知，A攻破本方案的優(yōu)勢(即區(qū)分密文)是ε，因此而當(dāng)b=b′時，C輸出μ′=0，所以

綜上所述，C攻破定性-BDHE假設(shè)的優(yōu)勢為

Adv-BDHE=

定理2證明完畢。

定理3(標(biāo)識符隱私)本方案的主要構(gòu)造在決策線性假設(shè)下具有標(biāo)識符隱私性。

證明 敵手A對于簇關(guān)鍵字索引W0，W1，獲得標(biāo)識符密文Cb，輸出猜測b′。若b=b′，則A挑戰(zhàn)成功(用Succ來表示該事件)，挑戰(zhàn)者C利用A來攻擊判定線性假設(shè)。挑戰(zhàn)者C接收一個決策線性實例g，gz1，gz2，gz1z3，gz2z4，Z，Z為gz3+z4或者是G中的一個隨機元素，兩者的概率是相等的。為了方便起見，將其改寫為g，gz1，gz2，gz1z3，V，gt，gt=Z。游戲流程如下。

初始化：敵手A向挑戰(zhàn)者C發(fā)送希望挑戰(zhàn)的用戶集合S0和簇對應(yīng)的關(guān)鍵字索引W0，W1。

設(shè)置：挑戰(zhàn)者選取隨機元素α，γ，ζ，a2，b2和b←R{0，1}，使用與決策線性實例中相同的g，設(shè)置g1，…，gn，gn+2，…，g2n，υ，其中g(shù)i=gαi，υ=gγ，h0，1=g-Wb+，h1，1=g，h0，2=gz2(-Wb)g，h1，2=gz2。挑戰(zhàn)者C設(shè)置

問詢1：對(S，W)進行加密問詢，其中W≠Wb。挑戰(zhàn)者C選取，1，2計算出hk，1，…，hk，7發(fā)送給敵手A，計算方式如式(3)所示。

問詢2：對(i，W)進行陷門問詢，敵手A進行陷門問詢時當(dāng)且僅當(dāng)i?S0，且詢問的關(guān)鍵字集合所對應(yīng)簇的關(guān)鍵字索引Wk滿足Wk≠Wb。挑戰(zhàn)者C選取ρi1，ρ′i1，ρi2，ρ′i2，r，r′計算出陷門中的(tr，1，tr，2，…，tr，5)發(fā)送給敵手A，計算方式如式(4)所示。

挑戰(zhàn)：挑戰(zhàn)者C以簇對應(yīng)的關(guān)鍵字索引Wb和集合S0作為響應(yīng)。假設(shè)t1=z3，挑戰(zhàn)者C隨機選取t2∈Zp，輸出密文。

猜測：令Γ0為事件敵手A輸出一個字節(jié)b′來猜測標(biāo)識符密文Cb是屬于哪個索引的加密結(jié)果，如果b′=b，則輸出為1；否則，輸出為0。當(dāng)輸出為1時，挑戰(zhàn)者C猜測B=gz2(t-z3)，Z=gt；當(dāng)輸出為0時，挑戰(zhàn)者C猜測B獨立于z1，z2，t，t1，t2時，Z是隨機的。

分析：令D表示B=gz2(t-z3)，Z=gt；令R表示B獨立于z1，z2，t，t1，t2時，Z是隨機的。

再證明Pr[C(Γ0)=1|D]=Pr[S]，S表示成功。因為事件D發(fā)生時，B=gz2(t-z3)，Z=gt(z1，z2，t，t1，t2是隨機選取的)，所以C輸出1當(dāng)且僅當(dāng)成功。

Pr[C(Γ0)=1=0]=Pr[D]Pr[C(Γ0)=1=0|D]+Pr[R]Pr[C(Γ0)=1=0|R]=

即如果A能以某個不可忽略的優(yōu)勢ε區(qū)分不同簇索引下加密的標(biāo)識符密文，則C可以以相同的優(yōu)勢攻破判定線性假設(shè)。

4.2 功能對比

將文中的功能特征與文獻[8，13]中的方案進行對比，如表1所示。文獻[8]中的方案支持多關(guān)鍵詞搜索，使用了排名關(guān)鍵詞搜索，并且通過減少陷門與索引的比較次數(shù)提高效率，但是文獻[8]不具備訪問控制功能和多客戶端設(shè)置。文獻[13]中的方案通過廣播加密的方式，實現(xiàn)了多客戶端設(shè)置，并在加密過程中將關(guān)鍵字一起加密實現(xiàn)訪問控制，但是文獻[13]中的方案只支持單關(guān)鍵詞查詢，而且每次查詢需要將陷門與所有索引進行對比。

從功能方面來看，筆者提出的方案在實現(xiàn)訪問控制和多客戶端的前提下，改進了文獻[13]中單關(guān)鍵詞搜索的權(quán)限，并通過聚類后的優(yōu)勢減少了陷門與索引的對比次數(shù)。

表1 功能對比

4.3 計算開銷分析

將文中的方案與文獻[8，13]中的方案從計算開銷方面進行分析比較。在方案對比中，E表示模指數(shù)運算，P表示雙線性對計算，M表示群中模乘運算，X表示異或運算，H代表哈希運算，n代表文檔數(shù)量，j表示用戶數(shù)量，t表示陷門中的關(guān)鍵字個數(shù)。計算開銷如表2所示。

由于文獻[8]中的方案沒有細粒度訪問控制功能，所以無驗證階段并且不需要進行配對操作。文獻[13]中的方案為單關(guān)鍵字可搜索加密方案，因此生成陷門的計算開銷與關(guān)鍵字個數(shù)無關(guān)。筆者提出方案的主要優(yōu)勢是對文獻[13]中的方案進行了功能性的擴展，并在搜索階段減少搜索集的大小來提高搜索效率。搜索效率的提高將在節(jié)4.4中進行闡述。

表2 計算開銷對比

4.4 實驗分析

(1) 數(shù)據(jù)集和評估環(huán)境

數(shù)據(jù)集(https：//archive.ics.uci.edu/ml/datasets/NSF+Research+Award+Abstracts+1990-2003) 包含描述1990年至2003年NSF基礎(chǔ)研究獎項的129 000個摘要，選擇了3 000個摘要作為實驗數(shù)據(jù)，并提取了226個不同的關(guān)鍵字。實驗硬件環(huán)境為Intel Core i5-9300H，2.4 GHz，處理器內(nèi)核數(shù)為4，內(nèi)存為8 GB DDR4；軟件環(huán)境是Windows 10 64位操作系統(tǒng)和PyCharm開發(fā)平臺。本次實驗的主要內(nèi)容是計算聚類操作后返回正確文檔的精確率以及對同一個可搜索加密方案進行聚類操作和未進行聚類操作的搜索時間對比。

在k均值算法中的聚類數(shù)目會影響搜索精度和搜索效率。聚類數(shù)目越小，每個簇的文檔數(shù)量就會增加，搜索精度就越高，但搜索效率會下降；聚類數(shù)目越大，每個簇的文檔數(shù)量就會減少，搜索精度就越低，但搜索效率會提升。因此，聚類數(shù)目的選取變得至關(guān)重要。為了保證每個簇中有一定的文檔數(shù)量，將聚類數(shù)目的區(qū)間設(shè)置在5～20之間，并采用肘部法則，按照遞增的順序嘗試不同的聚類數(shù)目，選取拐點作為聚類數(shù)目。經(jīng)過實驗測試，選擇11為聚類數(shù)目。

(2) 搜索精度

表3 搜索精確率

(3) 搜索時間評估

將本方案對文檔集使用聚類算法和不使用聚類算法兩種情況的搜索時間進行對比，根據(jù)查詢關(guān)鍵字個數(shù)(q)、文檔數(shù)(m)和返回的文檔數(shù)(k)評估和分析了搜索時間(Δt)。圖1顯示了CSP基于授權(quán)用戶從陷門搜索文檔所需的時間，搜索時間包括獲取陷門中的關(guān)鍵字集合，并根據(jù)該關(guān)鍵字集合選擇相似性分數(shù)最高的簇中，計算該關(guān)鍵字集合在每個文檔中的分數(shù)。搜索時間隨著查詢關(guān)鍵字個數(shù)的增加而增加。如果對文檔集不使用聚類算法，雖然不用計算關(guān)鍵字集合和簇索引的相似性分數(shù)，但由于是在整個文檔集上進行搜索，當(dāng)查詢關(guān)鍵字個數(shù)為10時，搜索時間約為39.89 ms；當(dāng)查詢關(guān)鍵字個數(shù)為50時，搜索時間約為50.82 ms。當(dāng)使用聚類算法后，搜索效率提高了約6倍，搜索時間分別約為5.53 ms和9.08 ms。

在圖2中，設(shè)定文檔總數(shù)為1 000，1 500，2 000，2 500，3 000。當(dāng)未進行聚類操作時，可以發(fā)現(xiàn)文檔總數(shù)越多，搜索時間就越長，且遠高于聚類后的搜索時間。當(dāng)文檔總數(shù)為1 500時，搜索時間約為10.5 ms；當(dāng)文檔總數(shù)為2 500時，搜索時間約為18.92 ms。在進行聚類后，在簇中文檔數(shù)量相似的情況下來計算搜索時間。此次選擇的簇中文件數(shù)量約為80。當(dāng)簇中文檔數(shù)量相似時，搜索時間分別約為1.18 ms，1.3 ms，1.19 ms，1.23 ms，1.26 ms。

圖1 基于查詢關(guān)鍵字個數(shù)的搜索時間

圖2 基于文檔總數(shù)的搜索時間

在圖3中顯示出搜索時間會隨著簇中文檔數(shù)量的增加而增加。當(dāng)簇中文檔數(shù)量為107時，搜索時間約為1.56 ms；當(dāng)簇中文檔數(shù)量為244時，搜索時間約為3.55 ms；當(dāng)簇中文檔數(shù)量為392時，搜索時間約為5.6 ms。

圖2和圖3顯示出聚類后的搜索時間受到每個簇中文檔數(shù)量的影響，而不會受到文檔總數(shù)的影響，因此搜索時間不會因為文檔總數(shù)的增多而增加。

圖4顯示出搜索時間會隨著返回的文檔數(shù)量的增加而增加，且基于相同的返回文檔數(shù)量，進行聚類操作后的搜索時間要優(yōu)于未進行聚類操作的搜索時間。隨著返回文檔數(shù)量的增加，兩者的搜索時間相差越大。當(dāng)未進行聚類時，若返回文檔數(shù)量為50，則搜索時間約為20.72 ms；若返回文檔數(shù)量為150，則搜索時間約為 36.23 ms；若返回文檔數(shù)量為300，則搜索時間約為55.75 ms。當(dāng)進行聚類后，選取簇中文檔數(shù)量為363的簇，若返回文檔數(shù)量為50，則搜索效率提高了約4倍；若返回文檔數(shù)量為150，則搜索效率提高了約5倍；若返回文檔數(shù)量為300，則搜索效率提高了6倍。

圖3 基于簇中最大文檔數(shù)的搜索時間

圖4 基于返回的文檔數(shù)量的搜索時間

綜上所述，筆者提出的方案在功能方面更加全面，實現(xiàn)了訪問控制功能、多關(guān)鍵字搜索以及多客戶端的設(shè)置。在搜索效率方面，對文檔集采用聚類方法，根據(jù)查詢關(guān)鍵字個數(shù)、文檔數(shù)和返回的文檔數(shù)，評估和分析了搜索時間。結(jié)果表明，在保持了搜索文檔的精確率前提下(精確率平均約為91.67%)，大大提高了搜索效率，并使得搜索時間與文檔總數(shù)無關(guān)。

5 結(jié)束語

筆者提出的方案在可搜索加密方案的基礎(chǔ)上，對明文消息進行聚類，并對每個簇進行主題和摘要提取。通過陷門中的關(guān)鍵字集合來選擇在相關(guān)度最高的簇中進行搜索，以減少陷門與索引的對比次數(shù)。此外，對加密數(shù)據(jù)進行排序的多關(guān)鍵字搜索減少了文件檢索階段的通信開銷，從而以最小的誤報為用戶提供了最相關(guān)的文件。同時，將每個簇的摘要加入加密過程中，分發(fā)給用戶對于簇的權(quán)限控制。筆者提出的方案保證了用戶都只擁有常數(shù)大小的私鑰，網(wǎng)絡(luò)帶寬使用和服務(wù)器的存儲開銷不取決于被授權(quán)訪問文件的用戶數(shù)量。

未來將對聚類算法進行改進，以支持云環(huán)境中更高效的動態(tài)數(shù)據(jù)操作和對大型加密數(shù)據(jù)的排名多關(guān)鍵字搜索。另外，希望能高效地更新用戶集(從預(yù)定義的授權(quán)集中添加或刪除用戶)。