杜瑞忠 , 李明月 , 田俊峰 , 吳萬(wàn)青

1(河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院,河北 保定 071002)

2(河北省高可信信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(河北大學(xué)),河北 保定 071002)

在計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)應(yīng)用迅猛發(fā)展的推動(dòng)下,用戶(hù)對(duì)數(shù)據(jù)訪問(wèn)的需求日益增多,信息對(duì)儲(chǔ)存容量的要求日益提高.云計(jì)算使用戶(hù)可以按需地享受高質(zhì)量服務(wù)和無(wú)處不在的網(wǎng)絡(luò)訪問(wèn)[1],但是用戶(hù)將數(shù)據(jù)外包給云服務(wù)器使數(shù)據(jù)脫離了物理控制,隨之帶來(lái)了數(shù)據(jù)隱私泄露的問(wèn)題.

為了保障用戶(hù)的數(shù)據(jù)隱私安全,通常在外包之前對(duì)數(shù)據(jù)進(jìn)行加密,這樣就限制了外包數(shù)據(jù)的可用性,使得廣泛使用的基于關(guān)鍵字的明文信息檢索技術(shù)不能直接應(yīng)用于加密數(shù)據(jù).為了解決上述問(wèn)題,Song 等人[2]首次提出了基于密文掃描思想的可搜索加密方案.可搜索加密方案使用戶(hù)能夠?qū)⒓用艿臄?shù)據(jù)存儲(chǔ)到云中,并通過(guò)密文域執(zhí)行關(guān)鍵字搜索,有選擇地從云中檢索感興趣的文檔,為用戶(hù)節(jié)省了大量開(kāi)銷(xiāo).此后,很多研究人員致力于通過(guò)加密數(shù)據(jù)進(jìn)行安全關(guān)鍵字搜索.Curtmola 等人[3]提出了實(shí)現(xiàn)最優(yōu)搜索時(shí)間的2 種方案(SSE-1 和SSE-2),其中,SSE-1 方案對(duì)于選擇關(guān)鍵字攻擊是安全的,SSE-2 對(duì)于自適應(yīng)選擇關(guān)鍵字攻擊是安全的.但這些早期的方案只是用于單關(guān)鍵字的查詢(xún),在功能方面非常簡(jiǎn)單.為了實(shí)現(xiàn)不同的搜索功能,Ibrahim 等人[4]基于信息檢索系統(tǒng)和密碼學(xué)方法,提出了一種安全的關(guān)鍵字可搜索加密方案,并利用密碼學(xué)原語(yǔ)PPM 來(lái)提高方案的安全性.Chen 等人[5]應(yīng)用稀疏矩陣的方法實(shí)現(xiàn)了大規(guī)模方程的安全外包.但以上方案都基于理想的假設(shè),即云服務(wù)器“好奇但誠(chéng)實(shí)”.在實(shí)際應(yīng)用中,云服務(wù)器可能是惡意的,會(huì)刪除長(zhǎng)期不用的加密文件節(jié)省內(nèi)存空間,或者偽造搜索結(jié)果來(lái)欺騙用戶(hù).為了從加密數(shù)據(jù)中獲得有效的數(shù)據(jù)檢索,需要對(duì)搜索的結(jié)果進(jìn)行驗(yàn)證以保證其正確性.Sun 等人[6]首次提出了對(duì)加密數(shù)據(jù)進(jìn)行安全排序的關(guān)鍵字搜索.此后,為了驗(yàn)證搜索結(jié)果正確性和完整性,Chen 等人[7]設(shè)計(jì)了最小哈希子樹(shù)的結(jié)構(gòu),但該方法只適合索引樹(shù)的結(jié)構(gòu);Wan 等人[8]設(shè)計(jì)了一個(gè)可信的隱私保護(hù)關(guān)鍵字搜索方案VPSearch,該方案通過(guò)對(duì)同態(tài)MAC 技術(shù)進(jìn)行改進(jìn),實(shí)現(xiàn)了多關(guān)鍵字查詢(xún)方案的隱私保護(hù),但由于檢索時(shí)需要搜索整個(gè)數(shù)據(jù)庫(kù),該方案對(duì)于大型數(shù)據(jù)庫(kù)效率是非常低的;Liu 等人[9]提出一個(gè)動(dòng)態(tài)可驗(yàn)證的排序SSE 方案以保護(hù)云環(huán)境中的大數(shù)據(jù)安全,但是每次返回包含關(guān)鍵詞的top-K個(gè)文件,該方案存在排序泄露等問(wèn)題;Zhang 等人[10]提出了基于威懾的可驗(yàn)證關(guān)鍵字排名檢索方案,在整個(gè)驗(yàn)證過(guò)程中,云服務(wù)器不清楚有哪些數(shù)據(jù)所有者,并允許數(shù)據(jù)用戶(hù)根據(jù)喜好來(lái)控制驗(yàn)證的通信成本,但該方案依舊存在排序泄露等問(wèn)題;Jiang 等人[11]提出了可驗(yàn)證的關(guān)鍵字排名密文檢索方案,為每個(gè)關(guān)鍵字生成二進(jìn)制向量,并使用MAC 來(lái)檢查返回密文的真實(shí)性,但由于使用MAC 技術(shù)驗(yàn)證以及涉及大量文件向量間的的內(nèi)積運(yùn)算,帶來(lái)了相對(duì)較高的計(jì)算開(kāi)銷(xiāo).總之,現(xiàn)有的方案在安全性和效率方面有待提高,而文獻(xiàn)[8,9]提出的可驗(yàn)證密文檢索方案在效率和安全方面存在的問(wèn)題具有代表性,因此在隱私保護(hù)度以及查詢(xún)效率兩個(gè)方面與其進(jìn)行了對(duì)比實(shí)驗(yàn).

為了獲得更好的隱私保證并有效地對(duì)密文進(jìn)行檢索,本文設(shè)計(jì)了基于倒排索引的可驗(yàn)證混淆關(guān)鍵字密文檢索方案(a verifiable obfuscated keyword ciphertext retrieval scheme based on inverted index,簡(jiǎn)稱(chēng)VOKCRSII),利用安全的倒排索引結(jié)構(gòu)實(shí)現(xiàn)次線性搜索,通過(guò)插入混淆關(guān)鍵字的技術(shù)來(lái)抵抗關(guān)鍵字攻擊.主要工作如下.

1) 在生成陷門(mén)時(shí)引入混淆關(guān)鍵字,防止云服務(wù)器根據(jù)關(guān)鍵詞的搜索頻率推斷出包含該關(guān)鍵詞文件的價(jià)值,從而進(jìn)行惡意攻擊.

2) 引進(jìn)數(shù)據(jù)緩存區(qū),過(guò)濾返回搜索結(jié)果中包含混淆關(guān)鍵字的密文和驗(yàn)證數(shù)據(jù),減少通信開(kāi)銷(xiāo).

3) 引入雙線性映射驗(yàn)證返回結(jié)果,并對(duì)惡意服務(wù)器模型中返回結(jié)果的正確性、安全性和可靠性進(jìn)行了驗(yàn)證.

4) 在真實(shí)數(shù)據(jù)集上進(jìn)行反復(fù)實(shí)驗(yàn),性能分析和實(shí)驗(yàn)結(jié)果表明,VOKCRSII 方案在保證檢索效率的同時(shí),有效地提高了密文檢索的安全性.

1 背景介紹

1.1 系統(tǒng)模型

本文的系統(tǒng)模型如圖1 所示,將云服務(wù)按功能不同分為3 個(gè)實(shí)體——數(shù)據(jù)擁有者、云服務(wù)器和數(shù)據(jù)使用者.

1) 數(shù)據(jù)擁有者:數(shù)據(jù)擁有者要處理原始數(shù)據(jù)、建立倒排索引以及加密和上傳數(shù)據(jù)與索引.此外,數(shù)據(jù)擁有者要與數(shù)據(jù)使用者分享解密密鑰,并授予數(shù)據(jù)使用者查詢(xún)和驗(yàn)證的權(quán)利.

2) 數(shù)據(jù)使用者:數(shù)據(jù)使用者是授權(quán)用戶(hù),將查詢(xún)的內(nèi)容生成陷門(mén)TD發(fā)送給云服務(wù)器,并要求其返回前K個(gè)文檔以及驗(yàn)證證據(jù).收到搜索結(jié)果后,數(shù)據(jù)使用者執(zhí)行驗(yàn)證算法:若驗(yàn)證算法返回0,即返回結(jié)果錯(cuò)誤;若驗(yàn)證算法返回1,使用共享密鑰對(duì)文檔進(jìn)行解密.

3) 云服務(wù)器:云服務(wù)器存儲(chǔ)數(shù)據(jù)擁有者上傳的加密數(shù)據(jù)與索引,當(dāng)接到數(shù)據(jù)使用者合法的查詢(xún)請(qǐng)求時(shí),根據(jù)查詢(xún)算法利用倒排索引進(jìn)行計(jì)算,返回最相關(guān)的前K個(gè)密文文檔以及驗(yàn)證證據(jù).

Fig.1 Architecture of ciphertext retrieval圖1 密文檢索的系統(tǒng)架構(gòu)

1.2 安全模型

為了規(guī)范研究范圍,本文假設(shè)云服務(wù)器是非完全可信的,即

1) 為了節(jié)省存儲(chǔ)空間,云服務(wù)器可能刪除部分加密文件或索引.

2) 為了節(jié)省計(jì)算或下載帶寬,云服務(wù)器可能不執(zhí)行數(shù)據(jù)使用者的查詢(xún)請(qǐng)求,偽造搜索結(jié)果來(lái)欺騙用戶(hù)[12].

3) 云服務(wù)器存在好奇心,可能會(huì)嘗試分析其存儲(chǔ)的以及消息流中的數(shù)據(jù),推斷甚至識(shí)別某些關(guān)鍵詞.

1.3 主要符號(hào)表示

本文使用的主要符號(hào)的說(shuō)明如下.

·D:明文集合D={D1,…,Dm}.

·C:密文集合C={C1,…,Cm}.

·W:字典集合W={w1,…,wm}.

·#w:包含關(guān)鍵字w的文件數(shù)量.

·m:文件數(shù)量.

·n:字典數(shù)量.

·τ:混淆參數(shù).

·I={Ts,As}:排名倒排索引結(jié)構(gòu).

·Lw:索引標(biāo)記

·TD:搜索陷門(mén).

·Ωw:云服務(wù)器生成的驗(yàn)證標(biāo)簽.

·K:用戶(hù)指定返回文件數(shù)量.

·Di,j:包含關(guān)鍵詞wi的第j個(gè)文件.

·Cw,K:關(guān)鍵字w的top-K搜索密文集合.

·ID(w,K):包含關(guān)鍵字w的top-K文件標(biāo)識(shí)符.

1.4 安全定義

定義 1(正確性).設(shè)T是一個(gè)可驗(yàn)證的密文檢索方案,如果T滿足?PK,SK←Setup(1λ),?Di?D(1≤i≤n),?w?W,有(search(TD,K,I)=(Cw,K,Πw)∧FliterConfu(Cw,K,Ωw)→,則該方案是正確的.其中,Cw,K,Πw是包含混淆關(guān)鍵字的搜索結(jié)果和驗(yàn)證標(biāo)簽,和是真正要搜索關(guān)鍵字的搜索結(jié)果和驗(yàn)證標(biāo)簽.

定義2(自適應(yīng)性選擇關(guān)鍵字攻擊安全).設(shè)T是一個(gè)可驗(yàn)證的密文檢索方案,ρ為攻擊者,s是模擬器,Leak1和Leak2為泄漏算法.概率實(shí)驗(yàn)的滿足:

如果對(duì)于多項(xiàng)式時(shí)間的ρ,都存在多項(xiàng)式時(shí)間的s,使成立,其中,negl(λ)是可以忽略的,則T滿足自適應(yīng)選擇關(guān)鍵字攻擊安全.

定義3(可靠性).設(shè)T是一個(gè)可驗(yàn)證的密文檢索方案,ρ為攻擊者.滿足以下條件.

1.5 雙線性映射

雙線性映射[13]:設(shè)P為λ比特的素?cái)?shù),Zp為有限域,G,GT是階為素?cái)?shù)P的循環(huán)群,g,gT分別為G,GT對(duì)應(yīng)的一個(gè)生成元.可定義一個(gè)雙線性映射:e:G×G→GT滿足以下性質(zhì).

1) 雙線性性:對(duì)于所有的a,b∈Zp,有e(ga,gb)=e(g,g)ab.

2) 非退化性:e(g,g)≠1.

3) 可計(jì)算性:對(duì)于任意元素g,h∈G,可有效地計(jì)算e(g,h).

設(shè)X={x1,...,xl},Y={y1,...,yl}是兩個(gè)l維的向量,則雙線性映射的計(jì)算如下:

2 基于倒排索引的可驗(yàn)證混淆關(guān)鍵字密文檢索方案

2.1 安全倒排索引創(chuàng)建

由于倒排索引搜索時(shí)間是次線性的[14],本文采取倒排索引實(shí)現(xiàn)密文的安全搜索,排序的倒排索引結(jié)構(gòu)I={Ts,As},如圖2 所示.

· 搜索數(shù)組As是一個(gè)長(zhǎng)度為的數(shù)組,其中,#wi是指包含關(guān)鍵字wi的文件數(shù)量.As[i]表示存儲(chǔ)在位置i的值,對(duì)于關(guān)鍵詞wi∈W,列表被隨機(jī)存儲(chǔ)在搜索數(shù)組As中.列表由#wi個(gè)節(jié)點(diǎn)(Ni,1,...,Ni,＃w)組成,其中,Ni,j=〈wi,idj,RScore,addrs(Ni,j+1)〉,idi(j)∈ID(w)是包含關(guān)鍵字wi的rank-j文件的標(biāo)識(shí)符,addrs(Ni,j+1)是Lw的rank-(j+1)個(gè)節(jié)點(diǎn)在搜索數(shù)組As中的地址.最后一個(gè)節(jié)點(diǎn)Ni,＃w=〈wi,id＃w,RScore,NULL〉;

· 搜索表Ts是一個(gè)大小為n的字典,的頭指針存儲(chǔ)在搜索表Ts中.其中,F和P分別為加密關(guān)鍵字和指針的偽隨機(jī)函數(shù).

Fig.2 Security inverted index structure圖2 安全倒排索引結(jié)構(gòu)

2.2 混淆關(guān)鍵字

當(dāng)數(shù)據(jù)使用者想要搜索密文時(shí),可以通過(guò)關(guān)鍵字陷門(mén)來(lái)實(shí)現(xiàn).但是,云服務(wù)器會(huì)根據(jù)經(jīng)常被搜索的關(guān)鍵詞推斷出與其相關(guān)的文件數(shù)據(jù)非常具有價(jià)值,從而選擇性地攻擊這些文件;另一方面,云服務(wù)器還可能將長(zhǎng)時(shí)間未得到搜索的數(shù)據(jù)惡意刪除[15].為了防止云服務(wù)器的惡意攻擊,構(gòu)造如下檢索請(qǐng)求.

1) 數(shù)據(jù)用戶(hù)通過(guò)插入混淆關(guān)鍵字?jǐn)U大搜索的關(guān)鍵字陷門(mén).假設(shè)數(shù)據(jù)使用者想要檢索包含ws的加密文件,為了不讓云服務(wù)器知道關(guān)鍵字集,可以在集合中添加其他x個(gè)關(guān)鍵詞.

2) 數(shù)據(jù)使用者為每一個(gè)關(guān)鍵字增加一個(gè)特殊標(biāo)志位τ,然后用Paillier[7]加密附加的τ來(lái)區(qū)分混淆關(guān)鍵字與用戶(hù)真實(shí)檢索關(guān)鍵字.

3) 假設(shè)數(shù)據(jù)使用者想要檢索包含ws的文件,并引入x個(gè)混淆關(guān)鍵字,則將{〈ws,E(PK,τ)〉,〈ws+1,E(PK,τ)〉,…,〈ws+x,E(PK,τ)〉}上傳到云服務(wù)器.

2.3 數(shù)據(jù)緩沖區(qū)

1) 映射過(guò)程

在接收到數(shù)據(jù)使用者的搜索請(qǐng)求后,云服務(wù)器根據(jù)倒排索引初步得到搜索結(jié)果,其中有包含混淆關(guān)鍵字的密文與驗(yàn)證證據(jù),直接發(fā)送給數(shù)據(jù)使用者會(huì)增加云服務(wù)器和數(shù)據(jù)用戶(hù)之間的通信開(kāi)銷(xiāo).引入數(shù)據(jù)緩存區(qū)模塊,先將搜索結(jié)果按照算法1 映射到數(shù)據(jù)緩存區(qū).

算法1.數(shù)據(jù)緩存區(qū)算法.

輸入:搜索結(jié)果θ.

輸出:數(shù)據(jù)緩存區(qū)DB.

其中,x是數(shù)據(jù)使用者插入的混淆關(guān)鍵字個(gè)數(shù),E(PK,τ)中的τ是混淆參數(shù),τ=1 表示數(shù)據(jù)使用者需要查詢(xún)此關(guān)鍵字,τ=0 表示該關(guān)鍵字為混淆關(guān)鍵字.如圖3 中①所示,云服務(wù)器首先初始化驗(yàn)證數(shù)據(jù)緩沖區(qū),并將結(jié)果映射到具有k散列函數(shù)的驗(yàn)證數(shù)據(jù)緩沖區(qū),每個(gè)散列函數(shù)的輸出屬于[0,x].

2) 過(guò)濾過(guò)程

將云服務(wù)器初步的查詢(xún)結(jié)果通過(guò)Paillier 加密的同態(tài)性質(zhì)直接映射到數(shù)據(jù)緩沖區(qū)后,云服務(wù)器進(jìn)一步對(duì)密文和驗(yàn)證證據(jù)進(jìn)行盲計(jì)算,過(guò)程如圖3 中②所示,在數(shù)據(jù)緩存區(qū)中過(guò)濾掉含有混淆關(guān)鍵字的密文和驗(yàn)證證據(jù),減少通信開(kāi)銷(xiāo).此外,從云服務(wù)器的角度來(lái)看,處理了x+1 個(gè)關(guān)鍵詞的驗(yàn)證數(shù)據(jù)和密文,無(wú)法得到實(shí)際返回的數(shù)據(jù),提高了密文檢索的安全性.

Fig.3 Data buffer圖3 數(shù)據(jù)緩存區(qū)

3) 解密恢復(fù)數(shù)據(jù)

數(shù)據(jù)使用者收到云服務(wù)器返回的搜索結(jié)果后,對(duì)其進(jìn)行解密.圖4 顯示了解密結(jié)果,數(shù)據(jù)使用者可以從數(shù)據(jù)緩存區(qū)的第1 個(gè)節(jié)點(diǎn)恢復(fù)θ1.由于數(shù)據(jù)使用者可以預(yù)先計(jì)算沒(méi)有發(fā)生沖突的條目,而不是解密整個(gè)數(shù)據(jù)緩沖區(qū),可以提高解密效率.

Fig.4 Paillier decryption filter圖4 Paillier 解密過(guò)濾

2.4 方案設(shè)計(jì)

可驗(yàn)證的關(guān)鍵字排序可搜索加密方案構(gòu)造如下.

· 初始化階段

Setup(1λ)→(PK,SK):用戶(hù)運(yùn)行KeyGen(1λ)產(chǎn)生(e,q,g),然后隨機(jī)選擇3 個(gè)λ位的向量λ1,λ2,λ3作為F,P,H的隨機(jī)種子,F:{0,1}λ×{0,1}*→{0,1}λ是一個(gè)無(wú)沖突散列函數(shù),P:{0,1}λ×{0,1}*→{0,1}*,H:{0,1}λ×{0,1}*→{0,1}λ,再生成一個(gè)λ維向量S,.同時(shí)生成2 個(gè)λ×λ維的可逆矩陣(M′,M″).最后得到Key={PK,SK},其中,PK=(q,g),SK=(e,λ1,λ2,λ3,S,M′T,M″T).

· 存儲(chǔ)加密階段

1)EncIndex(SK,D,W)→I:對(duì)于每個(gè)關(guān)鍵字wi∈W,用戶(hù)執(zhí)行以下操作.

①在As中隨機(jī)選擇#wi個(gè)位置創(chuàng)建列表.對(duì)于j∈[1,#wi],將Ni,j={wi,idj,RScore,addrs(Ni,j+1)加密得到

② 對(duì)于i∈[1,n],利用向量S將分割成

Ts是存儲(chǔ)頭指針和索引標(biāo)記Lw的列表,

最后,輸出加密索引I=(Ts,As)上傳到云服務(wù)器.

2)EncFile(D,SK)→C:對(duì)于文件Di∈D,數(shù)據(jù)擁有者運(yùn)行EncFile(Di)來(lái)生成密文Ci,得到密文集合C={C1,C2,…,Cm},上傳到云服務(wù)器.

3)AccGen(PK,SK,D,W)→σ:對(duì)于i∈[1,n],數(shù)據(jù)所有者將關(guān)鍵字集合W={w1,...,wn}中每個(gè)關(guān)鍵詞根據(jù)Lw計(jì)算輸出簽名集合,其中,數(shù)據(jù)擁有者賦予數(shù)據(jù)使用者驗(yàn)證權(quán)限,將簽名集合σ發(fā)給數(shù)據(jù)使用者.

· 查詢(xún)階段

1)SrcToken(w,PK,SK)→TD:為了檢索包含關(guān)鍵字ws的top-K文件,同時(shí)為了不讓云服務(wù)器對(duì)關(guān)鍵詞ws進(jìn)行猜測(cè),獲取用戶(hù)隱私,用戶(hù)引入x個(gè)混淆關(guān)鍵字{ws+1,ws+2,…,ws+z}生成搜索陷門(mén)TD=(ζ1,ζ2,ζ3)上傳到云服務(wù)器.對(duì)于s

其中,E(PK,1)表示數(shù)據(jù)使用者需要查詢(xún)此關(guān)鍵字,E(PK,0)表示該關(guān)鍵字為混淆關(guān)鍵字.

2)Search(TD,K,I)→Cw,K:云服務(wù)器接收到TD=(ζ1,ζ2,ζ3)后,對(duì)于i∈(s,s+x),定位:如果不在Ts中,返回 0;否則,對(duì)于i∈(s,s+x),計(jì)算恢復(fù)的頭指針與索引標(biāo)記進(jìn)而通過(guò)恢復(fù)Ni,j,得到分別包含w={ws,ws+1,ws+2,…,wi+x}的密文集合:

3)GenProof(TD,PK,iwL,Cw,K)→Ωw:云服務(wù)器通過(guò)計(jì)算得到包含混淆關(guān)鍵字所有的驗(yàn)證標(biāo)簽集合其中,i∈(s,s+x).之后,將Ωw連同密文集合Cw,K映射到數(shù)據(jù)緩存區(qū).

4)FilterConfus(Cw,K,Ωw)→云服務(wù)器返回包含混淆關(guān)鍵字所有的驗(yàn)證數(shù)據(jù)會(huì)導(dǎo)致云和數(shù)據(jù)用戶(hù)之間的通信成本很高,如公式(3)所示.

其中,θ={Cw,K,Ωw}.過(guò)濾后得到的和是密態(tài)的,云服務(wù)器無(wú)法識(shí)別,保障了用戶(hù)數(shù)據(jù)的安全性.

通過(guò)Paillier 加密的同態(tài)性質(zhì)直接將驗(yàn)證數(shù)據(jù)映射到數(shù)據(jù)緩沖區(qū),使云端對(duì)搜索結(jié)果進(jìn)行盲計(jì)算,對(duì)驗(yàn)證數(shù)據(jù)Ωw與密文Cw,K進(jìn)行過(guò)濾,得到數(shù)據(jù)使用者要檢索的關(guān)鍵詞ws對(duì)應(yīng)的密文集合和驗(yàn)證標(biāo)簽.

· 驗(yàn)證解密階段

1)Verify(PK,SK,:根據(jù)數(shù)據(jù)緩存區(qū)得到的密文與標(biāo)簽,數(shù)據(jù)使用者進(jìn)行驗(yàn)證.

加密β′和β″得到

② 數(shù)據(jù)使用者利用公式(5)驗(yàn)證返回的是否為包含關(guān)鍵字ws的密文集:

驗(yàn)證失敗返回0;否則,再用公式(6)驗(yàn)證云服務(wù)器返回的是否為top-K文件:

3 方案的安全性驗(yàn)證

定理1.VOKCRSII 方案是正確的.

證明:根據(jù)陷門(mén)TD=(ζ1,ζ2,ζ3),云服務(wù)器可以定位關(guān)鍵字集w={ws,ws+1,ws+2,…,wi+x}在表Ts中的位置,并通過(guò)計(jì)算來(lái)解密列表Aw在數(shù)組As的相應(yīng)地址,從而得密文集合.此外,云服務(wù)器運(yùn)算得到標(biāo)簽集合,再通過(guò)Paillier 加密的同態(tài)性質(zhì)直接將包含混淆關(guān)鍵字的驗(yàn)證數(shù)據(jù)和密文映射到驗(yàn)證數(shù)據(jù)緩沖區(qū),對(duì)搜索結(jié)果進(jìn)行盲計(jì)算,篩選得到和之后發(fā)送給數(shù)據(jù)使用者.接收到來(lái)自云服務(wù)器的搜索結(jié)果和證據(jù)后,數(shù)據(jù)使用者首先檢查,運(yùn)算過(guò)程如公式(7)所示.

在驗(yàn)證VOKCRSII 滿足自適應(yīng)選擇關(guān)鍵字攻擊之前,對(duì)泄漏函數(shù)進(jìn)行形式化描述[16],泄漏函數(shù)Leak1定義為L(zhǎng)eak1(D)=(#D,m,#Di,id(Di)).它將文檔集合D作為輸入,輸出文檔集的大小#D,文檔數(shù)量m,每個(gè)文檔的大小#Di和文件標(biāo)識(shí)符id(Di).泄漏函數(shù)Leak2定義為L(zhǎng)eak2(D,w)=(AP(w),TD),將文檔集合和查詢(xún)關(guān)鍵字w作為輸入,并輸出關(guān)鍵字w的訪問(wèn)模式和陷門(mén).其中,AP(w)=(id(D1),…,□

定理2.VOKCRSII 方案滿足自適應(yīng)性選擇關(guān)鍵字攻擊安全.

證明:令λ∈N為安全參數(shù),ρ為攻擊者,s模擬器,需要證明:對(duì)于多項(xiàng)式時(shí)間的ρ,

1) 模擬加密索引I′:為了模擬索引,s初始化最大長(zhǎng)度為#wi的的每個(gè)條目為(1

2) 模擬密文序列C′:s根據(jù)泄漏函數(shù)Leak1(D)模擬加密文檔(1

3) 模擬陷門(mén)TD′:假設(shè)插入x個(gè)混淆關(guān)鍵字,對(duì)于s

s通過(guò)Leak2(D,wi)得到AP(wi).根據(jù)模擬的加密索引有

· 如果j≠#w,s計(jì)算

· 如果j=#w,s計(jì)算

最后,s返回陷門(mén)由于不具有密鑰λ1,λ2和λ3,可保證中的TD與中的TD′的不可區(qū)分性.即

由于ρ試圖通過(guò)分析加密索引、密文和密鑰來(lái)獲勝,則

令negl(λ)=negl1(λ)+negl2(λ)+negl3(λ),則.其中,Adv(ρ(Key))是ρ區(qū)分密鑰與隨機(jī)字符串的優(yōu)勢(shì),Adv(ρ(I))是ρ區(qū)分索引與隨機(jī)字符串的優(yōu)勢(shì),Adv(ρ(C))是ρ區(qū)分加密文檔和真實(shí)密文的優(yōu)勢(shì).

綜上,對(duì)于多項(xiàng)式時(shí)間的ρ,與的輸出是不可區(qū)分的.VOKCRSII 方案滿足自適應(yīng)性選擇關(guān)鍵字攻擊安全. □

定理3.VOKCRSII 方案滿足定義3 中的可靠性.

證明:假設(shè)VOKCRSII 方案不可靠,則對(duì)于搜索請(qǐng)求TD返回?zé)o效搜索結(jié)果和偽造證據(jù)*Ωw,使得算法Verify(PK,SK,輸出1.令Cw,k={C1,C2,…,C#w}表示正確的搜索結(jié)果:首先可能是文檔的內(nèi)容會(huì)被修改,即在返回的結(jié)果集中存在密文,但其中,j∈{1,...,#w},ρ偽造證據(jù)發(fā)送給數(shù)據(jù)使用者;其次是返回的結(jié)果集中缺少文檔Cj,ρ偽造證據(jù)發(fā)送給數(shù)據(jù)用戶(hù).

4 性能分析

本文實(shí)驗(yàn)原型系統(tǒng)的開(kāi)發(fā)和測(cè)試環(huán)境是基于windows 7(64 位)系統(tǒng),具體硬件配置是intel(R)Core(TM)i7-6700(3.40GHz)處理器,配備8GB 內(nèi)存和網(wǎng)速為1Gbps 的校園網(wǎng)環(huán)境.使用國(guó)內(nèi)云存儲(chǔ)提供商阿里云的云存儲(chǔ)平臺(tái)(搭載centos 7.3 64 位系統(tǒng),主頻為2.5GHz 的4 核CPU,16GB 內(nèi)存,內(nèi)網(wǎng)寬帶為0.8Gbps,公網(wǎng)寬帶為100Mbps,系統(tǒng)盤(pán)為40GB 高效云盤(pán))搭建存儲(chǔ)系統(tǒng).實(shí)驗(yàn)數(shù)據(jù)使用20 431 篇英文文章作為測(cè)試數(shù)據(jù)集,用Lucene 分詞器對(duì)純文本字節(jié)流進(jìn)行分詞,過(guò)濾掉29.1%的停用詞,進(jìn)行關(guān)鍵詞提取形成關(guān)鍵詞數(shù)為7 200 的關(guān)鍵詞集合.在實(shí)驗(yàn)中,從數(shù)據(jù)集中選擇m=3012 個(gè)文件,不同關(guān)鍵字的數(shù)量n=1000,每個(gè)關(guān)鍵字出現(xiàn)在1 個(gè)～44 個(gè)文件中.實(shí)驗(yàn)構(gòu)建了不同關(guān)鍵字?jǐn)?shù)量的索引(即n=100,200,…,1000),使用VOKCRSII 加密索引,使用AES 加密數(shù)據(jù)集,加密算法由JPBC 庫(kù)實(shí)現(xiàn).多次執(zhí)行每個(gè)實(shí)驗(yàn)以獲得平均執(zhí)行時(shí)間.

4.1 功能比較

如表1 所示,文獻(xiàn)[9]和文獻(xiàn)[8]的方案都可以實(shí)現(xiàn)關(guān)鍵詞搜索結(jié)果排序與結(jié)果可驗(yàn)證的功能.

與上述方案相比,VOKCRSII 方案不僅支持多關(guān)鍵字搜索結(jié)果排序與可驗(yàn)證的功能,還支持插入混淆關(guān)鍵字,使方案安全性更高.

Table 1 Function comparison表1 功能比較

4.2 安全性

實(shí)驗(yàn)利用公式(9)檢測(cè)文獻(xiàn)[8]、文獻(xiàn)[9]和VOKCRSII 方案的隱私保護(hù)水平.

其中,0

H(D)越大,隱私泄露可能性就越小,在沒(méi)有外部條件影響時(shí),該值是一個(gè)確定的值[17].

如圖5 所示是文獻(xiàn)[8]、文獻(xiàn)[9]與x=2 時(shí)的VOKCRSII 隱私保護(hù)度對(duì)比.VOKCRSII 賦予用戶(hù)可驗(yàn)證的權(quán)利,且在查詢(xún)陷門(mén)中引進(jìn)混淆關(guān)鍵字,防止云服務(wù)器惡意攻擊搜索頻率高的數(shù)據(jù),或者刪除搜索頻率低的數(shù)據(jù),因此,x=2 時(shí),VOKCRSII 方案的隱私保護(hù)度高于文獻(xiàn)[9]和文獻(xiàn)[8]提出的方案,安全性更高.

Fig.5 Comparison chart of privacy protection圖5 隱私保護(hù)度比較圖

4.3 檢索效率

授權(quán)用戶(hù)在進(jìn)行檢索時(shí),總希望快速地得到檢索結(jié)果[18],本文分別對(duì)方案的生成陷門(mén)時(shí)間、查詢(xún)時(shí)間和驗(yàn)證時(shí)間進(jìn)行實(shí)驗(yàn).由第4.2 節(jié)可知,x=2 時(shí),VOKCRSII 方案的安全性已經(jīng)高于文獻(xiàn)[9]和文獻(xiàn)[8]的方案.隨著插入混淆關(guān)鍵字個(gè)數(shù)的增長(zhǎng),安全性會(huì)增加,但會(huì)帶來(lái)更多的計(jì)算開(kāi)銷(xiāo).因此選擇引入2 個(gè)混淆關(guān)鍵字的VOKCRSII方案做對(duì)比實(shí)驗(yàn).

1) 數(shù)據(jù)緩存區(qū)

VOKCRSII 比文獻(xiàn)[9]方案多消耗的時(shí)間主要體現(xiàn)在云服務(wù)器將查詢(xún)數(shù)據(jù)映射到數(shù)據(jù)緩存區(qū)過(guò)濾掉包含混淆關(guān)鍵字和利用Paillier 解密恢復(fù)數(shù)據(jù)兩個(gè)方面.表2 的第2 行是插入不同數(shù)量混淆關(guān)鍵字時(shí)映射和過(guò)濾消耗的時(shí)間,當(dāng)x=2 時(shí),時(shí)間為0.160s.表2 的第3 行是隨著插入混淆關(guān)鍵字?jǐn)?shù)量增加利用Paillier 解密恢復(fù)數(shù)據(jù)的時(shí)間.當(dāng)x=2 時(shí),時(shí)間為0.031s.

Table 2 Time of mapping filter and decryption data表2 映射過(guò)濾和解密時(shí)間

2) 查詢(xún)效率

查詢(xún)過(guò)程可以分為陷門(mén)生成、查詢(xún)和驗(yàn)證3 個(gè)部分.

生成陷門(mén)時(shí),如表3 所示,文獻(xiàn)[8]的方案用到了大量的內(nèi)積運(yùn)算,復(fù)雜度是O(n2),與關(guān)鍵詞集大小有關(guān).文獻(xiàn)[9]的方案中,陷門(mén)只是由3 個(gè)PRF 產(chǎn)生的3 個(gè)偽隨機(jī)位序列組成.構(gòu)造陷門(mén)的復(fù)雜度是O(λ).VOKCRSII 雖然在陷門(mén)中加入了混淆關(guān)鍵字,但構(gòu)造陷門(mén)的復(fù)雜度仍是O(λ).如圖6,VOKCRSII 和文獻(xiàn)[9]的構(gòu)造陷門(mén)時(shí)間只與隨機(jī)種子λ相關(guān),而與n無(wú)關(guān),隨著關(guān)鍵詞數(shù)量的增加時(shí)間幾乎不變.

Table 3 Comparison of time complexity表3 時(shí)間復(fù)雜度比較

查詢(xún)時(shí),文獻(xiàn)[8]涉及搜索陷門(mén)和每個(gè)文檔子索引的內(nèi)積,見(jiàn)表3,查詢(xún)時(shí)間的復(fù)雜度為O(nm).由于倒排索引搜索的時(shí)間成本與包含w的文檔的數(shù)量成線性關(guān)系,文獻(xiàn)[10]查詢(xún)時(shí)間復(fù)雜度為O(#w),VOKCRSII 由于要搜索x混淆關(guān)鍵字的文件以及將數(shù)據(jù)映射到數(shù)據(jù)緩存區(qū),因此查詢(xún)時(shí)間的復(fù)雜度為O(xK).如圖7 所示,由于文獻(xiàn)[8]的方案檢索時(shí)間隨著文檔數(shù)量的增加而增加,時(shí)間最長(zhǎng).而文獻(xiàn)[9]與VOKCRSII 只與包含搜索關(guān)鍵字的文件數(shù)量相關(guān),相較文獻(xiàn)[8]的方案查詢(xún)時(shí)間增長(zhǎng)緩慢,其中,VOKCRSII 引入了混淆關(guān)鍵字來(lái)提高檢索的安全性,需要過(guò)濾混淆關(guān)鍵字,VOKCRSII 比文獻(xiàn)[9]的方案的所用時(shí)間長(zhǎng),但相差不是很多.

Fig.6 Time of generate trapdoor圖6 陷門(mén)生成時(shí)間

Fig.7 Search time圖7 查詢(xún)時(shí)間

驗(yàn)證時(shí)間包括在云服務(wù)器端生成標(biāo)簽的時(shí)間與用戶(hù)驗(yàn)證的時(shí)間兩部分.如表3 所示,由于文獻(xiàn)[8]要計(jì)算文檔之間的向量積,在客戶(hù)端驗(yàn)證搜索結(jié)果的復(fù)雜度為O(nm);云服務(wù)器端通過(guò)hash 驗(yàn)證樹(shù)生成標(biāo)簽,時(shí)間復(fù)雜度為O(mlogm).文獻(xiàn)[9]在云服務(wù)器鏈簽名技術(shù)生成標(biāo)簽,時(shí)間復(fù)雜度為O(Σ#w);收到來(lái)自云服務(wù)器的返回結(jié)果和標(biāo)簽后,客戶(hù)端利用MAC 將查詢(xún)關(guān)鍵字和返回的top-K文檔的連接作為輸入進(jìn)行驗(yàn)證,復(fù)雜度為O(#w+Σ#Ctop-K),其中,#w表示查詢(xún)關(guān)鍵字的長(zhǎng)度,#Ctop-K表示返回的top-K文檔的總長(zhǎng)度.VOKCRSII 在云服務(wù)器生成標(biāo)簽時(shí)間復(fù)雜度為O(#w);在客戶(hù)端數(shù)據(jù)用戶(hù)先利用雙線性映射的性質(zhì)確定返回的結(jié)果是否是包含關(guān)鍵字ws的文件,再驗(yàn)證來(lái)確定返回的結(jié)果是否正確,復(fù)雜度為O(#w+λ).如圖8(a)所示,由于文獻(xiàn)[8]利用MAC 來(lái)驗(yàn)證,驗(yàn)證時(shí)間最長(zhǎng).文獻(xiàn)[9]驗(yàn)證的復(fù)雜度與top-K文檔的總長(zhǎng)度相關(guān),隨著用戶(hù)要求返回文檔數(shù)量的增加,檢索時(shí)間增長(zhǎng).由于VOKCRSII 引入混淆關(guān)鍵字,映射過(guò)濾消耗的時(shí)間要隨之增加,但VOKCRSII 驗(yàn)證時(shí)不涉及對(duì)返回密文的計(jì)算,驗(yàn)證時(shí)間最短.如圖8(b)所示,當(dāng)Top-K=20 時(shí),隨著文件集數(shù)量變化,文獻(xiàn)[9]驗(yàn)證消耗時(shí)間呈線性增長(zhǎng).而文獻(xiàn)[9]和VOKCRSII 與包含查詢(xún)關(guān)鍵字的文檔數(shù)量有關(guān),驗(yàn)證時(shí)間增長(zhǎng)緩慢.

Fig.8 Verification time圖8 驗(yàn)證時(shí)間

5 總結(jié)

本文提出了一個(gè)安全有效的關(guān)鍵字密文檢索方案VOKCRSII.該方案通過(guò)混淆關(guān)鍵字隱藏搜索頻率,并利用雙線性映射生成標(biāo)簽驗(yàn)證搜索結(jié)果,提高方案的安全性.同時(shí),對(duì)其正確性、安全性和可靠性這3 個(gè)方面進(jìn)行了驗(yàn)證.通過(guò)分析驗(yàn)證,VOKCRSII 滿足自適應(yīng)性選擇關(guān)鍵字攻擊安全.此外,利用加密標(biāo)志位區(qū)分混淆關(guān)鍵字和真正要檢索的關(guān)鍵字,生成陷門(mén)上傳至云服務(wù)器,但根據(jù)陷門(mén)得到的搜索結(jié)果有包含混淆關(guān)鍵字的文件,利用Paillier 加密算法生成數(shù)據(jù)緩存區(qū)過(guò)濾掉多余文件,以減少通信開(kāi)銷(xiāo).通過(guò)建立密文檢索實(shí)驗(yàn)平臺(tái),驗(yàn)證VOKCRSII 在保證檢索效率的同時(shí),提高了密文檢索的安全性.但VOKCRSII 只支持加密文檔集的查詢(xún),將可搜索加密技術(shù)擴(kuò)展到關(guān)系型數(shù)據(jù)庫(kù),是未來(lái)要做的工作.