云存儲環(huán)境中多關(guān)鍵詞加密排序搜索方法研究

黃 健，鐵治欣，2，宋瀅錕

（1.浙江理工大學信息學院，浙江 杭州 310018；2.浙江理工大學科學與藝術(shù)學院，浙江 紹興 312369）

0 引言

隨著大數(shù)據(jù)與云計算技術(shù)的發(fā)展，云存儲也逐漸受到人們重視。很多用戶和企業(yè)開始將復(fù)雜的數(shù)據(jù)從本地站點外包給商業(yè)公共云進行存儲，以獲得極大的靈活性，并節(jié)約成本，同時實現(xiàn)信息共享［1］。然而，在云存儲環(huán)境下存在一些數(shù)據(jù)安全隱患，個人信息或機密文件等一些隱私也很容易被泄露出去。為保證隱私信息的安全性，數(shù)據(jù)在存儲到云端前需對其進行加密。盡管加密后的數(shù)據(jù)可免受不法用戶、非授權(quán)用戶及不可信云服務(wù)商的攻擊，但同時也帶來了如檢索效率低、檢索難度高等問題［2］。

基于明文的關(guān)鍵詞檢索方案對密文是不可行的，但如果每次查詢時都將密文數(shù)據(jù)下載到本地，在本地解密后再執(zhí)行查詢，不僅浪費了本地存儲空間，而且提高了檢索難度。如何在保護隱私的前提下實現(xiàn)加密文件搜索，仍是目前迫切需要解決的問題。迄今已有很多學者對可搜索加密技術(shù)進行了研究，并提出一些有效方法，使用戶能夠輸入關(guān)鍵詞對加密文檔進行檢索［3-6］。然而直接將這些方法應(yīng)用于復(fù)雜的文檔系統(tǒng)并不科學，因為這些方法不僅檢索效率低，而且不適用于要求更高的檢索情景。一些相關(guān)研究也嘗試提高密文檢索的靈活性，但仍不能按照用戶需求排序篩選出數(shù)據(jù)［7］?，F(xiàn)有云存儲環(huán)境下的密文排序搜索方案執(zhí)行創(chuàng)建與更新加密索引時間較長，且隨著文檔數(shù)量的增加，檢索效率會逐步降低。因此，尋找一種既能降低檢索開銷，又能提高檢索效率的方案是目前的主要研究方向。

1 相關(guān)工作

可搜索加密技術(shù)是將數(shù)據(jù)和索引加密后存儲到遠程服務(wù)器中，根據(jù)用戶提交的加密后的搜索請求生成特定陷門對加密數(shù)據(jù)進行搜索，之后返回匹配文檔。在整個過程中，云服務(wù)器除負責存儲與搜索外，不能獲得任何有關(guān)的數(shù)據(jù)信息。

最早的可搜索加密技術(shù)是由Song 等［8］提出的，這種對稱可搜索加密方案的主要流程是先將文檔拆分成多個詞，然后用流密碼對這些關(guān)鍵詞進行雙層加密，當用戶輸入查詢關(guān)鍵詞后，云服務(wù)器會將陷門與加密后的關(guān)鍵詞依次進行匹配，并根據(jù)匹配結(jié)果返回相應(yīng)的加密文檔。該方案雖然滿足了安全性要求，但是全文搜索效率較低。Goh［9］首次采用布隆過濾器作為安全索引結(jié)構(gòu)，對提取的關(guān)鍵詞利用哈希函數(shù)計算其對應(yīng)哈希值，之后映射到布隆過濾器中。當用戶輸入查詢關(guān)鍵詞時，通過相同的哈希函數(shù)計算、查詢關(guān)鍵詞的哈希值，并驗證其在布隆過濾器相應(yīng)位置處的值是否相同。該方案雖然提高了查詢效率，但在檢索時會存在誤差，從而影響結(jié)果的準確性。Chai 等［10］首次提出“半誠實且好奇”的云服務(wù)器模型，由于為了節(jié)省計算量和帶寬資源，服務(wù)器提供商可能僅執(zhí)行了部分搜索操作并返回部分搜索結(jié)果，因此提出基于單詞查找樹索引結(jié)構(gòu)的可驗證可搜索加密方案。Mahajan 等［11］提出層次聚類方法用于云數(shù)據(jù)保護，該框架的重要組成部分是數(shù)據(jù)復(fù)制以及使用SHA1 哈希策略進行檢查。Chen 等［12］提出一種新的基于關(guān)鍵字搜索的雙服務(wù)器公鑰加密框架，通過光滑投影構(gòu)造散列函數(shù)，可防止來自兩個不可信服務(wù)器的關(guān)鍵詞猜測攻擊。Tariq 等［13］協(xié)調(diào)了對稱和非對稱加密算法，設(shè)計一種新的基于服務(wù)器認證的雙重加密框架，利用通配符技術(shù)尋找加密數(shù)據(jù)，同時對服務(wù)器進行驗證，從而提高了數(shù)據(jù)的安全性。

隨著數(shù)據(jù)文件的增加，關(guān)鍵詞詞典中詞的數(shù)量也不斷增加，使得通過構(gòu)建索引進行關(guān)鍵詞檢索的計算量增大，效率很低。Cao 等［14-15］解決了加密數(shù)據(jù)的排序搜索問題，增強了系統(tǒng)的可用性，并提出基于多關(guān)鍵詞排序的搜索方案（Multi-keyword Ranked Search over Encrypted cloud data，MRSE），通過對索引向量和請求向量計算內(nèi)積得分對文檔進行排序，但對大量文檔而言，搜索計算量過大、耗時長，且精度不高。Saini 等［16］提出關(guān)鍵詞模糊搜索方案，通過構(gòu)造關(guān)鍵詞模糊集，以容忍用戶搜索時輸入拼寫錯誤與格式不一致的情況，但無法搜索與關(guān)鍵詞語義相關(guān)的文檔。Ahmed 等［17］通過使用加密動態(tài)索引以提高搜索效率，在加密數(shù)據(jù)集發(fā)生變化時能夠?qū)λ饕M行動態(tài)更新。Chen等［18］提出支持高效、動態(tài)多關(guān)鍵字排序搜索的方案，首先通過協(xié)調(diào)匹配獲得外包文件以查詢關(guān)鍵詞相關(guān)性，然后利用內(nèi)積相似性進行分析，最后采用塊稀疏對角矩陣與置換矩陣提高搜索速度。Fu 等［19］利用基于樹的索引結(jié)構(gòu)組織所有的文檔索引向量，提出一種新的基于概念層次與語義的搜索方案。該方案使用一臺服務(wù)器用于存儲外包數(shù)據(jù)集，并將排名結(jié)果返回給數(shù)據(jù)用戶，再使用另一個服務(wù)器計算文檔及查詢關(guān)鍵詞之間的相似性分數(shù)，并將分數(shù)發(fā)送到第一個服務(wù)器。

一些學者提出基于樹的搜索方案，Krishna 等［20］提出基于樹的排名搜索方案，通過二叉樹建立動態(tài)索引，以減少索引生成與查詢時間。Peng 等［21］利用雙線性映射構(gòu)建用加法順序與隱私保護函數(shù)族加密的基于樹的索引，云服務(wù)器通過合并這些索引，用深度優(yōu)先算法搜索文檔。黃新宇［22］基于分治思想為數(shù)據(jù)集構(gòu)建B+樹結(jié)構(gòu)的索引樹組，之后對對查詢向量進行分組并在相應(yīng)索引樹上進行檢索，在提高效率的同時降低了存儲開銷。陳垚等［23］提出一種基于優(yōu)先級排序的動態(tài)安全可搜索加密方案，首先采用預(yù)處理字典樹結(jié)構(gòu)提高搜索效率，然后通過對新添加的文件標識符進行加密，使動態(tài)更新算法的時間復(fù)雜度變?yōu)镺（1），最后增加自定義搜索結(jié)果排序功能，提高了搜索準確率。徐光偉等［24］注意到查詢關(guān)鍵詞與索引之間的關(guān)聯(lián)性，提出一種基于語義擴展的多關(guān)鍵詞可搜索加密算法，首先根據(jù)依存句法區(qū)分多關(guān)鍵詞并進行語義擴展，然后基于凝聚層次聚類與關(guān)鍵詞平衡二叉樹構(gòu)建索引關(guān)聯(lián)的索引樹，最后通過剪枝參數(shù)和相關(guān)性得分閾值過濾索引無關(guān)的子樹。

在MRSE 方案［14］的基礎(chǔ)上，本文提出一種新的云存儲環(huán)境中多關(guān)鍵詞加密排序搜索方法。首先從聚類后的文檔中提取關(guān)鍵詞，并將關(guān)鍵詞按所屬類別隨機排列構(gòu)成詞典，然后利用向量空間模型，根據(jù)詞典中的關(guān)鍵詞為每篇文檔建立特征較集中的向量索引。在此基礎(chǔ)上，通過對索引和查詢向量構(gòu)建標記，根據(jù)查詢關(guān)鍵詞的位置過濾掉大量無關(guān)文檔，從而減少搜索時間。最后，將索引向量按照關(guān)鍵詞所屬類別進行分組，以提高了索引加密速度。將加密后的索引上傳至云服務(wù)器，云服務(wù)器通過計算文檔組索引向量與組查詢向量的內(nèi)積，降序返回用戶所需的前θ個文檔。

本文的貢獻總結(jié)如下：①對聚類后的文檔提取關(guān)鍵詞，構(gòu)建特征集中的索引向量；②對索引和查詢向量構(gòu)建標記，根據(jù)查詢標記的位置過濾掉大量無關(guān)文檔；③對過濾后的索引向量分組加密，使每個加密密鑰的維度降低，從而提高搜索效率。

2 問題描述

2.1 系統(tǒng)模型

如圖1 所示，系統(tǒng)模型包括數(shù)據(jù)所有者、用戶和云服務(wù)器。這3 個實體和密文搜索方法組成一個系統(tǒng)模型，其中數(shù)據(jù)所有者和用戶是誠實可信的，云服務(wù)器是半可信的。

Fig.1 System model of encrypted search scheme圖1 加密檢索方案系統(tǒng)模型

（1）數(shù)據(jù)所有者：數(shù)據(jù)所有者首先根據(jù)文獻［25］中的方法將文檔聚類，然后提取所有類中的文檔關(guān)鍵詞生成詞典，據(jù)此為每一篇文檔建立索引向量，并對文檔進行加密，最后將加密后的文檔和索引上傳給云服務(wù)器。當需要修改數(shù)據(jù)時，重復(fù)以上過程。

（2）私有云服務(wù)器：私有云服務(wù)器用于存儲數(shù)據(jù)擁有者上傳的索引標記向量，之后與用戶發(fā)送過來的查詢標記向量進行匹配，將匹配度高的類的文檔標識符發(fā)送給公共云服務(wù)器。

（3）公共云服務(wù)器：公共云服務(wù)器為半可信服務(wù)器，用于存儲數(shù)據(jù)擁有者上傳的文檔索引和加密后的文檔集，并對用戶發(fā)送的陷門和私有云服務(wù)器發(fā)送的文檔標識符對應(yīng)索引向量執(zhí)行搜索操作，之后向用戶返回所需的前θ個文檔。

（4）用戶：用戶是數(shù)據(jù)使用者，當需要訪問某文檔時，則向數(shù)據(jù)所有者發(fā)送請求。收到數(shù)據(jù)所有者返回的密鑰后，根據(jù)檢索內(nèi)容生成陷門，并發(fā)送給云服務(wù)器。云服務(wù)器據(jù)此返回用戶檢索的相應(yīng)加密文檔，用戶再根據(jù)密鑰對文檔進行解密。

2.2 攻擊模型

在數(shù)據(jù)所有者、用戶、云服務(wù)器之間的通信過程中，攻擊者可攔截通信，從所攔截的信息中推導(dǎo)出額外信息。云服務(wù)器被認為是“誠實且好奇”的［26］，具體而言，云服務(wù)器會誠實地執(zhí)行指定操作，但同時也會試圖從文件、索引或陷門中獲取并分析隱私信息。在本研究中，僅要求云服務(wù)器知道加密后的數(shù)據(jù)文檔、索引及查詢陷門，而不知道具體密鑰。但由于云服務(wù)器是“好奇”的，會在搜索過程中學習更多信息，如查詢關(guān)鍵詞和加密文檔的信息，從而根據(jù)陷門與查詢關(guān)鍵詞的關(guān)聯(lián)性推導(dǎo)出加密密鑰。

根據(jù)云服務(wù)器獲取的信息數(shù)量，將服務(wù)器攻擊類別分成兩種：①已知密文：云服務(wù)器只知道加密信息，如加密后的數(shù)據(jù)集、索引以及陷門；②已知背景：云服務(wù)器可知道更多信息，如搜索請求（陷門）的關(guān)聯(lián)關(guān)系，或通過陷門與查詢結(jié)果推測查詢關(guān)鍵詞。

2.3 符號說明

本文使用的符號及其說明如表1 所示。

Table 1 Symbol description表1 符號說明

2.4 詞語解釋

關(guān)鍵詞詞典：根據(jù)文檔類別分別提取文檔關(guān)鍵詞，經(jīng)去重處理后按類別排列組成關(guān)鍵詞詞典。

向量空間模型：將所有文檔和搜索關(guān)鍵詞用向量表示，維度為關(guān)鍵詞詞典大小，向量中每一維的值為該位置關(guān)鍵詞得分。在加密搜索領(lǐng)域，通常采用詞頻tf和反詞頻idf表示該得分，其中詞頻是指關(guān)鍵詞在文檔中出現(xiàn)的頻率，頻率越高說明關(guān)鍵詞對該文檔越重要；反詞頻表示包含某關(guān)鍵詞的文檔數(shù)，反映該關(guān)鍵詞在整個數(shù)據(jù)集中的重要程度，文檔數(shù)越多說明關(guān)鍵詞對文檔的區(qū)分度越低。

文檔得分：文檔得分反映了查詢關(guān)鍵詞與文檔中關(guān)鍵詞之間的匹配程度，云服務(wù)器會計算文檔得分，并按照分數(shù)高低進行排序，之后返回搜索結(jié)果。當云服務(wù)器收到查詢請求q后，可用式（1）計算文檔Fij的得分［27］。

其中，|Fij|是文檔的歐幾里得長度，作為歸一化因子，計算公式為是文檔Fij中的關(guān)鍵詞，fi,j是關(guān)鍵詞wij在文檔Fij中的出現(xiàn)次數(shù)，是文檔Fij中包含的關(guān)鍵詞集合，m是文檔總數(shù)，fj是包含關(guān)鍵詞wij的文檔數(shù)。

3 云存儲環(huán)境中多關(guān)鍵詞加密排序搜索方法

以下將分為5 部分詳細介紹本文提出的云存儲環(huán)境中多關(guān)鍵詞加密排序搜索方案（Multi-Keyword Encrypted Sorting Search Method，MESM）。

3.1 詞典構(gòu)建

數(shù)據(jù)所有者首先根據(jù)文獻［25］中的方法提取文檔特征，并根據(jù)關(guān)鍵詞權(quán)重構(gòu)建相應(yīng)特征向量，然后利用kmeans算法［28］將m篇文檔分成k類。按類分別提取關(guān)鍵詞并去重，同一類關(guān)鍵詞由于相關(guān)性較強，可將這些關(guān)鍵詞按所屬類別隨機排列，令相關(guān)性較強的類間詞語排列在一起，繼而構(gòu)建大小為n=n1+n2…nk的關(guān)鍵詞詞典。其中，n是詞典中的關(guān)鍵詞總數(shù)，ni是第i類中的關(guān)鍵詞個數(shù)。

3.2 索引創(chuàng)建

第一步：創(chuàng)建索引與標記向量。計算詞典中每一維關(guān)鍵詞在每篇文檔中的詞頻得分，對于每一類文檔而言，通過向量空間模型將其中第i篇文檔表示為D′i=(di1,di2…din)T，其中dij是詞典中第j個詞在第i篇文檔對應(yīng)位置的詞頻。與創(chuàng)建索引向量類似，如果詞典中的關(guān)鍵詞在第i篇文檔中對應(yīng)位置的詞頻得分不為0，則標記該位置的值為1，最終得到標記向量Bφi∈{0,1}(n)，其中φ表示該標記向量所屬類別。

第二步：維度擴展。對D′i進行擴維，從n維擴到n+u+ 1 維，其中將第n+ 1 維到n+u維設(shè)置為任意隨機數(shù)εi，而將第n+u+ 1 維設(shè)置為常數(shù)1。擴維后第i篇文檔的索引向量Pi′= (,ε1,ε2…εu,1)。第三步：向量分組。將擴展后的向量Pi′按照每一維得分所在組的不同分為k+ 1 組，表示為(P′i1,P′i2…P′i(k+1))T，其中Pij′即為第j個組向量，其前k個組向量維度即是該組的關(guān)鍵詞數(shù)ni，而P′i(k+1)的維度為u+ 1。

第四步：生成密鑰。數(shù)據(jù)擁有者隨機生成2k個維度為ni×ni的 可 逆 矩 陣M11,M12…M1k和M21,M22…M2k，2 個(u+1) × (u+ 1)維的M1(k+1)、M2(k+1)以及1 個n+u+ 1 維的分割指示向量S。其中，u+ 1 是擴展維度，S∈{0,1}(n+u+1)。與前面Pi′的分組方法相同，將分割指示向量S也分成k+ 1組，最后表示為S= (S1,S2…Sk+1)，密鑰則表示為M1=(M11,M12…M1(k+1))和M2= (M21,M22…M2(k+1))。

第五步：隨機分割。根據(jù)指示向量S的每個組指示向量Si對索引向量Pi′的對應(yīng)組向量P′ij(j= 1,2…k+ 1)進行隨機分割，分割成分別表示為和對于該組第ω個位置上的值，分割規(guī)則如式（2）所示。

第六步：索引加密。用組密鑰M1i和M2i(i= 1,2…k+1)分 別對分割后的組索引i′j與i″j(j= 1,2…k+ 1)進行加密，第i篇文檔索引加密過程可分別表示為=2(k+1)}，整個加密結(jié)果表示為篇加密結(jié)果則表示為I= (I1,I2…Im)。最后，將加密文檔C 與加密索引I上傳到服務(wù)器。

3.3 陷門創(chuàng)建

步驟1：創(chuàng)建查詢與標記向量。用戶輸入查詢關(guān)鍵詞，根據(jù)關(guān)鍵詞詞典生成相應(yīng)查詢向量q=(q1,q2…qn)T。如果查詢關(guān)鍵詞與詞典中對應(yīng)位置的關(guān)鍵詞相匹配，則設(shè)置qi為該詞對應(yīng)的反詞頻，否則設(shè)置qi=0。與創(chuàng)建查詢向量類似，但將qi不為0 的值標記為1，得到標記向量b∈{0,1}(n)。

步驟2：維度擴展。首先對q進行維度擴展，從n維擴展到n+u+ 1 維，其中在第n+ 1 維到n+u維間任意選擇v維設(shè)置為1，其余設(shè)為0，然后將前n+u維數(shù)值乘以一個非零隨機數(shù)r，最后將第n+u+ 1 維設(shè)置為隨機數(shù)t，則擴展后的最終查詢向量表示為Q。

步驟3：查詢向量分組。將查詢向量Q分成k+ 1 個組向量Q1,Q2…Qk+!，其中Qi(i= 1,2…k)的維度是其所屬類別關(guān)鍵詞個數(shù)ni，而Qk+1的向量維度為u+ 1。

步驟4：隨機分割。根據(jù)指示向量S的每個組指示向量Si對查詢向量Q的組向量Qi進行隨機分割，分割成Q′i和，分 別 表 示 為。對于該組第?個位置上的值，分割規(guī)則如式（3）所示。

3.4 文檔篩選

對于數(shù)據(jù)擁有者上傳的索引標記向量Bφi∈{0,1}(n（)φ表示所屬類別），當用戶輸入查詢關(guān)鍵詞時，這些關(guān)鍵詞之間往往不會是完全無關(guān)的，由于其是對所需文檔的特征描述，因而這些詞的相關(guān)度較高，其查詢標記向量b∈{0,1}(n)的特征值也是集中的。根據(jù)標記向量之間的匹配，返回匹配度高的標記Bφi。

查詢標記與索引標記匹配過程如圖2 所示。假設(shè)文檔分類數(shù)為3，每類文檔數(shù)分別為2、3、2，關(guān)鍵詞詞典及標記向量維度為15。第2 類是有關(guān)云計算的文檔集，從中提取的關(guān)鍵詞可能包括cloud、computing、encrypted、search 等，這些詞將按順序排列在詞典中的特定位置，如詞典的最后，因此生成的索引標記1 也都會集中于最后一部分。當用戶輸入包括相關(guān)聯(lián)的如cloud、search 等多個查詢關(guān)鍵詞時，查詢標記向量b與第2 類文檔集的索引標記B21、B22、B32的匹配度更高，而最終需要返回的是前θ個相關(guān)性最高的文檔。所以對于匹配度較低的屬于第1、3 類的文檔，可將其過濾，從而避免對所有文檔進行不必要的得分計算，提高了搜索效率。

Fig.2 Matching process of query mark and index mark圖2 查詢標記與索引標記匹配過程

3.5 查詢

用戶將陷門T上傳給公共云服務(wù)器進行查詢，公共云服務(wù)器接收后將依次計算私有云服務(wù)器發(fā)送的文檔標識符Bφi對應(yīng)索引向量與陷門的內(nèi)積得分，之后根據(jù)內(nèi)積大小對其進行降序排列，將得分較高的前θ個加密文檔返回給數(shù)據(jù)使用者。內(nèi)積計算過程如式（4）所示。

4 性能分析

4.1 復(fù)雜度分析

隨著數(shù)據(jù)量的增加，關(guān)鍵字數(shù)量增多，生成的關(guān)鍵詞詞典也越大，導(dǎo)致索引的加密矩陣維度很高。而在MRSE方案中，加密矩陣維度直接取決于詞典大小，當詞典中關(guān)鍵詞個數(shù)為n、擴展維度為u+ 1 時，m 篇文檔的加密時間復(fù)雜度為O(m(n +u+ 1)2)。為降低加密矩陣維度，進一步減少加密時間，本方案將所有索引向量與查詢向量按其特征值所屬類別分成k+ 1 組，其加密時間復(fù)雜度可表示為故本方案的加密效率更高。

4.2 隱私分析

保證數(shù)據(jù)信息的安全性對于可搜索加密過程十分重要，在已知背景的攻擊模型下，本文從密鑰安全性、關(guān)鍵詞信息、查詢信息與陷門非關(guān)聯(lián)性保護幾方面進行安全性分析。

密鑰安全性：對于文檔集中的第i篇文檔，云服務(wù)器并不知道索引加密過程Ii={1,Pi″ M2}，其第j(j= 0,1…k+1)組向量的加密過程表示為和。設(shè)ωj為每組向量維度，其值為nj或u+ 1。云服務(wù)器不知道降維、分組及分割具體過程，對于加密后的組向量和，只能 建立式（5）：

其中，M1j、M2j各有個未知變量則各有ωj個未知變量。方程組（5）有2(+ωj)個未知數(shù)，而等式個數(shù)只有2ωj，方程組則會有無數(shù)個解，因而云服務(wù)器無法據(jù)此推出加密矩陣M1j和M2j。

關(guān)鍵詞信息保護：云服務(wù)器不知道詞典中的關(guān)鍵詞個數(shù)，通過分組可使得降維后的矩陣也是多變的，從而提高數(shù)據(jù)安全性。此外，在已知背景的攻擊模型下，為有效提高安全性，可引入系統(tǒng)參數(shù)w，保證索引向量至少有2w個不同的，使得擁有相同值的概率小于1 2w，不同的數(shù)量不大于u v，且在u/v= 2 時達到最大值?？紤]到Cvu≥(u/v)v，需設(shè)置u= 2w和v=w。εi還需滿足均勻分布N(μ′-c,μ′+c)，其均值為μ′，方差σ2=c2/3。為保證εv符合正態(tài)分布N(μ,σ2)，應(yīng)設(shè)置在正態(tài)分布中，標準差σ作為折中參數(shù)，σ較小時搜索精度較高，但是相對帶來的混淆較小，降低了安全性，因此需要合理地設(shè)置σ以獲得安全性與精度的平衡。

查詢信息與陷門非關(guān)聯(lián)性保護：為防止云服務(wù)器從陷門中推知用戶查詢信息，本方案對查詢向量進行特征集中、分組、擴展、隨機分割與加密處理，使查詢關(guān)鍵詞信息不會表現(xiàn)在查詢陷門中，從而保護了查詢信息。此外，由于隨機數(shù)的引入，使得不同甚至相同的查詢請求都會有不同得分，從而保護了陷門非關(guān)聯(lián)性。

4.3 實驗分析

本實驗使用RFC（Request For Comments）［14］數(shù)據(jù)作為實驗數(shù)據(jù)集，實驗環(huán)境為Windows 7 服務(wù)器，CPU 為英特爾酷睿i5（2.5GHZ）處理器。

影響實驗效率的主要因素是文檔數(shù)量m及詞典中的關(guān)鍵詞數(shù)量n(n=n1+n2…nk)，其決定了通過向量空間模型構(gòu)建的索引與查詢向量維度，從而決定了加密密鑰維度及最終的檢索效率。本實驗通過減少查詢文檔數(shù)量以及降低加密維度兩方面解決該問題，以下將分別分析MESM 方案得到的結(jié)果，并與MRSE 方案結(jié)果作對比。實驗結(jié)果如圖3-圖6 所示，其中MESM-5、MESM-7、MESM-9、MESM-6 000 分別表示分組數(shù)為5、7、9 及文檔數(shù)為6 000 時MESM方案的實驗結(jié)果。

隨著文檔數(shù)量的增加，生成的關(guān)鍵詞詞典也越大，通過向量空間模型構(gòu)造的查詢向量和索引向量維度也就越高，導(dǎo)致加密的時間復(fù)雜度提升。為此，可將索引與查詢向量按其特征值所屬類別進行分組，從而降低了加密密鑰維度。如圖3 所示，對于MRSE 方案和分組數(shù)分別為5、7、9的MESM 方案，當文檔數(shù)從1 000 增加到6 000 時，陷門生成時間持續(xù)增加，這是因為生成陷門的索引向量和加密密鑰維度增加，但文檔數(shù)量相同時，MESM 方案所用時間少于MRSE 方案。如文檔數(shù)為6 000，分組數(shù)為5、7、9 的MESM方案陷門生成時間分別為2.4s、2.1s、1.8s，而MRSE 方案為2.9s。

Fig.3 Variation of trapdoor generation time with increasing number of documents in different groups圖3 不同分組時陷門生成時間隨文檔數(shù)量的變化

Fig.4 Change of trapdoor generation time with different number of groups圖4 陷門生成時間隨分組數(shù)的變化

Fig.5 Change of query time with different number of documents圖5 查詢時間隨文檔數(shù)量的變化

圖4 為MESM 方案在文檔數(shù)為1 000～4 000，分組數(shù)從2增加到9 時的陷門生成時間。從圖中可以看出，在文檔數(shù)一定時，陷門生成時間將隨著分組數(shù)的增加而減少。如當文檔數(shù)為4 000 時，分組數(shù)為2、9 時的陷門生成時間分別為1.85s 和1.5s，減少了近20%。隨著分組數(shù)的增加，陷門生成時間會進一步減少，加密效率會更高。

通過對相關(guān)性強的詞進行聚類，然后將索引標記向量與查詢標記向量進行匹配，以過濾相關(guān)度低的文檔，對這些文檔不再計算得分，從而減少了檢索時間，提高了檢索效率。如圖5 所示，隨著文檔數(shù)從1 000 增加到6 000，MRSE 方案的查詢時間從0.7s 增加到6.3s，近似一次系數(shù)增長，而MESM 方案在分組數(shù)為5、7、9 時，查詢時間均遠少于前者。其中，當分組數(shù)為9 時，查詢時間僅從0.3s 增加到3.3s，查詢效率提高了近一倍。當文檔數(shù)量一定時，MESM方案的查詢時間均少于MRSE 方案，如文檔數(shù)為6 000，分組 數(shù) 為5、7、9 的MESM 方 案 查 詢 時 間 分 別 為4.4s、3.8s、3.3s，而MRSE 方案為6.2s。隨著分組數(shù)的增加，查詢效率會進一步提升。

圖6 為在查詢關(guān)鍵詞相同而返回文檔數(shù)不同的情況下，6 000 篇文檔在分組數(shù)為9 時的MESEM 方案與MRSE 方案查詢精度變化情況。

Fig.6 Change of query accuracy with different number of returned documents圖6 查詢精度隨返回文檔數(shù)的變化

在計算前θ個與查詢關(guān)鍵詞匹配度最高的文檔得分時，通過標記向量過濾掉很多相關(guān)性弱的文檔，但由于聚類時的偏差以及用戶輸入查詢關(guān)鍵詞的差異性，可能導(dǎo)致查詢結(jié)果并不都符合查詢要求。本實驗通過公式（6）計算查詢結(jié)果精度。

其中，β表示返回的文檔數(shù)量，α表示包含查詢關(guān)鍵詞的文檔。設(shè)置返回文檔數(shù)從10 增加到50，MRSE 方案查詢精度在0.76～0.8 之間，相比之下，MESM 方案精度略低，在0.7～0.72 之間，但還是比較穩(wěn)定。

5 結(jié)語

本文提出一種云存儲環(huán)境中多關(guān)鍵詞加密排序搜索方法——MESM，首先對關(guān)鍵詞進行聚類，使相關(guān)性強的詞排列在一起，并獲得特征較集中的索引向量；然后對索引與查詢向量進行標記處理，根據(jù)查詢向量中的特征位置匹配相應(yīng)索引向量，從而過濾掉無關(guān)文檔，提高搜索效率；最后對向量按其特征所屬類別進行分組，降低了加密密鑰維度，減少了加密時間。實驗結(jié)果表明，本文提出的MESM 方案是可行的，在相同條件下，MESM 方案的查詢效率高于MRSE 方案。在下一步研究中，將主要致力于解決用戶輸入關(guān)鍵詞相關(guān)度差異帶來的查詢精度下降問題。