安全云環(huán)境中一種改進(jìn)的多關(guān)鍵字檢索方案

郭 秋 滟

安全云環(huán)境中一種改進(jìn)的多關(guān)鍵字檢索方案

郭 秋 滟

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

為了降低硬件購(gòu)置成本，許多機(jī)構(gòu)傾向于使用穩(wěn)健快速的云服務(wù)將他們的數(shù)據(jù)轉(zhuǎn)包出去。然而，外包數(shù)據(jù)可能含有需要防護(hù)的敏感數(shù)據(jù)，而云提供商并不能可靠地滿(mǎn)足這一要求。因此，必須采取防護(hù)措施，以保護(hù)敏感數(shù)據(jù)不受到云服務(wù)器和其他未授權(quán)機(jī)構(gòu)的破壞。針對(duì)該問(wèn)題，提出一種基于minhash函數(shù)的高效加密云數(shù)據(jù)隱私保護(hù)多關(guān)鍵字檢索方法。該方法根據(jù)數(shù)據(jù)所有者生成并外包給云服務(wù)器的加密可檢索索引進(jìn)行加密云檢索。已知檢索內(nèi)容后，服務(wù)器采用tf-idf加權(quán)法將檢索內(nèi)容與可檢索索引相比較，除了鑒于隱私因素可被泄露的信息外，不需其他信息即可返回結(jié)果?；诠_(kāi)的Enron數(shù)據(jù)集的仿真實(shí)驗(yàn)結(jié)果表明， 該方法可保證用戶(hù)只會(huì)檢索到最相關(guān)的條目，不會(huì)對(duì)用戶(hù)造成不必要的通信和計(jì)算負(fù)擔(dān)。另外，在檢索精度方面，也要優(yōu)于現(xiàn)有的方法。

云服務(wù) minhash函數(shù) 隱私保護(hù) 檢索 tf-idf加權(quán)法 檢索精度

0 引 言

隨著存儲(chǔ)和通信要求不斷提高，當(dāng)今機(jī)構(gòu)傾向于將他們的可檢索數(shù)據(jù)外包給遠(yuǎn)程服務(wù)器。云可以為各數(shù)據(jù)存儲(chǔ)及數(shù)據(jù)處理要求提供高效且高性?xún)r(jià)比的解決方案。然而，外包數(shù)據(jù)可能含有需要防護(hù)的敏感數(shù)據(jù)。這一要求非常關(guān)鍵，而云提供商并不能可靠滿(mǎn)足這一要求。因此，必須采取防護(hù)措施，以保護(hù)敏感數(shù)據(jù)不受到云服務(wù)器和其他未授權(quán)機(jī)構(gòu)的破壞。

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

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

1 相關(guān)工作

先前已有眾多文獻(xiàn)對(duì)隱私和防護(hù)關(guān)鍵字檢索進(jìn)行了研究。相關(guān)研究可分為兩類(lèi)：?jiǎn)侮P(guān)鍵字檢索和多關(guān)鍵字檢索。

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

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

2 基本理論

隱私防護(hù)檢索的主要問(wèn)題就是檢查條目的相似性。本文利用minhashing技術(shù)[11]來(lái)約簡(jiǎn)敏感性數(shù)據(jù)與給定加密檢索的相似性。我們還利用信息系統(tǒng)中的部分指標(biāo)來(lái)估計(jì)匹配結(jié)果的相關(guān)性排序，并分別給出這些技術(shù)的定義和基本內(nèi)容。

2.1 minhashing

在本文中，每個(gè)文檔用簽名來(lái)表示。簽名是一個(gè)小型集合，其中的每個(gè)元素可由Minhash函數(shù)構(gòu)造。

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

(1)

在本文方法中，對(duì)每個(gè)簽名使用關(guān)于Δ的λ個(gè)不同隨機(jī)排列，于是集合D的最終簽名為：

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

(2)

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

2.2 相關(guān)性指數(shù)

為了根據(jù)相對(duì)于檢索的相關(guān)性對(duì)匹配結(jié)果進(jìn)行排序，需要一個(gè)相似性函數(shù)。該函數(shù)為與給定檢索對(duì)應(yīng)的每個(gè)匹配結(jié)果分配一個(gè)相關(guān)性指數(shù)。

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

tf-idfw,D=tfw,D×idfw

(3)

其中，tf是關(guān)鍵字在文件中出現(xiàn)的次數(shù)，idf為檢索條目在數(shù)據(jù)庫(kù)集合中的稀有性。

3 總體框架

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

本文方法的總體框架描述如下。設(shè)D表示敏感性文件集合，F(xiàn)i表示Di∈D的特征集(即關(guān)鍵字)?？蚣馨?個(gè)子算法：配置、指數(shù)生成、檢索生成和檢索。

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

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

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

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

算法詳細(xì)內(nèi)容見(jiàn)第4節(jié)。下面先給出文中將要用到的定義及其涵義。

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

定義4 訪問(wèn)模式(Ap)：表示包括用戶(hù)檢索結(jié)果的數(shù)據(jù)標(biāo)志符集合。設(shè)Fi表示Qi的特征集，R(Fi)表示與特征集Fi相匹配的數(shù)據(jù)元素的標(biāo)識(shí)符集合，于是有Ap=R(Fi)。

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

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

4 本文方法

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

4.1 安全的索引生成

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

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

(4)

設(shè)max表示可能出現(xiàn)于索引中的桶最大數(shù)量，cnt為索引中桶的真正數(shù)量，我們向索引中加入max-cnt個(gè)虛擬元素，以隱藏桶的數(shù)量?？稍谌缦聴l件下隨機(jī)生成虛擬元素(πdumi,Vdumi)：

算法1總結(jié)了安全索引生成方法。

算法1 索引生成

要求：Δ：可能的關(guān)鍵字組成的集合，D：文檔集合，h：λ個(gè)Minhash函數(shù)，Ψ：安全參數(shù)

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

For所有的Di∈Ddo

Fi←提取Di的特征

Forj=1→λdo

Endif

Endfor

Endfor

Endfor

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

返回L

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

4.2 檢索生成

4.3 安全檢索

4.4 文件檢索

用戶(hù)需要避免返回不相關(guān)的文檔，因?yàn)檫@會(huì)迅速導(dǎo)致不必要的通信負(fù)擔(dān)。因此，用戶(hù)往往只檢索最前面的t個(gè)匹配，而不是在檢索時(shí)返回至少個(gè)桶的所有文檔。本文使用tf-idf數(shù)值對(duì)匹配結(jié)果進(jìn)行排序。接收到加密向量EV={V1,…,Vλ}時(shí)，用戶(hù)解密這些向量，獲得的明文向量為Vi=DecKcontent(Vi)。然后，根據(jù)其指數(shù)對(duì)文件排序。請(qǐng)注意，Vi[id(Dj)]表示第i個(gè)桶文檔Dj的tf-idf值。

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

(5)

當(dāng)score(id(Dj))較大時(shí)，文檔相對(duì)檢索的相關(guān)性也將上升。排序階段過(guò)后，用戶(hù)從服務(wù)器檢索到最前面的t個(gè)區(qū)域。文件檢索方法總結(jié)于算法2中。

算法2 文檔檢索

用戶(hù)：

要求：EV：經(jīng)過(guò)加密的向量，Kcontent：密鑰，t：將被檢索的文檔數(shù)量約束

For 所有的Vi∈EVdo

Vi←DecKcontent(Vi)

End for

End for

對(duì)指數(shù)列表排序

idlist←最前面的t個(gè)指數(shù)的標(biāo)識(shí)符

把idList發(fā)送給服務(wù)器

服務(wù)器：

要求：idlist：被請(qǐng)求的文檔標(biāo)識(shí)符，EDoc：被外包且經(jīng)過(guò)加密的文檔

For 所有的id∈idlist do

If (id,Ωid)∈EDocthen

向用戶(hù)發(fā)送(id,Ωid)

End if

End for

用戶(hù)：

Did←DecKcontent(Ωid)

5 雙服務(wù)器檢索

本文方法可能會(huì)將加密檢索與相應(yīng)匹配文檔的標(biāo)識(shí)符關(guān)聯(lián)起來(lái)，為了防止這一關(guān)聯(lián)現(xiàn)象，我們引入稱(chēng)為文件服務(wù)器的第2臺(tái)服務(wù)器。該服務(wù)器并不會(huì)與之前稱(chēng)為檢索服務(wù)器的初始服務(wù)器進(jìn)行合作。當(dāng)檢索服務(wù)器為給定檢索返回加密向量時(shí)，將從文件服務(wù)器獲得經(jīng)過(guò)加密的文檔。通過(guò)這種策略，檢索服務(wù)器不會(huì)知道被檢索出來(lái)的文檔的標(biāo)識(shí)符，文件服務(wù)器不會(huì)知道檢索內(nèi)容。因此，如果假設(shè)兩臺(tái)服務(wù)器沒(méi)有串通合作，便不會(huì)發(fā)生檢索與相應(yīng)文檔標(biāo)識(shí)符相關(guān)聯(lián)這一現(xiàn)象。

有了兩臺(tái)服務(wù)器后，也可以利用這兩臺(tái)服務(wù)器為用戶(hù)執(zhí)行其他操作。第4.4節(jié)描述的文檔檢索階段與用戶(hù)能力有關(guān)，可能會(huì)給用戶(hù)帶來(lái)沉重負(fù)擔(dān)。用戶(hù)在解密檢索出來(lái)的加密向量后，應(yīng)該計(jì)算所有文檔標(biāo)識(shí)符的指數(shù)并對(duì)指數(shù)排序。與服務(wù)器不同的是，用戶(hù)使用的設(shè)備可能對(duì)資源存在約束。為了減輕用戶(hù)負(fù)擔(dān)，可以使用文件服務(wù)器來(lái)對(duì)匹配文檔標(biāo)識(shí)符的指數(shù)進(jìn)行排序。

文件服務(wù)器獲得了匹配的Paillier加密桶內(nèi)容向量，并對(duì)結(jié)果解密。然后，對(duì)指數(shù)排序，與前t個(gè)相似性指數(shù)匹配的項(xiàng)目被發(fā)送給用戶(hù)。通過(guò)這種方法，用戶(hù)的所有計(jì)算負(fù)擔(dān)都轉(zhuǎn)移給了服務(wù)器，但是此時(shí)會(huì)增加經(jīng)過(guò)加密的桶內(nèi)容向量的尺寸。在單服務(wù)器方法中，向量的每個(gè)元素為一個(gè)32比特的整數(shù)，而在雙服務(wù)器方法中，每個(gè)元素是「log2n2?比特的密文，其中n表示兩個(gè)較大素?cái)?shù)的倍數(shù)。然而，這一向量只會(huì)在兩臺(tái)具有大量通信和計(jì)算資源的服務(wù)器間轉(zhuǎn)移。所以，這一策略不會(huì)增加用戶(hù)的通信成本。算法3給出了雙服務(wù)器檢索方法。

算法3 雙服務(wù)器安全檢索和文檔檢索

檢索服務(wù)器：

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

For所有πi∈Qdo

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

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

Endif

Endfor

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

文件服務(wù)器：

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

For所有ido

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

Endfor

對(duì)所有指數(shù)排序

發(fā)送與最前面的t個(gè)指數(shù)相對(duì)應(yīng)的加密文檔

6 仿真實(shí)驗(yàn)

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

(6)

(7)

根據(jù)相關(guān)性指數(shù)(見(jiàn)2.2節(jié))對(duì)匹配項(xiàng)目排序，只有指數(shù)最高的前t個(gè)項(xiàng)目被檢索。我們將閾值固定為t=15，特征數(shù)量范圍設(shè)為2～6個(gè)，對(duì)150次檢索取均值(即每單位尺寸的特征有300次檢索)，來(lái)分析minhash函數(shù)(λ)對(duì)算法精度的影響。如圖1所示，對(duì)任何λ≥150，本文方法的召回指標(biāo)為1，表明在給定檢索中，包含所有特征的所有項(xiàng)目均被用戶(hù)檢索到。對(duì)于我們考慮的數(shù)據(jù)庫(kù)外包場(chǎng)景，用戶(hù)必須獲得與被檢索的特征集相匹配的所有文檔，這一點(diǎn)非常重要。精度指標(biāo)非常低，表明被獲得的文檔中約有40%包括所有被檢索的特征。然而，獲得的其他項(xiàng)目仍然與檢索相關(guān)。這些項(xiàng)目只包括部分檢索特征，匹配的特征的相關(guān)性指數(shù)較高，表明即使沒(méi)有匹配所有的特征，匹配的項(xiàng)目與檢索仍然具有較高的相關(guān)性。請(qǐng)注意，與檢索沒(méi)有任何特征匹配的項(xiàng)目的相關(guān)性指數(shù)為0，因此無(wú)法與檢索匹配。因?yàn)樗梢栽诒ＷC完美召回效果的同時(shí)滿(mǎn)足最優(yōu)精度，所以我們?cè)O(shè)置λ=150。

圖1 t=15且λ變化時(shí)的成功率

我們進(jìn)一步分析了檢索中關(guān)鍵字?jǐn)?shù)量對(duì)精度和召回率的影響，并在圖2中給出結(jié)果。當(dāng)公共關(guān)鍵字?jǐn)?shù)量上升時(shí)，檢索和文檔簽名間的相似性也將上升。因此，當(dāng)檢索中的關(guān)鍵字?jǐn)?shù)量上升時(shí)，本文方法的精度和召回率都會(huì)上升。成功率的上升表明，當(dāng)關(guān)鍵字?jǐn)?shù)量超過(guò)5個(gè)時(shí)，本文方法的效果更優(yōu)。

圖2 檢索中包含的關(guān)鍵字?jǐn)?shù)量和t對(duì)精度(a)和召回率(b)的影響

另外，我們通過(guò)改變數(shù)據(jù)集尺寸(4000到10 000個(gè)文檔)來(lái)評(píng)估本文方法的效率。本文方法成本最高的操作就是索引生成。圖3表明，索引生成步驟需要數(shù)分鐘時(shí)間，且當(dāng)文檔數(shù)量上升時(shí)呈線性增長(zhǎng)?？紤]到這一操作由數(shù)據(jù)所有者離線操作，因此不影響本文方法的實(shí)用性。隱私保護(hù)檢索策略的最重要參數(shù)之一就是檢索響應(yīng)時(shí)間，因?yàn)橛脩?hù)使用這一操作的頻率很高，而且用戶(hù)希望盡快訪問(wèn)到他們的檢索結(jié)果。檢索操作與文檔數(shù)量無(wú)關(guān)，因?yàn)樵诒疚姆椒ㄖ锌偸峭ㄟ^(guò)檢索λ個(gè)被請(qǐng)求的桶來(lái)執(zhí)行檢索操作的。對(duì)于數(shù)量集為數(shù)百萬(wàn)份文檔的大型數(shù)據(jù)集來(lái)說(shuō)，這一特征尤其重要。λ=150時(shí)單服務(wù)器檢索方法的平均檢索響應(yīng)時(shí)間為210ms，且與數(shù)據(jù)集文檔數(shù)量無(wú)關(guān)。

圖3 λ=150時(shí)的索引構(gòu)建時(shí)間

為了更好地體現(xiàn)本文方案的優(yōu)越性，將本文方案與目前較為典型的多關(guān)鍵字檢索方案RQED[8]和PPMKS[9]在檢索精度方面進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果見(jiàn)圖4所示。可以看到，本文方案的檢索精度始終要優(yōu)于PPMKS。當(dāng)關(guān)鍵字?jǐn)?shù)目較少時(shí)，本文方法的性能和RQED基本一致，當(dāng)關(guān)鍵字?jǐn)?shù)目大于4時(shí)，本文方法的性能要優(yōu)于RQED。仔細(xì)分析其原因可知，這是因?yàn)楸疚姆桨妇C合采用了minhashing技術(shù)和為tf-idf加權(quán)方法來(lái)為與給定檢索對(duì)應(yīng)的每個(gè)匹配結(jié)果分配一個(gè)相關(guān)性指數(shù)，隨著指定的關(guān)鍵字?jǐn)?shù)目的增加，文檔中可以利用的特征數(shù)量更多，索引桶的構(gòu)建也更加精確，因此取得了更好的結(jié)果。

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

最后，我們還將本文方案與RQED和PPMKS在檢索效率方面進(jìn)行了比較，結(jié)果見(jiàn)圖5所示?？梢钥吹?，本文方案和RQED的檢索效率要遠(yuǎn)遠(yuǎn)優(yōu)于PPMKS。另外，當(dāng)關(guān)鍵字?jǐn)?shù)目小于6個(gè)時(shí)，本文方案的效率接近于RQED，而當(dāng)關(guān)鍵字?jǐn)?shù)目超過(guò)6個(gè)后，本文方案的效率漸漸地超過(guò)了RQED。這是由于RQED采用多屬性多關(guān)鍵字密文查詢(xún)排序函數(shù)進(jìn)行檢索，當(dāng)關(guān)鍵詞數(shù)目較多時(shí)，必然會(huì)造成效率的下降。而本文方案在檢索過(guò)程中，除了鑒于隱私因素可被泄露的信息外，不需其他信息即可返回結(jié)果，避免了對(duì)用戶(hù)造成不必要的通信和計(jì)算負(fù)擔(dān)，因此效率更高。

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

7 結(jié) 語(yǔ)

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

[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] 孔凡新,劉麗.云環(huán)境下的隱私保護(hù)密文排序查詢(xún)[J].計(jì)算機(jī)工程與設(shè)計(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] 程芳權(quán),彭智勇,宋偉,等.云環(huán)境下一種隱私保護(hù)的高效密文排序查詢(xún)方法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2215-2226.

[9] 李倩,岳風(fēng)順,王國(guó)軍.安全云存儲(chǔ)中高效的多關(guān)鍵字查找方案[J].計(jì)算機(jī)科學(xué),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。郭秋滟，講師，主研領(lǐng)域：云計(jì)算，算法理論。

TP391

A

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