云存儲環境中多關鍵詞加密排序搜索方法研究

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

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

0 引言

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

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

1 相關工作

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

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

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

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

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

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

2 問題描述

2.1 系統模型

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

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

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

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

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

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

2.2 攻擊模型

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

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

2.3 符號說明

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

Table 1 Symbol description表1 符號說明

2.4 詞語解釋

關鍵詞詞典：根據文檔類別分別提取文檔關鍵詞，經去重處理后按類別排列組成關鍵詞詞典。

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

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

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

3 云存儲環境中多關鍵詞加密排序搜索方法

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

3.1 詞典構建

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

3.2 索引創建

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

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

第四步：生成密鑰。數據擁有者隨機生成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))。

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

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

3.3 陷門創建

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

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

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

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

3.4 文檔篩選

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

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

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

3.5 查詢

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

4 性能分析

4.1 復雜度分析

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

4.2 隱私分析

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

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

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

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

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

4.3 實驗分析

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

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

隨著文檔數量的增加，生成的關鍵詞詞典也越大，通過向量空間模型構造的查詢向量和索引向量維度也就越高，導致加密的時間復雜度提升。為此，可將索引與查詢向量按其特征值所屬類別進行分組，從而降低了加密密鑰維度。如圖3 所示，對于MRSE 方案和分組數分別為5、7、9的MESM 方案，當文檔數從1 000 增加到6 000 時，陷門生成時間持續增加，這是因為生成陷門的索引向量和加密密鑰維度增加，但文檔數量相同時，MESM 方案所用時間少于MRSE 方案。如文檔數為6 000，分組數為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 不同分組時陷門生成時間隨文檔數量的變化

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

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

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

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

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

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

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

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

5 結語

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