安全云環境中一種改進的多關鍵字檢索方案

郭 秋 滟

安全云環境中一種改進的多關鍵字檢索方案

郭 秋 滟

(西昌學院汽車與電子工程學院 四川 西昌 615013)

為了降低硬件購置成本，許多機構傾向于使用穩健快速的云服務將他們的數據轉包出去。然而，外包數據可能含有需要防護的敏感數據，而云提供商并不能可靠地滿足這一要求。因此，必須采取防護措施，以保護敏感數據不受到云服務器和其他未授權機構的破壞。針對該問題，提出一種基于minhash函數的高效加密云數據隱私保護多關鍵字檢索方法。該方法根據數據所有者生成并外包給云服務器的加密可檢索索引進行加密云檢索。已知檢索內容后，服務器采用tf-idf加權法將檢索內容與可檢索索引相比較，除了鑒于隱私因素可被泄露的信息外，不需其他信息即可返回結果。基于公開的Enron數據集的仿真實驗結果表明， 該方法可保證用戶只會檢索到最相關的條目，不會對用戶造成不必要的通信和計算負擔。另外，在檢索精度方面，也要優于現有的方法。

云服務 minhash函數 隱私保護 檢索 tf-idf加權法 檢索精度

0 引 言

隨著存儲和通信要求不斷提高，當今機構傾向于將他們的可檢索數據外包給遠程服務器。云可以為各數據存儲及數據處理要求提供高效且高性價比的解決方案。然而，外包數據可能含有需要防護的敏感數據。這一要求非常關鍵，而云提供商并不能可靠滿足這一要求。因此，必須采取防護措施，以保護敏感數據不受到云服務器和其他未授權機構的破壞。

對遠程數據最重要的操作之一就是數據檢索。檢索操作不僅應該保護用戶和數據的隱私，還應該非常高效。正是因為隱私極其重要，最近幾年人們對可以保護隱私的檢索方法進行了廣泛研究。這些研究主要關注單關鍵字檢索[1,2]，很少有研究提出多關鍵字解決方案[3,4]。鑒于數據集規模較大，單關鍵字檢索往往匹配大量數據條目但只有少量條目相關。此外，用戶需要進行多次檢索，選擇相應結果的交集，對用戶的計算量和時間造成了嚴重負擔。多關鍵字檢索可以在一次檢索中集成多個關鍵字，通過增加檢索約束，只有最相關的條目返回給用戶，降低了用戶的計算負擔。因此，本文提出一種新的全面高效的多關鍵字檢索方法，把匹配數據經過排序后返回給用戶。

本文貢獻包括多個方面。首先，提出一種新的基于minhash的隱私保護多關鍵字檢索方法，且準確率較高。其次，使用了一種基于關鍵字字匯頻率和文件逆向頻率(tf-idf)的排序方法。最后，利用公開的Enron數據集驗證了本文方法的有效性。

1 相關工作

先前已有眾多文獻對隱私和防護關鍵字檢索進行了研究。相關研究可分為兩類：單關鍵字檢索和多關鍵字檢索。

在單關鍵字檢索中，孔凡新等[5]為支持加密云數據高效隱私的密文查詢，提出了一種基于訪問記錄的密文排序函數，以過去推測現在，提高了數據查詢準確性。Ogata等[6]基于RSA blind簽名提出一種隱私防護檢索協議。因為該協議的用戶需要對每個數據庫條目的公開密鑰進行繁雜的操作，所以該方法的實用性不強。Raykova等[7]提出一種基于重新路由加密協議的解決方案，他們在用戶和服務器之間引入一種新客戶端，稱為檢索路由器(QR)。用戶通過該QR把檢索發送給服務器，以保護其相對服務器的匿名性。通過機密性(即加密)實現用戶信息相對QR的安全性。以上介紹的所有方法均只能進行單關鍵字檢索。然而，在對加密云數據進行檢索時，被外包的數據集規模往往較大，單關鍵字檢索必然會返回大量匹配結果，而其中大部分結果均與用戶無關。

多關鍵字檢索可支持對檢索施加多個約束，使用戶只訪問最相關的數據。在多關鍵字檢索中，程芳權等[8]提出了一種隱私保護的高效密文排序查詢方法RQED。通過設計無證書認證的PKES(支持關鍵字檢索的公鑰加密)，并構建RQED框架來實現強隱私保護的密文查詢。基于該框架，設計了更合理的多屬性多關鍵字密文查詢排序函數，并提出了基于層次動態布隆過濾器的RQED索引機制，提高了密文查詢時空效率。李倩等[9]提出了支持多關鍵字查找的安全高效的云計算方案。該方案基于二叉排序樹結構，把關鍵字映射為固定長度的二進制數組，在保證用戶數據的安全和隱私的前提下，支持授權用戶對文件的多關鍵字查詢，讓用戶可以隨時隨地享受多關鍵字查詢服務。Cao等[4]提出另一種多關鍵字檢索方法，將可檢索數據庫索引編碼為兩個二進制矩陣，并在匹配過程中使用內積相似性。該方法需要索引中的關鍵字段，這意味著，用戶必須知道所有合法關鍵字的列表及其位置作為強制信息，以生成一次檢索。該假設在多種情況下均不可行。Chen等[10]提出了基于雙線性配對的隱私防護多關鍵字檢索解決方案。然而，基于配對方案導致較高的服務器和用戶計算成本。此外，這些方案不能為用戶的訪問或檢索模式提供隱私保護。因此，基于配對的解決方案在許多情況下不具有可行性。鑒于此，本人在已有研究工作的基礎上，提出了一種改進的面向隱私保護的多關鍵字檢索方法，并通過仿真實驗驗證了該方法的有效性。

2 基本理論

隱私防護檢索的主要問題就是檢查條目的相似性。本文利用minhashing技術[11]來約簡敏感性數據與給定加密檢索的相似性。我們還利用信息系統中的部分指標來估計匹配結果的相關性排序，并分別給出這些技術的定義和基本內容。

2.1 minhashing

在本文中，每個文檔用簽名來表示。簽名是一個小型集合，其中的每個元素可由Minhash函數構造。

定義1 minhash函數：設Δ表示元素有限集，P表示Δ的排列，P[i]表示P的第i個元素。在排列P條件下集合D?Δ的Minhash定義為：

(1)

在本文方法中，對每個簽名使用關于Δ的λ個不同隨機排列，于是集合D的最終簽名為：

Sig(D)={hP1(D),…,hPλ(D)}

(2)

其中，hPj為排列Pj條件下的minhash函數。

2.2 相關性指數

為了根據相對于檢索的相關性對匹配結果進行排序，需要一個相似性函數。該函數為與給定檢索對應的每個匹配結果分配一個相關性指數。

信息檢索常用的加權因子為tf-idf加權[12]。直觀地講，它可衡量文件內檢索條目對于數據庫集合的重要性。本文使用tf-idf加權方案計算每個文件內每個檢索條目的權重。該方案利用條目頻率(tf)和文件逆向頻率(idf)信息指定一個合成權重。文件D檢索條目w的tf-idf權重為：

tf-idfw,D=tfw,D×idfw

(3)

其中，tf是關鍵字在文件中出現的次數，idf為檢索條目在數據庫集合中的稀有性。

3 總體框架

本文主要研究數據庫外包場景下針對加密云數據的隱私保護關鍵字檢索。在該場景下，我們假設數據所有者沒有充足的資源或不愿存儲整個數據庫。他把數據外包給可靠性和可信度均較低的服務器，但在檢索時仍然可以保證在訪問和檢索模式外不泄露其他數據。數據所有者對將被外包的敏感性文件進行加密，并利用這些敏感性文件中的特征集生成安全的可檢索指數。在離線階段，可檢索指數和加密文件均被外包給可信任云。經過授權的用戶利用可檢索指數來檢索云，并接收與他們的檢索相匹配的加密文件。在這一過程中，云服務器除了數據所有者允許泄露的數據外不該獲知其他數據。最后，用戶使用解密密鑰對接收到的文件解密。

本文方法的總體框架描述如下。設D表示敏感性文件集合，Fi表示Di∈D的特征集(即關鍵字)。框架包括4個子算法：配置、指數生成、檢索生成和檢索。

(1)Setup(Ψ)：已知安全參數Ψ，生成一個密鑰K∈{0,1}Ψ。

(2)IndexGeneration(K,D)：已知敏感文件集合D，它可提取每個文件Di∈D的特征集Fi，通過密鑰K加密來生成一個可檢索安全索引L。

(3)QueryGeneration(K,F)：用密鑰K，為已知特征集F生成檢索Q。

(4)Search(L,Q)：檢索Q和可檢索索引L做比較，返回匹配文件Di的加密版本Ci。

算法詳細內容見第4節。下面先給出文中將要用到的定義及其涵義。

定義2 檢索模式(Sp)：表示被檢索的檢索內容的頻率，通過檢查兩次檢索的等價性便可確定檢索模式。正式地講，設{Q1,Q2,…,Qn}表示由n個連續檢索構成的集合，Fi表示Qi的特征集，檢索模式Sp表示為一個n×n二進制矩陣且Sp(i,j)=1?Qi=Qj。

定義4 訪問模式(Ap)：表示包括用戶檢索結果的數據標志符集合。設Fi表示Qi的特征集，R(Fi)表示與特征集Fi相匹配的數據元素的標識符集合，于是有Ap=R(Fi)。

定義5History(Hn)。設D表示數據集中的文件集合，Q={Q1,Q2,…,Qn}表示由n個連續檢索構成的集合。n-檢索歷史定義為Hn(D,Q)。

定義7View(v)：表示可被對手訪問的信息。設L表示安全的可檢索索引，id(Ci)和Q定義如上。Hn的視角定義為v(Hn)={(id(C1),…,id(Cl)),C,L,Q}。

4 本文方法

本節給出本文方法的關鍵步驟。根據數據所有者生成并外包給云服務器的加密可檢索索引進行加密云檢索。已知檢索內容后，服務器將檢索內容與可檢索索引相比較，除了鑒于隱私因素可被泄露的信息外，不需其他信息即可返回結果。

4.1 安全的索引生成

在該步驟中，我們利用2.1節的minhash函數和桶分組技術[13]把每個對象分到多個桶中，桶ID作為桶中每個對象的標識符。這種方法將對象映射后，當這些對象間的相似度上升時，兩個對象發生沖突的桶數量將會上升。即當所有箱中相同的對象發生沖突時，如果對象間的差異度上升，則公共桶數量下降。數據所有者通過如下階段生成安全索引：特征提取、桶索引構建、桶索引加密。

(1) 特征提取 對每個文檔Di∈D，提取可以刻畫文檔特征的特征集Fi={fi1,…,fiz}。在本文中，這些特征由兩個數值fij=(wij,rsij)構成。第1個數值為敏感性文件的關鍵字wij，第2個數值是相關性指數(rs)。如2.2節所示，該指數基于文件Di關鍵字wij的tf-idf值。在對匹配結果進行排序時的檢索方法將會用到該相關性指數。

(4)

設max表示可能出現于索引中的桶最大數量，cnt為索引中桶的真正數量，我們向索引中加入max-cnt個虛擬元素，以隱藏桶的數量。可在如下條件下隨機生成虛擬元素(πdumi,Vdumi)：

算法1總結了安全索引生成方法。

算法1 索引生成

要求：Δ：可能的關鍵字組成的集合，D：文檔集合，h：λ個Minhash函數，Ψ：安全參數

Kid=Setup(Ψ),Kcontent=Setup(Ψ)

For所有的Di∈Ddo

Fi←提取Di的特征

Forj=1→λdo

Endif

Endfor

Endfor

Endfor

添加max-cnt個虛擬元素(πdumi,Vdumi)

返回L

在索引生成之后，數據擁有者將數據集D中的每個文檔加密為Ωid(Di)=EncKdata(Di)，并利用L把該加密文件集合EDoc外包給服務器，且：

4.2 檢索生成

4.3 安全檢索

4.4 文件檢索

用戶需要避免返回不相關的文檔，因為這會迅速導致不必要的通信負擔。因此，用戶往往只檢索最前面的t個匹配，而不是在檢索時返回至少個桶的所有文檔。本文使用tf-idf數值對匹配結果進行排序。接收到加密向量EV={V1,…,Vλ}時，用戶解密這些向量，獲得的明文向量為Vi=DecKcontent(Vi)。然后，根據其指數對文件排序。請注意，Vi[id(Dj)]表示第i個桶文檔Dj的tf-idf值。

在索引生成階段，利用minhash函數的輸出把每個文件映射到一定數量的桶內，minhash輸出的tf-idf值設置為該桶該文檔的相關性指數。類似地，檢索Q也映射到部分桶內，文檔Dj的指數(即score(id(Dj)))為文檔和檢索共享的桶的相關性指數之和，定義為：

(5)

當score(id(Dj))較大時，文檔相對檢索的相關性也將上升。排序階段過后，用戶從服務器檢索到最前面的t個區域。文件檢索方法總結于算法2中。

算法2 文檔檢索

用戶：

要求：EV：經過加密的向量，Kcontent：密鑰，t：將被檢索的文檔數量約束

For 所有的Vi∈EVdo

Vi←DecKcontent(Vi)

End for

End for

對指數列表排序

idlist←最前面的t個指數的標識符

把idList發送給服務器

服務器：

要求：idlist：被請求的文檔標識符，EDoc：被外包且經過加密的文檔

For 所有的id∈idlist do

If (id,Ωid)∈EDocthen

向用戶發送(id,Ωid)

End if

End for

用戶：

Did←DecKcontent(Ωid)

5 雙服務器檢索

本文方法可能會將加密檢索與相應匹配文檔的標識符關聯起來，為了防止這一關聯現象，我們引入稱為文件服務器的第2臺服務器。該服務器并不會與之前稱為檢索服務器的初始服務器進行合作。當檢索服務器為給定檢索返回加密向量時，將從文件服務器獲得經過加密的文檔。通過這種策略，檢索服務器不會知道被檢索出來的文檔的標識符，文件服務器不會知道檢索內容。因此，如果假設兩臺服務器沒有串通合作，便不會發生檢索與相應文檔標識符相關聯這一現象。

有了兩臺服務器后，也可以利用這兩臺服務器為用戶執行其他操作。第4.4節描述的文檔檢索階段與用戶能力有關，可能會給用戶帶來沉重負擔。用戶在解密檢索出來的加密向量后，應該計算所有文檔標識符的指數并對指數排序。與服務器不同的是，用戶使用的設備可能對資源存在約束。為了減輕用戶負擔，可以使用文件服務器來對匹配文檔標識符的指數進行排序。

文件服務器獲得了匹配的Paillier加密桶內容向量，并對結果解密。然后，對指數排序，與前t個相似性指數匹配的項目被發送給用戶。通過這種方法，用戶的所有計算負擔都轉移給了服務器，但是此時會增加經過加密的桶內容向量的尺寸。在單服務器方法中，向量的每個元素為一個32比特的整數，而在雙服務器方法中，每個元素是「log2n2?比特的密文，其中n表示兩個較大素數的倍數。然而，這一向量只會在兩臺具有大量通信和計算資源的服務器間轉移。所以，這一策略不會增加用戶的通信成本。算法3給出了雙服務器檢索方法。

算法3 雙服務器安全檢索和文檔檢索

檢索服務器：

要求：L：安全索引，Q：檢索，n個Paillier模塊，t：將被檢索的文檔數量約束

For所有πi∈Qdo

If(πi,{ei1,…,eil})∈Lthen

Enc(score(j))←Enc(score(j))·eij

Endif

Endfor

向文件服務器發送(j,Enc(score(j)))和t

文件服務器：

要求：Kcontent：密鑰，Kpriv：Paillier密鑰

For所有ido

score(i)=DecKpriv(Enc(score(i)))

Endfor

對所有指數排序

發送與最前面的t個指數相對應的加密文檔

6 仿真實驗

在本文中，我們采用matlab 2012進行仿真實驗，實驗平臺為32位Win7，2.30 GHz Intel Pentium Dual-Core處理器，使用公開的Enron數據集[15]作為測試對象。使用精度和召回指標來分析檢索方法的性能。設R(F)表示特征集為F的被檢索項目集合，R*(F)表示R(F)的子集，于是R*(F)的元素包括F中的所有特征。此外，假設D(F)表示包括F中所有特征的項目集合。請注意，R*(F)?R(F)且R*(F)?D(F)。對于集合F={F1,…,Fn}，精度prec(F)、召回rec(F)、平均精度aprec(F)、平均召回arec(F)的定義如下：

(6)

(7)

根據相關性指數(見2.2節)對匹配項目排序，只有指數最高的前t個項目被檢索。我們將閾值固定為t=15，特征數量范圍設為2～6個，對150次檢索取均值(即每單位尺寸的特征有300次檢索)，來分析minhash函數(λ)對算法精度的影響。如圖1所示，對任何λ≥150，本文方法的召回指標為1，表明在給定檢索中，包含所有特征的所有項目均被用戶檢索到。對于我們考慮的數據庫外包場景，用戶必須獲得與被檢索的特征集相匹配的所有文檔，這一點非常重要。精度指標非常低，表明被獲得的文檔中約有40%包括所有被檢索的特征。然而，獲得的其他項目仍然與檢索相關。這些項目只包括部分檢索特征，匹配的特征的相關性指數較高，表明即使沒有匹配所有的特征，匹配的項目與檢索仍然具有較高的相關性。請注意，與檢索沒有任何特征匹配的項目的相關性指數為0，因此無法與檢索匹配。因為它可以在保證完美召回效果的同時滿足最優精度，所以我們設置λ=150。

圖1 t=15且λ變化時的成功率

我們進一步分析了檢索中關鍵字數量對精度和召回率的影響，并在圖2中給出結果。當公共關鍵字數量上升時，檢索和文檔簽名間的相似性也將上升。因此，當檢索中的關鍵字數量上升時，本文方法的精度和召回率都會上升。成功率的上升表明，當關鍵字數量超過5個時，本文方法的效果更優。

圖2 檢索中包含的關鍵字數量和t對精度(a)和召回率(b)的影響

另外，我們通過改變數據集尺寸(4000到10 000個文檔)來評估本文方法的效率。本文方法成本最高的操作就是索引生成。圖3表明，索引生成步驟需要數分鐘時間，且當文檔數量上升時呈線性增長。考慮到這一操作由數據所有者離線操作，因此不影響本文方法的實用性。隱私保護檢索策略的最重要參數之一就是檢索響應時間，因為用戶使用這一操作的頻率很高，而且用戶希望盡快訪問到他們的檢索結果。檢索操作與文檔數量無關，因為在本文方法中總是通過檢索λ個被請求的桶來執行檢索操作的。對于數量集為數百萬份文檔的大型數據集來說，這一特征尤其重要。λ=150時單服務器檢索方法的平均檢索響應時間為210ms，且與數據集文檔數量無關。

圖3 λ=150時的索引構建時間

為了更好地體現本文方案的優越性，將本文方案與目前較為典型的多關鍵字檢索方案RQED[8]和PPMKS[9]在檢索精度方面進行了對比，實驗結果見圖4所示。可以看到，本文方案的檢索精度始終要優于PPMKS。當關鍵字數目較少時，本文方法的性能和RQED基本一致，當關鍵字數目大于4時，本文方法的性能要優于RQED。仔細分析其原因可知，這是因為本文方案綜合采用了minhashing技術和為tf-idf加權方法來為與給定檢索對應的每個匹配結果分配一個相關性指數，隨著指定的關鍵字數目的增加，文檔中可以利用的特征數量更多，索引桶的構建也更加精確，因此取得了更好的結果。

圖4 不同方案的檢索精度比較

最后，我們還將本文方案與RQED和PPMKS在檢索效率方面進行了比較，結果見圖5所示。可以看到，本文方案和RQED的檢索效率要遠遠優于PPMKS。另外，當關鍵字數目小于6個時，本文方案的效率接近于RQED，而當關鍵字數目超過6個后，本文方案的效率漸漸地超過了RQED。這是由于RQED采用多屬性多關鍵字密文查詢排序函數進行檢索，當關鍵詞數目較多時，必然會造成效率的下降。而本文方案在檢索過程中，除了鑒于隱私因素可被泄露的信息外，不需其他信息即可返回結果，避免了對用戶造成不必要的通信和計算負擔，因此效率更高。

圖5 不同方案的檢索效率比較

7 結 語

在本文中，我們研究了數據庫外包場景下的加密云數據隱私保護多關鍵字檢索方法。提出了一種新的基于minhash函數檢索方法，對文檔簽名和檢索內容進行高效比較。利用基于tf-idf的相關性排序策略，使本文方法具有排序功能。該方法可保證用戶只會檢索到最相關的條目，防止對用戶造成不必要的通信和計算負擔。部署了整個系統，并利用公開Enron數據集通過全面的仿真實驗證明了本文方法的有效性。

[1] Wang C,Cao N,Li J,et al.Secure ranked keyword search over encrypted cloud data[C]//ICDCS’10,2010:253-262.

[2] Kuzu M,Islam M S,Kantarcioglu M.Efficient similarity search over encrypted data[C]//Proceedings of the 2012 IEEE 28thInternational Conference on Data Engineering,ser.ICDE ’12,2012:1156-1167.

[3] Orencik C,Savas E.Efficient and secure ranked multi-keyword search on encrypted cloud data[C]//Proceedings of the 2012 Joint EDBT/ICDT Workshops.ACM,2012:186-195.

[4] Cao N,Wang C,Li M,et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]//IEEE INFOCOM,2011:456-465.

[5] 孔凡新,劉麗.云環境下的隱私保護密文排序查詢[J].計算機工程與設計,2014,35(1):47-50.

[6] Ogata W,Kurosawa K.Oblivious keyword search[J].Journal of Complexity,2004,20(3):356-371.

[7] Raykova M,Vo B,Bellovin S M,et al.Secure anonymous database search[C]//Proceedings of the 2009 ACM workshop on Cloud computing security,ser.CCSW 2009,ACM,2009:115-126.

[8] 程芳權,彭智勇,宋偉,等.云環境下一種隱私保護的高效密文排序查詢方法[J].計算機學報,2012,35(11):2215-2226.

[9] 李倩,岳風順,王國軍.安全云存儲中高效的多關鍵字查找方案[J].計算機科學,2012,39(12):159-161.

[10] Chen Z,Wu C,Wang D,et al.Conjunctive keywords searchable encryption with efficient pairing,constant ciphertext and short trapdoor[C]//PAISI,2012:176-189.

[11] Rajaraman A,Ullman D,Jeffrey.Mining of massive datasets[M].Cambridge University Press,2011.

[12] Christopher H S,Manning D,Prabhakar Raghavan.Introduction to Information Retrieval[M].Cambridge University Press,2008.

[13] Hore B,Mehrotra S,Canim M,et al.Secure multidimensional range queries over outsourced data[J].The VLDB Journal,2012,21(3):333-358.

[14] Cramer R,Shoup V.Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[C]//Advances in Cryptology—Eurocrypt 2002.Springer Berlin Heidelberg,2002:45-64.

[15] Keila P S,Skillicorn D B.Structure in the Enron email dataset[J].Computational & Mathematical Organization Theory,2005,11(3):183-199.

AN IMPROVED MULTI-KEYWORD SEARCH SCHEME IN SECURE CLOUD ENVIRONMENT

Guo Qiuyan

(SchoolofAutomotiveandElectronicEngineering,XichangCollege,Xichang615013,Sichuan,China)

In order to reduce the purchase cost of hardware, many organisations tend to outsource their data utilising robust and fast services of clouds. However, the outsourced data may contain sensitive information that needs to be hidden. With which the cloud providers are not necessarily trusted. Therefore, some precautions are required to protect the sensitive data from being destroyed by both the cloud server and any other non-authorised party. To solve this problem, in this paper we propose a minhash function-based efficient privacy-preserving and multi-keyword search method over encrypted cloud data. Search over encrypted cloud is performed through an encrypted searchable index that is generated by the data owner and outsourced to a cloud server. Given a querying content, by the weighted method of tf - idf, the server compares the content with the searchable index and returns the results without learning anything other than the information that is allowed to be leaked due to privacy factors. Results of simulative experiment based on open Enron data sets show that, this approach ensures that only the most relevant items are retrieved by the user with no unnecessary communication and computation burden on the user. In addition, the proposed method is better than the existing method in terms of the retrieval accuracy.

Services of clouds minhash functions Privacy-preserving Search The weighted method of tf-idf Retrieval accuracy

2014-07-19。郭秋滟，講師，主研領域：云計算，算法理論。

TP391

A

10.3969/j.issn.1000-386x.2016.04.025