基于計(jì)數(shù)型布隆過濾器的可排序密文檢索方法

李 勇，相中啟

(1.曲靖師范學(xué)院 信息工程學(xué)院，云南 曲靖 655011； 2.上饒師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 上饒 334001)

0 引言

隨著云計(jì)算技術(shù)的日益推廣，越來越多的用戶選擇將本地?cái)?shù)據(jù)外包給云服務(wù)器存儲(chǔ)，以獲取高質(zhì)量低成本的應(yīng)用服務(wù)。然而，近年來不斷暴發(fā)的信息安全事件，尤其是2016全球“勒索”病毒事件的出現(xiàn)，引起了互聯(lián)網(wǎng)用戶對(duì)云計(jì)算環(huán)境下數(shù)據(jù)隱私安全性的廣泛擔(dān)憂。因此，必須對(duì)數(shù)據(jù)進(jìn)行加密處理，以密文的形式在云中存儲(chǔ)數(shù)據(jù)，防止隱私信息的泄漏。數(shù)據(jù)以密文的形式在云中存儲(chǔ)，改變了數(shù)據(jù)之間原有的特性和關(guān)聯(lián)，使得傳統(tǒng)基于明文的數(shù)據(jù)檢索方法不再有效。可搜索加密技術(shù)以密文的方式建立安全檢索索引和保存數(shù)據(jù)，直接在密文狀態(tài)下完成對(duì)數(shù)據(jù)的檢索，不會(huì)泄漏任何明文信息，被廣泛地應(yīng)用于云計(jì)算環(huán)境下對(duì)數(shù)據(jù)的隱私保護(hù)和密文檢索；但是，已有的可搜索加密方法存在數(shù)據(jù)查詢更新和刪除操作不方便、時(shí)間效率低、不支持對(duì)查詢結(jié)果按精確度進(jìn)行排序等問題，因此，設(shè)計(jì)一種安全高效、操作方便、支持排序的密文檢索方法具有重要的理論意義和實(shí)用價(jià)值。

1 相關(guān)工作

可搜索加密技術(shù)起源于Song等于2000年在文獻(xiàn)[1]中提出的首個(gè)對(duì)稱可搜索加密(Symmetric Searchable Encryption, SSE)方案——基于密文掃描思想的對(duì)稱可搜索加密方案(Symmetric Searchable Encryption Scheme based on Ciphertext Scanning, SWP)，但該方案不支持文件檢索索引，而是采用對(duì)稱加密技術(shù)將文件劃分為“單詞”進(jìn)行加密，算法的存儲(chǔ)開銷大、時(shí)間效率極低。此后，國內(nèi)外學(xué)者圍繞著如何提高可搜索加密算法的安全性、時(shí)間開銷、查詢精確度、可操作性等問題開展了大量的研究工作。2003年，Goh在文獻(xiàn)[2]中提出了基于索引的可搜索加密方案Z-DIX(Index-based Searchable Encryption Scheme)，相比SWP方案有較大提升，但是，當(dāng)檢索系統(tǒng)中的文件數(shù)目較多時(shí)，仍然需要耗費(fèi)較長的檢索時(shí)間，效率較低。2006年，文獻(xiàn)[3]中，Curtmola等在Song等的基礎(chǔ)上，提出了SSE-1、SSE-2方案，進(jìn)行文件檢索時(shí)，服務(wù)器只需要O(1)時(shí)間復(fù)雜度即可完成檢索操作，然而，在文件進(jìn)行添加、刪除時(shí)，服務(wù)器需重新構(gòu)建索引以適應(yīng)更新狀態(tài)，索引維護(hù)開銷較大。針對(duì)文獻(xiàn)[3]中存在的索引維護(hù)開銷大、不支持文件動(dòng)態(tài)更新的問題，文獻(xiàn)[4-6]對(duì)服務(wù)器中存放的密文文件的動(dòng)態(tài)添加、更新或刪除操作進(jìn)行了改進(jìn)，提出了適合密文狀態(tài)下動(dòng)態(tài)更新的算法。此外，對(duì)于如何提高密文檢索結(jié)果的精確度和排序問題，文獻(xiàn)[7]基于樹狀檢索結(jié)構(gòu)提出了改進(jìn)算法，但該算法存儲(chǔ)開銷較大。文獻(xiàn)[8]為減小存儲(chǔ)空間開銷，基于二叉樹構(gòu)建了可排序文件檢索結(jié)構(gòu)。針對(duì)文獻(xiàn)[7-8]中存在的索引維護(hù)開銷大和時(shí)間性能低的問題，文獻(xiàn)[9]中，提出了一種基于計(jì)數(shù)型布隆過濾器的分布式文本檢索模型(Text Retrieval Model based on Counting Bloom Filter, CBFTRM)，但CBFTRM模型無法實(shí)現(xiàn)對(duì)查詢結(jié)果排序。文獻(xiàn)[10]提出了一種安全多關(guān)鍵詞密文排序檢索方案，但是該方案中對(duì)不同關(guān)鍵詞計(jì)算的相關(guān)性分?jǐn)?shù)并不能有效地說明文件與關(guān)鍵詞之間的相關(guān)性高低，排序結(jié)果不夠精確。文獻(xiàn)[11]中首次提出了基于隱私保護(hù)的多關(guān)鍵詞模糊檢索方案，大幅提高了文件檢索效率和精確度。文獻(xiàn)[12]在文獻(xiàn)[11]的基礎(chǔ)上基于計(jì)數(shù)型布隆過濾器構(gòu)建索引向量，使用MinHash算法對(duì)關(guān)鍵詞降維，減少了索引構(gòu)建和查詢陷門生成時(shí)間，同時(shí)以計(jì)數(shù)型布隆過濾器索引向量的計(jì)數(shù)表示關(guān)鍵詞權(quán)重，對(duì)查詢結(jié)果排序，但是計(jì)數(shù)型布隆過濾器索引向量的計(jì)數(shù)并不能準(zhǔn)確地表示關(guān)鍵詞與文件間之間的關(guān)系，對(duì)查詢結(jié)果的排序并不準(zhǔn)確。

綜上所述，已有的可搜索加密技術(shù)方案在時(shí)間效率、檢索精確度、排序性能、索引更新能力等方面存在不足之處。為了對(duì)已有方案進(jìn)行改進(jìn)，本文基于計(jì)數(shù)型布隆過濾器提出一種適合云計(jì)算環(huán)境下的可排序密文檢索方法——基于計(jì)數(shù)型布隆過濾器的可排序密文檢索方法(Ciphertext Retrieval Ranking Method based on Counting Bloom Filter, CRRM-CBF)。首先，基于計(jì)數(shù)型布隆過濾器構(gòu)建安全檢索索引，以實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的高效檢索和索引的動(dòng)態(tài)更新功能；然后，使用文件集中關(guān)鍵詞在文件中的出現(xiàn)頻率構(gòu)建關(guān)鍵詞頻率矩陣；最后，使用詞頻逆文本頻率(Term Frequency-Inverse Document Frequency, TF-IDF)模型計(jì)算檢索關(guān)鍵詞與目標(biāo)文件的相關(guān)度分值，根據(jù)檢索關(guān)鍵詞與目標(biāo)文件的相關(guān)度分值來實(shí)現(xiàn)對(duì)文件檢索結(jié)果按精確度排序。

2 預(yù)備知識(shí)

2.1 計(jì)數(shù)型布隆過濾器

布隆過濾器(Bloom Filter, BF)起源1970年，由Burton Bloom在文獻(xiàn)[13]中首次提出，是一種高時(shí)空效率的數(shù)據(jù)結(jié)構(gòu)，由一個(gè)很長的二進(jìn)制向量和一組相互獨(dú)立的哈希函數(shù)組成，主要用于判斷某一個(gè)元素是否在某一個(gè)集合中：若某一元素經(jīng)過一組相互獨(dú)立的哈希函數(shù)映射，輸出結(jié)果對(duì)應(yīng)于布隆過濾器中向量位置序列的值全為1，則可判斷該元素屬于集合；反之，只要任意相應(yīng)位置的取值不為1則可判斷該元素不屬于集合。BF只支持插入和查找操作，不支持刪除操作，是一種僅適合應(yīng)用于靜態(tài)集合中元素判斷的簡單數(shù)據(jù)結(jié)構(gòu)，對(duì)于動(dòng)態(tài)集合中的元素判斷顯得無能為力。

計(jì)數(shù)型布隆過濾器(Counting Bloom Filter, CBF)[14]是一種在BF的基礎(chǔ)上進(jìn)行改進(jìn)的數(shù)據(jù)結(jié)構(gòu)，它的基本原理是，將BF向量中的每一位擴(kuò)展成一個(gè)計(jì)數(shù)器(Counter)，插入元素時(shí)，如果有不同元素被r個(gè)哈希函數(shù)多次映射到同一位置，那么將對(duì)應(yīng)位置Counter的值加1，刪除元素時(shí)，將對(duì)應(yīng)位置Counter的值減1，CBF在BF的基礎(chǔ)上增加了刪除操作，支持集合中元素的動(dòng)態(tài)更新，適用于動(dòng)態(tài)集合中的元素判斷，如文件檢索、網(wǎng)頁去重等，BF與CBF的映射結(jié)構(gòu)如圖1所示。

圖1 BF與CBF映射結(jié)構(gòu)

2.2 TF-IDF模型

TF-IDF模型[15]是常用于信息檢索的一種加權(quán)統(tǒng)計(jì)方法，用于評(píng)價(jià)某一關(guān)鍵詞對(duì)于文件集合中的某一份文件的重要程度，由關(guān)鍵詞詞頻(Term Frequency, TF)和逆文檔頻率(Inverse Document Frequency, IDF)兩部分組成。其中，詞頻TF表示某關(guān)鍵詞在文件中出現(xiàn)的次數(shù)，定義為式(1)：

(1)

逆文檔頻率IDF表示某一關(guān)鍵詞在文件集合中的普遍性重要程度，通常用作關(guān)鍵詞的權(quán)重因子，定義為式(2)：

(2)

最后，TF-IDF模型以式(3)的值作為查詢關(guān)鍵詞與目標(biāo)文件的相關(guān)度分值，并從大到小排序，返回用戶最感興趣的top-p個(gè)目標(biāo)文件。

TF-IDF=TFij*IDFij

(3)

3 系統(tǒng)安全模型

云計(jì)算環(huán)境下可搜索加密系統(tǒng)的安全模型如圖2所示，由數(shù)據(jù)擁有者(Owner User, OU)、授權(quán)用戶(Authentication User, AU)、不可信云服務(wù)器(Cloud Server, CS)3部分組成。

1)數(shù)據(jù)擁有者：提取文件關(guān)鍵詞，構(gòu)建文件檢索索引，并將索引和文件加密外包給云服務(wù)器。

2)授權(quán)用戶：輸入查詢關(guān)鍵詞，生成查詢陷門發(fā)送給云服務(wù)器，獲取感興趣的top-p個(gè)目標(biāo)文件。

3)云服務(wù)器：根據(jù)密文索引和查詢陷門完成計(jì)算，給用戶返回感興趣的top-p個(gè)目標(biāo)文件，同時(shí)負(fù)責(zé)密文索引的更新。

由于云計(jì)算系統(tǒng)都是在遵守用戶數(shù)據(jù)托管和通信協(xié)議的基礎(chǔ)下進(jìn)行工作的，本文認(rèn)為，云計(jì)算系統(tǒng)中的服務(wù)器是一個(gè)“誠實(shí)而好奇”的半可信實(shí)體，即，云服務(wù)器不會(huì)刻意地惡意攻擊系統(tǒng)、泄漏用戶隱私、或與其他非授權(quán)用戶合謀攻擊系統(tǒng)，但卻會(huì)出于“好奇”而挖掘用戶數(shù)據(jù)和推送應(yīng)用服務(wù)、泄漏用戶隱私。因此，本文考慮選擇已知密文攻擊模型作為安全目標(biāo)，在云計(jì)算系統(tǒng)通信環(huán)境下，云服務(wù)器或其他未授權(quán)用戶不能獲取任何明文信息，數(shù)據(jù)擁有者上傳的文件集、安全檢索索引，授權(quán)用戶的查詢請(qǐng)求及查詢結(jié)果等都以密文的形式存在，攻擊者只能選擇唯密文攻擊。

圖2 云環(huán)境下可搜索加密系統(tǒng)安全模型

4 CRRM-CBF方法

云計(jì)算環(huán)境中數(shù)據(jù)檢索具有數(shù)據(jù)量大、用戶數(shù)量多、檢索更新操作頻繁等特點(diǎn)，已有的需要線性搜索時(shí)間來逐次匹配密文信息且需要大量對(duì)數(shù)運(yùn)算的可搜索公鑰加密方法顯然是不合適的，已有的排序密文搜索算法雖然計(jì)算量小、速度高，但是也存在查詢精確度不高的問題[16]，因此，本文基于CBF提出一種可以實(shí)現(xiàn)精確密文排序的可排序密文檢索方法CRRM-CBF，下面詳細(xì)介紹CRRM-CBF方法的具體實(shí)現(xiàn)過程。

4.1 主要符號(hào)定義及說明

CRRM-CBF方法中所涉及到的一些主要符號(hào)定義及說明如下。

F：明文文件集合F=(F1,F2,…Fm)。

C：密文文件集合C=(C1,C2,…Cm)。

FID：集合F中對(duì)應(yīng)文件的標(biāo)識(shí)符集合FID=(FID1,FID2,…,FIDm)，這里的FID是數(shù)據(jù)擁有者自己為了區(qū)分發(fā)布的文件而隨機(jī)分配的一個(gè)標(biāo)識(shí)，不具有任何挖掘語義。

MID：集合F中對(duì)應(yīng)文件在云服務(wù)器中的存儲(chǔ)標(biāo)識(shí)符集MID=(MID1,MID2,…,MIDm)。

QID：與檢索關(guān)鍵詞相關(guān)聯(lián)的文件標(biāo)識(shí)符集合QID=(QID1,QID2,…,QIDm1),QID?FID。

W：所有文件關(guān)鍵詞構(gòu)成的集合W=(w1,w2,…,wn)，關(guān)鍵詞允許在文件中多次重復(fù)出現(xiàn)。

ψ：關(guān)鍵詞在文件中的出現(xiàn)頻率次數(shù)構(gòu)成的關(guān)鍵詞頻率矩陣。

I：將所有關(guān)鍵詞映射到CBF中，構(gòu)成的文件檢索索引向量。

M：擁有k位存儲(chǔ)空間的映射向量，其長度允許動(dòng)態(tài)增加，存儲(chǔ)關(guān)鍵詞映射的取值。

Cψ：關(guān)鍵詞頻率矩陣密文。

CI：文件檢索索引的密文形式，即安全索引。

Qw：檢索關(guān)鍵詞。

Q：檢索關(guān)鍵詞向量。

TQ：檢索陷門。

4.2 具體實(shí)現(xiàn)過程

CRRM-CBF方法的具體實(shí)現(xiàn)過程主要包括：

步驟1 Initial()初始化操作。數(shù)據(jù)擁有者OU從集合F中提取每個(gè)文件的關(guān)鍵詞，得到關(guān)鍵詞集合W，并對(duì)關(guān)鍵詞進(jìn)行向量化處理。

步驟2 Preproc()預(yù)處理操作。數(shù)據(jù)擁有者OU統(tǒng)計(jì)各關(guān)鍵詞在文件中的出現(xiàn)次數(shù)記為ψij，表示關(guān)鍵詞wj在文件Fi中的出現(xiàn)次數(shù)，并以ψij值構(gòu)造如(4)所示的關(guān)鍵詞頻率矩陣ψ。

(4)

在ψ的基礎(chǔ)上，計(jì)算集合F中各文件Fi中包含的關(guān)鍵詞數(shù)并記為NFi,wj，以及集合F中包含有關(guān)鍵詞wj的文件數(shù)并記為Nwj,F，其中，NFi,wj的計(jì)算公式如(5)所示，Nwj,F的計(jì)算公式如(6)所示:

(5)

Nwj,F={Nwj,Fi-1+1,i=i-1|ψij≠0,i=m,j=1,2,…,n|}

(6)

步驟3 BuildIndex_I()、CreatLink()構(gòu)建文件檢索索引、關(guān)鍵詞與文件的關(guān)聯(lián)鏈表。數(shù)據(jù)擁有者OU先將W中的每個(gè)關(guān)鍵詞使用r個(gè)相互獨(dú)立的值域?yàn)閇0,k-1)整數(shù)的哈希函數(shù)映射到CBF中的M向量，以此作為文件檢索索引。然后將索引向量中M[k]位置的計(jì)數(shù)器Counter擴(kuò)展成如圖3所示的鏈表頭Link.head={M[k]，Next}，并在表頭的后面插入元素Link.element={FID，Next}，插入的元素即為與M[k]位置上關(guān)鍵詞相符的文件標(biāo)識(shí)符，Next為指向下一個(gè)元素的指針，尾部元素的Next指針指向Null。最后，得到文件檢索索引I和關(guān)鍵詞與文件的關(guān)聯(lián)鏈表，其結(jié)構(gòu)如圖3所示。

圖3 關(guān)鍵詞檢索索引結(jié)構(gòu)

步驟4 KenGen(k，n)產(chǎn)生安全密鑰。數(shù)據(jù)擁有者OU輸入安全參數(shù)k、n，使用概率密鑰生成算法生成安全密鑰sk=(M1,M2,M3,S,Pplu)，并使用秘密通道將安全密鑰sk發(fā)給授權(quán)用戶，這里的秘密通道指采用Kerberos協(xié)議來完成對(duì)授權(quán)用戶的身份認(rèn)證和密鑰分發(fā)，其中M1、M2為k階隨機(jī)可逆矩陣，M3為n階隨機(jī)可逆矩陣，S=(0,1)k為k位二元向量，Pplu為一個(gè)秘密的大素?cái)?shù)。

步驟5 Enc(F,ψ,I,sk)加密。數(shù)據(jù)擁有者OU使用安全密鑰sk對(duì)文件集F、詞頻矩陣ψ、文件檢索索引I加密，同時(shí)使用MD5函數(shù)計(jì)算每個(gè)文件在云服務(wù)器CS中的存儲(chǔ)標(biāo)識(shí)符MIDi=MD5(FIDi)，最后，將得到的文件集密文C、詞頻矩陣密文Cψ、安全索引CI、存儲(chǔ)標(biāo)識(shí)符MID一起上傳云服務(wù)器CS。

(7)

(8)

其中：ψ的加密過程如式(7)，I的加密過程如式(8)，I′、I″為I分解出來的兩個(gè)子向量，詳細(xì)的分解過程參考文獻(xiàn)[12]中的運(yùn)算規(guī)則進(jìn)行?？紤]到高級(jí)加密標(biāo)準(zhǔn)(Advanced Encryption Standard, AES)對(duì)稱加密運(yùn)算速率快、安全級(jí)別高，適合于加密大規(guī)模文件集，本文使用AES加密算法和密鑰Pplu對(duì)F加密得到密文文件C。

步驟6 Trap(Q,sk)產(chǎn)生檢索陷門，授權(quán)用戶AU輸入文件檢索關(guān)鍵詞Qw=(w1,w2,…,wj)，并使用步驟3中的同一組哈希函數(shù)將查詢關(guān)鍵詞映射到CBF中的M向量，得到檢索向量Q。然后再采用步驟5相似的方法，使用安全密鑰加密檢索向量，輸出得到檢索陷門TQ，文件檢索陷門的生成公式如式(9)，最后，將檢索陷門TQ發(fā)往云服務(wù)器CS。

(9)

步驟7 Ranking_Search(CI,Cψ,TQ)。密文檢索與排序的詳細(xì)過程如下:

1)云服務(wù)器CS收到授權(quán)用戶AU的檢索陷門后，首先進(jìn)行安全索引CI與TQ之間的內(nèi)積運(yùn)算，以檢索與查詢關(guān)鍵詞相符的目標(biāo)文件，詳細(xì)計(jì)算過程[11-12]如下。

I′T·Q′+I″T·Q″=IT·Q

根據(jù)上式文件檢索的計(jì)算結(jié)果，從關(guān)鍵詞與文件的關(guān)聯(lián)鏈表中找到與檢索向量中關(guān)鍵詞相符的文件標(biāo)識(shí)符集QID，并將QID發(fā)送給授權(quán)用戶AU。

(10)

3)授權(quán)用戶AU根據(jù)關(guān)鍵詞頻率矩陣ψ，使用式(1)～(6)讀取并計(jì)算檢索關(guān)鍵詞的TF-IDF值，以此TF-IDF值作為區(qū)分QID中目標(biāo)文件的相關(guān)度分值，并根據(jù)這個(gè)相關(guān)度分值從大到小對(duì)QID中的文件排序，返回授權(quán)用戶AU感興趣的前top-p個(gè)有序的目標(biāo)文件的標(biāo)識(shí)符。

4)授權(quán)用戶AU使用相同的MD5函數(shù)計(jì)算top-p個(gè)目標(biāo)文件的MD5[top-p(QID)]值，并將MD5[top-p(QID)]的值依次發(fā)送至云服務(wù)器CS。

5)云服務(wù)器CS收到MD5[top-p(QID)]值后，根據(jù)MID值依次按順序?qū)中的top-p個(gè)密文目標(biāo)文件發(fā)送給授權(quán)用戶AU，最后，授權(quán)用戶AU使用相同的解密算法AES和解密密鑰Pplu對(duì)前top-p個(gè)密文目標(biāo)文件解密，還原得到排序的明文目標(biāo)文件，完成整個(gè)通信過程。

5 性能分析

5.1 安全性分析

針對(duì)有關(guān)文件檢索索引、檢索陷門、關(guān)鍵詞頻率矩陣的安全性保護(hù)問題，本文借鑒了文獻(xiàn)[11-12]中的做法，隨機(jī)生成了可逆矩陣M1、M2、M3，二元向量S，對(duì)文件檢索索引向量、關(guān)鍵詞檢索向量及關(guān)鍵詞頻率矩陣進(jìn)行加密，由于密鑰矩陣的空間是無窮大的，每次隨機(jī)產(chǎn)生的密鑰矩陣只有唯一的一個(gè)可逆矩陣，未授權(quán)用戶想要正確偽造密鑰矩陣生成檢索陷門、解密關(guān)鍵詞頻率矩陣的可能性為0，有效保證了文件檢索索引、檢索陷門、關(guān)鍵詞頻率矩陣的安全性；同時(shí)，為了保證不會(huì)因關(guān)聯(lián)檢索陷門的泄漏而泄漏隱私信息，本文還使用二元向量S對(duì)索引向量I進(jìn)行分裂運(yùn)算，針對(duì)同一個(gè)檢索向量產(chǎn)生兩個(gè)完全不同的陷門，保證了陷門的無關(guān)聯(lián)性。最后，在文件隱私和密鑰管理的安全性保護(hù)方面，本文分別使用AES對(duì)稱加密算法和Kerberos協(xié)議來完成對(duì)文件集的加密和密鑰的管理，有效保證了文件集和密鑰的安全性，其中AES算法和Kerberos協(xié)議的安全性在許多文獻(xiàn)已有詳細(xì)的證明，本文在此不再敘述。綜上所述，在保證密鑰sk不被人為泄漏的前提下，CRRM-CBF方法針對(duì)已知密文攻擊模型是安全的。

5.2 可更新能力分析

5.3 可排序能力分析

針對(duì)CBF構(gòu)建索引不帶語義功能，不能實(shí)現(xiàn)對(duì)文件檢索結(jié)果排序的問題，本文在CBF索引的基礎(chǔ)上引入了關(guān)鍵詞文件關(guān)聯(lián)鏈表和關(guān)鍵詞頻率矩陣ψ，AU首先通過CBF索引判斷檢索關(guān)鍵詞是否屬于關(guān)鍵詞集W，若屬于，則在關(guān)鍵詞文件關(guān)聯(lián)鏈表中找到與檢索關(guān)鍵詞相關(guān)聯(lián)的目標(biāo)文件FID，再通過FID在關(guān)鍵詞頻率矩陣ψ中讀取檢索關(guān)鍵詞的出現(xiàn)頻率，使用TF-IDF模型統(tǒng)計(jì)計(jì)算檢索關(guān)鍵詞對(duì)目標(biāo)文件區(qū)分能力的相關(guān)度分值，最后，就可以按相關(guān)度分值對(duì)文件檢索結(jié)果實(shí)現(xiàn)排序，并且，查找鏈表和詞頻矩陣兩次比對(duì)過程還可以消除CBF索引的假陽性概率。

5.4 效率分析

為了較好地評(píng)測CRRM-CBF方法在文件檢索時(shí)的時(shí)間開銷、檢索精確度方面的性能。本文以安然公司郵件數(shù)據(jù)集(Enron Email Dataset, EED)作為實(shí)驗(yàn)真實(shí)數(shù)據(jù)集[17]，從中隨機(jī)選取文件，基于Java程序設(shè)計(jì)語言，使用開源開發(fā)環(huán)境Apache-tomcat-7.0.23、MyEclipse2014、JDK1.7，開源分詞器MMSEG4J來實(shí)現(xiàn)方案，并在Intel Core i5-3230 2.60 GHz雙核心CPU、2.0 GB RAM內(nèi)存、Windows 7 64位操作系統(tǒng)平臺(tái)上進(jìn)行實(shí)驗(yàn)測試。

5.4.1 檢索時(shí)間開銷

文件檢索的時(shí)間開銷主要受文件集的規(guī)模、文件檢索索引的效率、檢索陷門的生成時(shí)間、檢索結(jié)果的排序機(jī)制影響，可以較全面地衡量一種可排序密文檢索方案的整體性能，也是衡量系統(tǒng)服務(wù)質(zhì)量的一項(xiàng)重要性能指標(biāo)。為了較客觀地評(píng)價(jià)本文CRRM-CBF方法與文獻(xiàn)[11-12]中方法在文件檢索時(shí)間方面的性能，本文分別以CRRM-CBF方法、文獻(xiàn)[11-12]中方法構(gòu)建文件檢索索引和檢索陷門進(jìn)行測試。1)實(shí)驗(yàn)設(shè)定輸入10個(gè)檢索關(guān)鍵詞、返回top-10個(gè)結(jié)果為目標(biāo)文件，隨機(jī)從數(shù)據(jù)集中選取100、200、300、400、500、600、700、800、900、1 000個(gè)文件進(jìn)行文件檢索測試，實(shí)驗(yàn)測得文件檢索的時(shí)間開銷如圖4(a)所示。2)實(shí)驗(yàn)設(shè)定分別輸入1、5、10、15、20、25、30個(gè)檢索關(guān)鍵詞、返回top-10個(gè)結(jié)果為目標(biāo)文件，在1 000個(gè)文件中進(jìn)行文件檢索測試，實(shí)驗(yàn)測得文件檢索的時(shí)間開銷如圖4(b)所示。

圖4 3種方法文件檢索時(shí)間開銷比較

圖4(a)顯示，用10個(gè)關(guān)鍵詞為輸入在不同文件集規(guī)模下進(jìn)行文件檢索的時(shí)間開銷結(jié)果為，文獻(xiàn)[12]中方法最低，本文方法接近于文獻(xiàn)[11]中方法；圖4(b)顯示，在文件數(shù)為1 000檢索關(guān)鍵詞數(shù)不同的情況下文件檢索的時(shí)間開銷結(jié)果為，在檢索關(guān)鍵詞數(shù)量小于5個(gè)的情況下，本文方法接近于文獻(xiàn)[12]方法而略優(yōu)于文獻(xiàn)[11]中方法，隨著關(guān)鍵詞數(shù)量的增加，本文方法基本接近于文獻(xiàn)[11]中方法而漸差于文獻(xiàn)[12]中方法,主要原因是，3種方法的索引建立和陷門生成機(jī)制都基本相同，不同的是，文獻(xiàn)[12]使用了MinHash算法對(duì)關(guān)鍵詞進(jìn)行了降維處理，生成文件索引時(shí)需要的哈希函數(shù)運(yùn)算次數(shù)較少，減少了構(gòu)建文件檢索索引的時(shí)間開銷，但對(duì)比圖4(a)與圖4(b)中的結(jié)果發(fā)現(xiàn)，這種降維處理的效果在少量關(guān)鍵詞檢索時(shí)的時(shí)間開銷優(yōu)勢(shì)并不明顯。文獻(xiàn)[11]中方法相比本文方法雖然少了對(duì)檢索結(jié)果排序的時(shí)間開銷，但在構(gòu)建索引時(shí)卻多了相似度計(jì)算的時(shí)間開銷，而本文方法的排序只是對(duì)常數(shù)項(xiàng)關(guān)聯(lián)文件和精確詞頻的讀取與計(jì)算，其算法時(shí)間復(fù)雜度為O(1)，當(dāng)關(guān)鍵詞數(shù)量較少時(shí)，檢索結(jié)果中與關(guān)鍵詞相關(guān)聯(lián)的文件并不多，也就是說，詞頻讀取與計(jì)算的時(shí)間開銷并不大。因此，總體上來講，本文方法的文件檢索時(shí)間開銷是較小的。

5.4.2 檢索精確度

查詢精確度是衡量密文檢索系統(tǒng)服務(wù)質(zhì)量的另一項(xiàng)重要性能指標(biāo)，為了客觀地測評(píng)本文方法與文獻(xiàn)[11-12]中方法在文件檢索精確度方面的性能，實(shí)驗(yàn)設(shè)定從數(shù)據(jù)集中隨機(jī)選取1 000個(gè)文件、輸入10個(gè)檢索關(guān)鍵詞、返回top-10個(gè)結(jié)果作為目標(biāo)文件，測試在返回的top-10個(gè)結(jié)果中關(guān)鍵詞的相關(guān)度分值，以此衡量文件檢索結(jié)果的精確度，測試結(jié)果如圖5所示，相關(guān)度分值越高，表明檢索結(jié)果越精確。圖5中結(jié)果顯示，本文方法檢索精確度最高，而文獻(xiàn)[11]中方法最低，其主要原因是，文獻(xiàn)[12]僅以索引向量的計(jì)數(shù)為關(guān)鍵詞權(quán)重建立排序機(jī)制，其排序精確度受假陽性概率影響，所以排序精確度偏低，本文方法則建立精確的詞頻矩陣，依據(jù)詞頻矩陣來計(jì)算文件檢索關(guān)鍵詞區(qū)分目標(biāo)文件的相關(guān)度分值相對(duì)文獻(xiàn)[12]來講更加精確可靠。最后，文獻(xiàn)[11]中由于沒有建立有效的排序機(jī)制，所以精確度最低。

圖5 3種方法文件檢索精確度比較

6 結(jié)語

本文基于計(jì)數(shù)型布隆過濾器提出了一種適用于云計(jì)算環(huán)境下密文檢索和排序的方法CRRM-CBF。通過構(gòu)建CBF索引向量，實(shí)現(xiàn)了文件的密文檢索和索引的動(dòng)態(tài)更新，同時(shí)，考慮到CBF構(gòu)建的索引向量本身不帶語義功能，不能實(shí)現(xiàn)對(duì)目標(biāo)文件的精確排序功能，文中引入了詞頻矩陣和TF-IDF模型計(jì)算關(guān)鍵詞區(qū)分文件能力的相關(guān)度分值，有效地實(shí)現(xiàn)了對(duì)目標(biāo)文件的排序功能。最后，從理論上對(duì)方法的安全性能力、可更新能力和可排序能力進(jìn)行了分析，通過實(shí)驗(yàn)測試分析了方法的文件檢索時(shí)間開銷和檢索精確度，證明了方法的可行性和有效性，但不足之處是，本文方法在實(shí)現(xiàn)排序的過程中，由于引入了詞頻矩陣和文件關(guān)聯(lián)鏈表，增加了存儲(chǔ)空間和索引更新開銷，因此，下一步的研究方向是進(jìn)一步減少存儲(chǔ)空間和索引更新開銷。