崔韶剛,尹 輝,周春光

(長沙學院網(wǎng)絡(luò)中心,湖南 長沙 410003)

可搜索加密(Searchable Encryption,SE)[1]是加密數(shù)據(jù)的查詢和檢索技術(shù).近年來,云環(huán)境下的SE技術(shù)是學術(shù)界和產(chǎn)業(yè)界的研究熱點,目的在于不斷提高查詢效率和查詢準確度,降低空間和傳輸開銷,以及實現(xiàn)用戶查詢的隱私保護等.然而,現(xiàn)有的方案存在以下3個問題[2-3]：(1)將云作為唯一的威脅實體.(2)在大多數(shù)方案中,數(shù)據(jù)更新需要數(shù)據(jù)擁有者重建查詢索引,這會產(chǎn)生頻繁的索引重建工作,給云用戶帶來沉重的計算負擔,大大降低系統(tǒng)的伸縮性和可用性.(3)沒有一個真正安全和精確的查詢結(jié)果相關(guān)性排序方案來實現(xiàn)云端的top-k安全查詢.為了解決以上問題,筆者擬利用雙線性映射和布魯姆過濾器設(shè)計支持數(shù)據(jù)動態(tài)更新的安全索引和強隱私保護的高效查詢方案,并利用全同態(tài)加密技術(shù)[4]和關(guān)鍵字在數(shù)據(jù)文件中的權(quán)重信息,對查詢結(jié)果進行精確的相關(guān)性排序,以期在不泄露任何明文信息的情況下,讓云返回與用戶查詢最相關(guān)的數(shù)據(jù)文件.

1 相關(guān)工作

1.1 對稱可搜索加密

2000年,Song等[5]基于對稱密鑰環(huán)境,首次設(shè)計了一個實用的SE方案.因為此方案并沒有建立查詢索引,而是采用一種特殊的2層加密結(jié)構(gòu)對文檔中的全部詞項逐個進行加密,所以在查詢時,需要服務(wù)器對整個文檔的每一個詞項和用戶提交的查詢關(guān)鍵字進行比較.這種方案只能處理非壓縮形式的文檔類型文件,且無法抵御詞典攻擊.Goh[6]對文獻[5]中的查詢效率和安全性作了改進,利用布魯姆過濾器和偽隨機函數(shù)為外包文件建立安全索引,極大地減少了查詢的比較次數(shù).Curtmola等[7]利用倒排索引技術(shù)構(gòu)造了一個高效的單關(guān)鍵字對稱可搜索加密(Searchable Symmetric Encryption,SSE)方案,并給出了SSE機制的定義.但該方案存在預定義的全局詞典,導致文件更新需要用戶重建所有加密的倒排索引,不適合多用戶的云計算環(huán)境.Wong等[8]利用矩陣和向量的對稱加密運算,通過比較2個加密向量點的歐幾里得距離實現(xiàn)了加密數(shù)據(jù)庫的安全k-近鄰(k-Nearest Neighbor,k-NN)計算.

1.2 非對稱可搜索加密

2004年,Boneh等[9]基于加密郵件查詢的應(yīng)用場景,首次提出了基于公鑰加密的關(guān)鍵字查詢(Public-Key Encryption with Keyword Search,PEKS)方法.在PEKS方法中,郵件發(fā)送者利用郵件接收者的公鑰加密郵件和建立相應(yīng)的查詢索引;郵件接收者查詢時,他利用自己的私鑰加密查詢關(guān)鍵字后發(fā)送給郵件網(wǎng)關(guān),讓郵件網(wǎng)關(guān)執(zhí)行秘密查詢.Golle等[10-12]基于公鑰密鑰體制設(shè)計了加密文件的多關(guān)鍵字安全查詢方案.由于公鑰密碼加解密存在計算開銷,因此這些方案不適合大規(guī)模數(shù)據(jù)集下的安全查詢場景,而且文件和索引若采用公鑰加密,則一個具有強大計算資源的敵手(如云)可以對其進行字典攻擊和統(tǒng)計攻擊.

1.3 云環(huán)境下的Top-k安全排序查詢

Wang等[13]在SSE方案的基礎(chǔ)上,利用關(guān)鍵字在文檔中的權(quán)重和保序?qū)ΨQ加密(Order Preserving Symmetric Encryption,OPSE)[14]技術(shù)實現(xiàn)了云環(huán)境下相關(guān)性排序的對稱可搜索加密(Ranked Searchable Symmetric Encryption,RSSE)方案.但OPSE技術(shù)固有的缺陷,使得RSSE方案不能很好地抵御已知背景知識下的統(tǒng)計攻擊,以及無法適應(yīng)數(shù)據(jù)分布動態(tài)變化的云環(huán)境.2013年,Cao等[15]基于安全k-NN計算[8],首次提出了云環(huán)境下的加密數(shù)據(jù)多關(guān)鍵字排序查詢(Multi-Keyword Ranked Search over Encrypted Cloud Data,MRSE)方法.該方法以查詢關(guān)鍵字是否包含在文件中為依據(jù)進行相關(guān)排序,排序結(jié)果不能準確地反映文檔與查詢之間的相關(guān)性.Li等[16]使用編輯距離來量化字符串的相似度,并利用同一字符串的不同編輯距離實現(xiàn)云環(huán)境下的模糊查詢.但該方案需要的存儲和通信負載比較大,且不能對查詢結(jié)果進行相關(guān)性排序,準確率誤差較大.Liu等[17]通過對用戶和查詢進行分級,利用Paillier密碼系統(tǒng)的同態(tài)屬性,實現(xiàn)了按用戶等級返回一定百分比數(shù)量的文件給用戶,大大減少了網(wǎng)絡(luò)傳輸開銷.但該方案需要一個完全可行的第三方查詢匯聚和分發(fā)層作為中間件,同時需要一個預定義的全局詞典.

在以上相關(guān)工作中,對于用戶查詢隱私,都將遠程服務(wù)器作為唯一的威脅實體,而沒有考慮潛在的內(nèi)部攻擊者,如一個惡意的數(shù)據(jù)擁有者或一個妥協(xié)的數(shù)據(jù)使用者.在文獻[15-16]中,用戶的查詢內(nèi)容以明文的形式暴露給數(shù)據(jù)擁有者,數(shù)據(jù)擁有者直接掌握用戶查詢內(nèi)容.在文獻[5-7,13,17]中,雖然數(shù)據(jù)使用者自己加密查詢關(guān)鍵字,但加密密鑰是數(shù)據(jù)擁有者授權(quán)提供的,數(shù)據(jù)擁有者掌握密鑰信息,用戶無法抵御數(shù)據(jù)擁有者的惡意探查和分析查詢隱私的攻擊,也無法保證數(shù)據(jù)擁有者不將用戶查詢信息或密鑰泄露給第三方敵手,因此用戶的查詢隱私面臨更大的泄露風險.另外,一個妥協(xié)的數(shù)據(jù)使用者也可以向遠程服務(wù)器泄露其他用戶的查詢隱私,因為當他們使用相同的查詢關(guān)鍵字時具有相同的查詢陷門形式.在公鑰環(huán)境下,用戶通過自己的私鑰加密查詢關(guān)鍵字,遠程服務(wù)器無法合謀惡意的數(shù)據(jù)擁有者或妥協(xié)的數(shù)據(jù)使用者攻擊用戶的查詢隱私,但因為文件和索引采用公鑰加密,所以用戶無法抵御云的字典攻擊或統(tǒng)計攻擊.

2 問題陳述與相關(guān)知識

2.1 問題陳述

如圖1所示,云環(huán)境下基于隱私保護的多用戶查詢架構(gòu)中,主要包括3種實體,即多個數(shù)據(jù)擁有者、多個數(shù)據(jù)使用者和云服務(wù)提供商.

圖1 云環(huán)境下強隱私保護的排序查詢架構(gòu)Fig. 1 Sorting Query Architecture with Strong Privacy Protection over Cloud Data

為了保證數(shù)據(jù)的機密性,對于外包給云的數(shù)據(jù)集合F={F1,F2,…,Fn},數(shù)據(jù)擁有者采用語義安全的對稱加密算法Encek()加密文件Fi,采用單向哈希函數(shù)H計算文件Fi的文件標識號IDFi,用Wi={w1,w2,…}表示文件Fi的查詢關(guān)鍵字集合,用戶通過Wi中的關(guān)鍵字查詢文件Fi.為了能夠讓授權(quán)的數(shù)據(jù)使用者查詢加密文件,數(shù)據(jù)擁有者利用文件Fi的查詢關(guān)鍵字集合Wi為Fi建立一個安全索引Ii,要求敵手不能通過Ii推測出任何有關(guān)Fi和Wi的明文信息.最終的密文集合用C={Ci=Encek(Fi),H(IDFi),Ii|i=0,1,…,n}表示,Ci表示文件Fi的密文.最后,數(shù)據(jù)擁有者將C外包給云服務(wù)提供商存儲.

當數(shù)據(jù)使用者查詢文件時,為了保護隱私,他加密查詢關(guān)鍵字生成查詢陷門TRDu后提交給云服務(wù)提供商.云服務(wù)提供商接收到授權(quán)用戶提交的TRDu后開始執(zhí)行查詢,并對結(jié)果進行相關(guān)性排序,根據(jù)請求的文件數(shù)量返回top-k個密文給數(shù)據(jù)使用者.數(shù)據(jù)使用者用解密算法Deek(·)在本地進行解密,最終得到明文文件.整個過程中,云服務(wù)提供商僅僅知道哪些密文作為結(jié)果被返回,除此之外云無法獲取文件和查詢的任何明文信息.

2.2 威脅模型

云環(huán)境下,典型的基于隱私保護的密文查詢架構(gòu)中,云服務(wù)提供商作為誠實而好奇的半可信敵手模型,原則上它遵循數(shù)據(jù)托管和安全協(xié)議,正確合理地處理數(shù)據(jù),但無法排除其惡意推測外包數(shù)據(jù)內(nèi)容和惡意分析用戶查詢請求的可能性.本研究除了討論云服務(wù)提供商這種典型的敵手模型,還將考慮具有更強攻擊能力的合謀攻擊模型,即云服務(wù)提供商勾結(jié)一個惡意的數(shù)據(jù)擁有者或一個妥協(xié)的數(shù)據(jù)使用者對其他數(shù)據(jù)使用者的查詢關(guān)鍵字進行合謀攻擊,達到秘密探查授權(quán)用戶查詢隱私的目的.圖2示出了2種攻擊模型.在攻擊方式上,采用廣泛使用的已知密文攻擊和已知背景知識攻擊方式[13,15],且整個系統(tǒng)要求達到已知背景知識攻擊下的安全性.

圖2 威脅模型示意Fig. 2 Threat Model

2.3 相關(guān)知識

為了實現(xiàn)合謀威脅模型下的強隱私保護安全查詢方案,需要2個基本安全知識,即雙線性映射和雙線性Diffie-Hellman問題(Bilinear Diffie-Hellman Problem,BDHP)困難性假設(shè).

(1)雙線性映射.

若G1和G2是階為大素數(shù)p的乘法循環(huán)群,映射e：G1×G1→G2為雙線性映射,則e具有如下性質(zhì)：

(ⅱ)非退化性.若g是G1的生成元,則e(g,g)是G2的生成元.

(ⅲ)可計算性.對于?V,U∈G1,總是存在一個有效的多項式時間算法計算e(V,U)∈G2.

(2)雙線性BDHP困難性假設(shè).

3 基于關(guān)鍵字權(quán)重的加密排序方案

要實現(xiàn)top-k查詢,就要確定查詢結(jié)果的相關(guān)度排序機制.筆者根據(jù)查詢關(guān)鍵字在數(shù)據(jù)文件中的權(quán)重進行排序,權(quán)重越大說明文件和查詢關(guān)鍵字的相關(guān)度越高,越符合用戶查詢需求.一方面,數(shù)據(jù)使用者提交查詢請求給云,云查詢所有滿足要求的加密數(shù)據(jù)文件后,根據(jù)權(quán)重值在云端進行相關(guān)性排序;另一方面,若關(guān)鍵字權(quán)重以明文的形式存儲在云端,則攻擊者在已知背景知識的情況下,可以利用這些權(quán)重信息發(fā)起統(tǒng)計攻擊,達到獲取文件內(nèi)容的目的.因此,權(quán)重信息需要作為敏感信息加密以后再外包給云服務(wù)提供商.但是,加密數(shù)值將失去數(shù)值的比較功能,給數(shù)值排序帶來麻煩.保序加密是一個解決方案,它可以使加密后的數(shù)值保持順序關(guān)系,但在具有大量重復數(shù)值時,密文無法抵御統(tǒng)計攻擊且不適合數(shù)值分布動態(tài)變化的云環(huán)境.筆者將基于一個全同態(tài)加密方案實現(xiàn)基于加密數(shù)值的排序機制.

3.1 關(guān)鍵字權(quán)重的計算

3.2 全同態(tài)加密方案

Dijk等[18]提出了一個全同態(tài)公鑰加密方案FHEnc=(KeyGen,FHE,Evaluate,FHD).這里：KeyGen是公私鑰生成算法;FHE是明文空間為{0,1}加密算法;Evaluate是同態(tài)運算算法;FHD是解密算法.FHE在計算上能同時滿足加法同態(tài)

FHE(m1)+FHE(m2)=FHE(m1⊕m2)

(1)

和乘法同態(tài)

FHE(m1)×FHE(m2)=FHE(m1×m2)

(2)

的有效運算.

因為FHEnc的明文空間為{0,1},所以可利用FHEnc方案構(gòu)造一個明文空間為{0,1}*的數(shù)值加密方案FHEncS=(KeyGen,FHES,FHDS),且加密后的數(shù)值具有比較功能.設(shè)整數(shù)M∈{0,1}*,用l位二進制表示為M=(m1m2…ml)2,mi∈{0,1}(i=1,2,…,l).算法KeyGen保持不變,FHES和FHDS分別表示為

FHES(M)={FHE(m1),FHE(m2),…,FHE(ml)},

FHDS(M)={FHD(m1),FHD(m2),…,FHD(ml)}.

3.3 安全定義

(ⅰ)挑戰(zhàn)者X運行算法KeyGen(k)產(chǎn)生公私鑰對(sk,pk),將pk交給敵手A,sk秘密保留.

(ⅱ)敵手A對密文C進行解密查詢時,挑戰(zhàn)者運行FHD(sk,C)進行應(yīng)答.當A決定結(jié)束查詢時,他輸出消息m0和m1交給挑戰(zhàn)者.

(ⅲ)挑戰(zhàn)者隨機選擇一個比特b∈{0,1},計算密文C*=FHE(pk,mb),C*作為挑戰(zhàn)密文返回給敵手A.

(ⅳ)敵手A繼續(xù)進行解密查詢,但不能詢問C*的解密結(jié)果,最后A輸出一個比特位b′.

(ⅴ)若b′=b,則游戲的輸出為1,否則為0.

定義1全同態(tài)公鑰加密方案FHEnc=(KeyGen,FHE,Evaluate,FHD)是滿足IND-CCA的公鑰加密方案,對于任意的概率多項式時間的敵手A,對給定的安全參數(shù)n,存在可忽略的函數(shù)negl,滿足

3.4 加密數(shù)值的比較算法

ri-1=ai×bi∨(ai⊕bi)×ri,

(3)

ci=ai⊕bi⊕ri.

(4)

從i=l,rl=0開始,循環(huán)求出B1,B2各個二進制位相加的結(jié)果ci和進位ri-1,直到i=1時可得(c1c2…cl)2,最后計算r0并讓進位c0=r0.

給定任意比特位b1,b2∈{0,1},它們邏輯或(∨)、按位異或(⊕)和乘法(×)運算的值見表1.利用表1構(gòu)造等式b1∨b2=(b1⊕b2)⊕(b1×b2),于是(3)式變換成

表1 2個比特位的邏輯或、異或和乘法運算Table 1 Logical OR,XOR and Multiplication of Two Bits

ri-1=ai×bi∨(ai⊕bi)×ri=((ai×bi)⊕((ai⊕bi)×ri))⊕

((ai×bi)×((ai⊕bi)×ri)).

(5)

(ⅰ)用FHE加密(4)式.根據(jù)(1)式,有

FHE(ci)=FHE(ai⊕bi⊕ri)=FHE(ai)+FHE(bi)+FHE(ri).

(ⅱ)用FHE加密(3)式.根據(jù)(1),(2),(5)式,有

FHE(ri-1)=FHE(ai×bi∨(ai⊕bi)×ri)=FHE(((ai×bi)⊕((ai⊕bi)×ri))⊕

((ai×bi)×((ai⊕bi)×ri)))=FHE((ai×bi)⊕((ai⊕bi)×ri))+

FHE((ai×bi)×((ai⊕bi)×ri))=FHE(ai)×FHE(bi)+

(FHE(ai)+FHE(bi))×FHE(ri)+FHE(ai)×FHE(bi)×

((FHE(ai)+FHE(bi))×FHE(ri)).

提取最高位有效位FHE(c0),若c0=0,則FHES(B1)≥FHES(B2),否則FHES(B1)

3.5 相關(guān)文件加密排序函數(shù)Sec_Rank

對于一個查詢Q和用戶需要云返回的文件數(shù)量Request_Num,利用Q在文件中的權(quán)重實現(xiàn)文件的相關(guān)性秘密排序,并利用秘密排序函數(shù)Sec_Rank實現(xiàn)排序功能.將排在前Request_Num位的數(shù)據(jù)文件返回給用戶,且不會向云端泄露任何關(guān)鍵字權(quán)重和數(shù)據(jù)文件的明文信息.Sec_Rank的主要實現(xiàn)細節(jié)如下：

對于查詢Q,若文件F1和F2是Q的查詢結(jié)果,則從F1和F2的安全索引中分別提取它們關(guān)于Q的加密權(quán)重值,用FHES(W1)和FHES(W2)表示,然后執(zhí)行如下操作：

(ⅳ)V=FHD(FHE(w0)).

(ⅴ)若V=0,則將文件F1排在F2的前面,表示F1相對于F2對Q更相關(guān);若V=1,則將文件F2排在F1的前面.

(ⅵ)內(nèi)存銷毀.

Sec_Rank經(jīng)編譯以后,供云服務(wù)商調(diào)用完成排序.

4 強隱私保護的安全Top-k查詢方案

4.1 方案的設(shè)計

強隱私保護的安全top-k查詢方案(Secure Top-kQuery Scheme with Strong Privacy Protection,STQSSPP),由以下5個概率多項式時間算法組成：SetUp是整個查詢方案的參數(shù)初始化算法,由系統(tǒng)調(diào)用完成;數(shù)據(jù)使用者調(diào)用KeyGen生成公鑰和私鑰對;數(shù)據(jù)擁有者調(diào)用BulidIndex為外包數(shù)據(jù)文件建立可查詢安全索引;Trapdoor算法由授權(quán)用戶調(diào)用,加密查詢關(guān)鍵字達到隱私保護的目的;云服務(wù)提供商接受用戶提交的查詢陷門運行Query,實現(xiàn)在云端的top-k安全查詢,并將查詢結(jié)果返回給最終用戶.

4.2 方案的實現(xiàn)

STQSSPP的實現(xiàn)細節(jié)如下：

(3)BulidIndex(Wi,FIDi).數(shù)據(jù)擁有者為數(shù)據(jù)文件Fi建立安全索引,Wi表示文件Fi的查詢關(guān)鍵字集合,FIDi表示文件Fi的唯一標識號.

(ⅰ)數(shù)據(jù)擁有者生成大小為m的數(shù)組BFi和SFi,BFi作為布魯姆過濾器用于插入Fi查詢關(guān)鍵字,SFi存放各個查詢關(guān)鍵字在Fi中的加密權(quán)重.初始,它們的所有位被置為0.

(ⅱ)對Wi中的每一個查詢關(guān)鍵字w作如下處理：

(a)利用哈希函數(shù)H3和雙線性對運算e編碼w,計算e(H3(w),g1).

(b)將編碼后的關(guān)鍵字w和Fi進行關(guān)聯(lián),計算Iw=H2(e(H3(w),g1))⊕H2(FIDi).

(c)插入Iw到位數(shù)組BFi中,利用哈希函數(shù)族H中的k個哈希函數(shù)計算h1(Iw),h2(Iw),…,hk(Iw),再將數(shù)組BFi的這些相應(yīng)位置為1.

(d)計算w在文件Fi中的權(quán)重并轉(zhuǎn)化為正整數(shù)SFi,w,用FHES加密算法對SFi,w進行加密得到FHES(SFi,w),將它存儲到數(shù)組SFi的(h1(Iw)⊕h2(Iw)⊕…⊕hk(Iw)) modm位置中,即

SFi((h1(Iw)⊕…⊕hk(Iw)) modm)=FHES(SFi,w).

(ⅲ)將BFi和SFi共同作為Fi的安全查詢索引,即Ii=(BFi,SFi),對F中的所有文件做以上處理后,將密文數(shù)據(jù)集合C={Ci=Encek(Fi),H2(IDFi),Ii|i=0,1,…,n}外包給云服務(wù)提供商.

(5)Query(TRDu,Request_Num).云接收用戶提交的查詢陷門TRDu后進行查詢,并將查詢結(jié)果按關(guān)鍵字在文件中的權(quán)重排序,返回與查詢最相關(guān)的前Request_Num個文件給用戶.

(ⅰ)云接收TRDu后,對每一個密文Ci作如下查詢操作：

(a)將查詢陷門TRDu和Ci的標示號H2(IDFi)進行異或運算,即

(b)利用哈希函數(shù)族H計算h1(Qu),h2(Qu),…,hk(Qu),若位數(shù)組BFi上所有的這些相應(yīng)位都為1,則Ci是Qu的一個查詢結(jié)果.若Ci是查詢結(jié)果,則需要訪問數(shù)組SFi,取出Qu中的關(guān)鍵字w在文件Ci的權(quán)重,以便在云端進行文件相關(guān)性排序.用SFi,Qu表示查詢Qu中包含的關(guān)鍵字w在數(shù)據(jù)文件Fi中的密文權(quán)重,它的值可以從數(shù)組SFi中獲取,即SFi,Qu=SFi((h1(Qu)⊕…⊕hk(Qu)) modm).

(c)將Fi的密文和SFi,Qu加入到結(jié)果集合中：Result←Result{Encek(Fi),SFi,Qu}.

(ⅱ)對Result中的任意2個數(shù)據(jù)文件{Encek(Fi),SFi,Qu}和{Encek(Fj),SFj,Qu}調(diào)用排序函數(shù)Sec_Rank(SFi,Qu,SFj,Qu)進行排序,將權(quán)重較大者排在前面,表示它與查詢Qu的相關(guān)性更大.

(ⅲ)云將前Request_Num個文件返回給用戶,用戶利用數(shù)據(jù)所有者授權(quán)的加密密鑰ek在本地解密,獲取明文文件.

4.3 方案正確性分析

定理1假設(shè)用戶提交的TRDu中包含的查詢關(guān)鍵字為w,若文件Fi的查詢關(guān)鍵字集合中存在一個關(guān)鍵字w′,滿足w=w′,則STQSSPP能正確返回密文Encek(Fi).

證明已知w′是Fi的一個關(guān)鍵字,數(shù)據(jù)擁有者為Fi構(gòu)建索引時,先計算Iw′=H2(e(H3(w′),g1))⊕H2(FIDi),再利用哈希函數(shù)族Η將Iw′插入到位數(shù)組BFi中去.當云收到TRDu后,云執(zhí)行運算

并利用Η的各個哈希函數(shù)計算Qu,再檢查BFi所有的這些位置是否都為1.

若陷門TRDu中的查詢關(guān)鍵字為w,且滿足w=w′,則文件Fi是查詢的正確結(jié)果,因為云收到TRDu后執(zhí)行如下運算：

若w=w′,則Iw′=Qu,從而云根據(jù)Qu在BFi上執(zhí)行查詢后能正確返回密文Encek(Fi).證畢.

4.4 多關(guān)鍵字Top-k安全查詢

根據(jù)(1)式,有

4.5 假陽性分析

5 安全分析與證明

從索引構(gòu)造算法和查詢陷門生成算法的實現(xiàn)方式可知,在已知密文攻擊模型下STQSSPP是安全的.但在已知背景知識的攻擊模型下,H2是一個確定性單向哈希函數(shù),敵手利用領(lǐng)域知識、關(guān)鍵字統(tǒng)計信息、歷史查詢結(jié)果等背景知識就能對安全索引進行字典攻擊和統(tǒng)計分析,為了彌補這一安全缺陷,可以采用偽隨機函數(shù)PRF：{0,1}*×{0,1}rk→{0,1}s代替H2,而不會影響查詢的正確性.此時,外包給云服務(wù)提供商的加密數(shù)據(jù)集C={ci=Encek(Fi),PRFrk(IDFi),Ii|i=0,1,…,n}.如果采用PRF函數(shù),那么數(shù)據(jù)擁有者需要將密鑰rk和文件解密密鑰ek一并發(fā)送給授權(quán)用戶,數(shù)據(jù)使用者提交如下查詢陷門讓云執(zhí)行秘密查詢操作：

在實際應(yīng)用中,用HMAC-SHA1或HMAC-MD5實現(xiàn)偽隨機函數(shù)PRFrk(·).另外,數(shù)據(jù)文件的安全性由語義安全的對稱加密方案Enc和密鑰ek保證,不是本研究的重點,故不做論述.

現(xiàn)利用文獻[7]中的證明方法來證明STQSSPP的語義安全性.在證明之前,先給出幾個基本概念：

(ⅰ)歷史(History)H：一個歷史H可以看成是在文件集合上的一次查詢請求序列,如數(shù)據(jù)使用者提交一個具有q個查詢關(guān)鍵字的集合Wq={w1,w2,…,wq},在文件集合F上執(zhí)行查詢,表示成一個歷史H={F,Wq}.文件集合F中的文件包括的信息有數(shù)據(jù)文件本身、文件標識號FID及文件F的查詢索引I.

(ⅱ)視圖(View)V(H)：一個歷史H的視圖V(H)可以理解成H的密文形式,敵手只能看到H的視圖V(H),而不能掌握H的任何明文信息.用C(F)表示F和所有文件標識符的密文集合,用C(I)表示F的密文索引集合,用C(Wq)表示W(wǎng)q的密文,于是歷史H的視圖表示為V(H)={C(F),C(I),C(Wq)}.

(ⅲ)蹤跡(Trace)Tr(H)：一個歷史H的蹤跡Tr(H)可以看成關(guān)于V(H)的一個查詢結(jié)果.用Ci表示文件Fi的密文,于是Tr(H)={(Ci,|Ci|)|wj∈Fi∧wj∈Wq,i=1,2,…,n,j=1,2,…,q},云執(zhí)行查詢后僅僅知道密文及其長度.

根據(jù)文獻[5],假設(shè)存在一個概率多項式模擬者S根據(jù)V(H)模擬另一個與V(H)具有相同蹤跡的集合V*(H)={C(F)*,C(I)*,C(Wq)*},若對于任意的概率多項式敵手不能區(qū)分V(H)和V*(H),則STQSSPP是語義安全的.

定理2若PRFrk(·)是偽隨機函數(shù),則查詢陷門是語義安全的,具有陷門不可區(qū)分性.

定理3若PRFrk(·)是偽隨機函數(shù),則STQSSPP中的可查詢索引是語義安全的,具有索引不可區(qū)分性.

證明要證明索引C(I)是語義安全的,只要證明對于模擬者S構(gòu)造的C(I)*,敵手無法區(qū)分C(I)和C(I)*.

因為數(shù)據(jù)擁有者在構(gòu)建索引時采用的是偽隨機函數(shù)PRFrk(·),所以敵手無法獲取密鑰rk,PFRrk(·)的偽隨機性保證沒有任何的概率多項式敵手能夠區(qū)分C(I)和C(I)*.證畢.

定理4令PRFrk(·)是偽隨機函數(shù),假設(shè)某個數(shù)據(jù)擁有者將密鑰rk泄露給云或云勾結(jié)一個妥協(xié)的數(shù)據(jù)使用者,對授權(quán)用戶的查詢隱私發(fā)起合謀攻擊,則在這種強大的內(nèi)部攻擊模型下,查詢陷門仍然是語義安全的,具有陷門不可區(qū)分性.

輸出C(Wq)*={C(wi)*,i=1,2,…,q}.只要數(shù)據(jù)使用者u秘密保存私鑰sku,u的查詢隱私在云掌握rk或勾結(jié)任一個妥協(xié)的數(shù)據(jù)使用者的情況下都是語義安全的,這是因為即使給定映射e,H3(wi)sku和aqu=g11/sku·g2,由于BDHP的計算困難性,敵手無法計算密鑰sku,所以除了數(shù)據(jù)使用者u自己之外,其他任何實體都無法獲取wi的明文信息.因此,隨機的sk*保證了C(Wq)和C(Wq)*是不可區(qū)分的.證畢.

定理5若FHEnc是IND-CCA安全的加密方案,則加密方案FHEncS也是IND-CCA安全的,保證了關(guān)鍵字權(quán)重的語義安全性.

(ⅱ)X從M0和M1中隨機選擇一個向量Mb,計算密文C*=FHDS(pk,Mb),C*作為挑戰(zhàn)密文返回給敵手A.

游戲的其他部分保持不變.

要證明FHEncS是IND-CCA安全的,只需證明對于任意的概率多項式時間的敵手A,對給定安全參數(shù)n,存在可忽略的函數(shù)negl(n),滿足

(6)

證明在游戲中,最終輸出的b可能為0或1,根據(jù)條件概率和FHE,有

(7)

和

易知當i=0時,

當i=l時,

根據(jù)(7)式,有

從而(6)式得證,FHEncS加密方案是IND-CCA安全的,保證了關(guān)鍵字權(quán)重在已知背景知識攻擊下的機密性.證畢.

6 實驗分析

6.1 實驗環(huán)境

所有的文檔采用高級加密標準(Advanced Encryption Standard,AES)加密后進行存儲,偽隨機函數(shù)使用HMAC-SHA1.雙線性對操作的實現(xiàn)采用JPBC函數(shù)庫[21],它是基于配對的密碼庫 (Pairing-Based Cryptography Library,PBC Library)[22]的Java版本,提供所有基于線性對操作的Java接口和函數(shù).實驗采用階為160位大素數(shù)的type A橢圓曲線群,它是一個能提供80位安全強度的對稱雙線性環(huán)境.

為了評估STQSSPP的查詢執(zhí)行時間效率,筆者實現(xiàn)了經(jīng)典的云環(huán)境下外包數(shù)據(jù)查詢方案RSSE和MRSE-2.為RSSE預置系統(tǒng)詞典且建立加密的倒排索引;在MRSE-2方案中,將每個文件作為一條有d=60個屬性的數(shù)據(jù),生成一個d′×d′=80×80的密鑰矩陣和一個d′=80位的位向量,且生成d′-d=20個隨機數(shù)作為填充數(shù)據(jù)向量的元素.

客戶端的配置為Intel Core 2 Duo CPU 2.26 GHz,3 GB內(nèi)存的Windows 7操作系統(tǒng);服務(wù)器端是Intel Core 2 Duo CPU 2×2.394 GHz,有8 GB內(nèi)存的虛擬機環(huán)境,操作系統(tǒng)為centos 5.8.

6.2 索引構(gòu)建時間效率

因為RSSE,MRSE-2和STQSSPP方案在索引構(gòu)建上機制差異較大,所以無法對它們的索引構(gòu)建時間效率進行對比.RSSE基于SSE方案采用倒排索引技術(shù),對詞典中的每一個關(guān)鍵字建立鏈表,鏈表的頭節(jié)點是預置詞典中的一個關(guān)鍵字,鏈表中的每一個節(jié)點包含的信息是文件標識號、保序加密權(quán)重及下一個節(jié)點的解密密鑰等.MRSE-2基于安全k-NN方案構(gòu)建索引的計算主要包括矩陣轉(zhuǎn)置、取逆及數(shù)據(jù)向量的生成.STQSSPP為每一個文件建立一個索引,索引中的信息是文件的查詢關(guān)鍵字.圖3給出了STQSSPP的索引構(gòu)建時間效率.

圖3 密文索引構(gòu)建時間Fig. 3 Construction Time of Ciphertext Index

從圖3(a)可以看出,密文索引的構(gòu)建時間隨著數(shù)據(jù)中的查詢關(guān)鍵字個數(shù)呈線性增長,當文件包含60個查詢關(guān)鍵字時,構(gòu)建一條密文索引的時間大約為3.7 s.

從圖3(b)可以看出,當文件數(shù)量僅為2 000時,整個密文索引集合的構(gòu)建時間就達近1 h,隨著文件數(shù)量的增加,這似乎是非常耗時的過程.但其實在許多實際的應(yīng)用場景中,數(shù)據(jù)擁有者可以對收集的文件定時定期動態(tài)上傳,如數(shù)據(jù)擁有者對每天收集的文件在非工作時間定時上傳,這個數(shù)據(jù)集的規(guī)模一般不是很大,實時性要求也不高.

6.3 查詢陷門構(gòu)建時間效率

查詢時,數(shù)據(jù)使用者在客戶端加密查詢關(guān)鍵字后提交給云.圖4顯示了3種方案的查詢構(gòu)建時間.

圖4 查詢陷門生成時間Fig. 4 Query Trap Generation Time

從圖4可以看出：RSSE和STQSSPP方案的查詢陷門生成時間都與查詢關(guān)鍵字個數(shù)呈線性增長關(guān)系,但在相同數(shù)量的查詢關(guān)鍵字情況下,STQSSPP方案的生成時間高于RSSE,因為1次雙線性對操作的計算時間高于2個偽隨機函數(shù)的加密時間;雖然MRSE-2方案的查詢陷門生成時間不受關(guān)鍵字個數(shù)的影響,但是當關(guān)鍵字少于20時,該方案的生成時間高于其他2種方案.一般地,數(shù)據(jù)使用者用12～16個關(guān)鍵字足以表達他們的查詢需求.當關(guān)鍵字個數(shù)達到20時,STQSSPP的查詢加密時間大概是3.2 s,這對數(shù)據(jù)使用者是可以接受的.

6.4 查詢執(zhí)行時間效率

圖5(a)示出了當用8個關(guān)鍵字查詢時,3種方案在不同文件規(guī)模下的查詢時間;圖5(b)示出了當文件數(shù)量為2 000時,3種方案在不同查詢關(guān)鍵字個數(shù)下的查詢時間.

圖5 查詢執(zhí)行時間Fig. 5 Query Execution Time

從圖5(a)可以看出,MRSE-2方案的查詢時間高于STQSSPP.這是因為MRSE-2在查詢時要進行相對比較耗時的矩陣和向量內(nèi)積運算,而STQSSPP只有簡單的異或和哈希運算.RSSE方案是一個單關(guān)鍵字排序查詢方案,在單關(guān)鍵字查詢的條件下,它的運算主要由一個線性查找、一個異或運算和鏈表中所有節(jié)點的解密運算組成.為了實現(xiàn)多關(guān)鍵字查詢,需要對每一個關(guān)鍵字進行分別查詢,得到多個結(jié)果集合,再對這些集合取交集.從圖5(a)還可以看出：當文件數(shù)量少于600時,RSSE的查詢時間優(yōu)于STQSSPP和MRSE-2,因為當文件數(shù)量較少時,每個鏈表中的節(jié)點數(shù)量較少,與8個查詢關(guān)鍵字對應(yīng)的結(jié)果集合中,包含的文件數(shù)量也較少且有可能是空集;而當文件數(shù)量不斷增多時,RSSE的查詢時間將超過STQSSPP和MRSE-2.

從圖5(b)可以看出：MRSE-2方案的查詢時間不受查詢關(guān)鍵字個數(shù)的影響,一直保持在155 ms左右;STQSSPP和RSSE方案的查詢時間與關(guān)鍵字的個數(shù)呈線性增長關(guān)系,當使用少于5個關(guān)鍵字進行查詢時,RSSE的查詢效率最好,但隨著查詢關(guān)鍵字的增多,RSSE的查詢時間將大大超過STQSSPP和MRSE-2;當查詢關(guān)鍵字的個數(shù)超過16時,STQSSPP的查詢時間也將超過MRSE-2.

6.5 查詢正確性分析

在進行top-k查詢時,為了評估返回給用戶的k個查詢結(jié)果是否都真實反映了查詢與文件的相關(guān)程度,設(shè)Na為結(jié)果中應(yīng)該排在前k位的實際文件數(shù)量,Nu為用戶需要的文件數(shù)量,于是可用

A=Na/Nu

(8)

定義相關(guān)文件排序機制的準確性.(8)式分子部分表示在查詢時有部分應(yīng)該排在前k位的文件,受排序機制的影響并沒有排在前k位,而被排在第k位以后的一些文件取代了.

單關(guān)鍵字查詢時,RSSE和STQSSPP方案依據(jù)查詢關(guān)鍵字在文件中的實際權(quán)重值從大到小進行排序,它們總是能返回與查詢最相關(guān)的前k個文件給用戶.當進行多關(guān)鍵字查詢時,RSSE使用保序加密方案,無法綜合考慮多個關(guān)鍵字在一次查詢中的權(quán)重,而STQSSPP利用同態(tài)加密特性可以實現(xiàn)查詢集合中各個關(guān)鍵字密文權(quán)重的重新運算,以更精確的數(shù)值表示多關(guān)鍵字查詢權(quán)重.MRSE-2根據(jù)查詢關(guān)鍵字向量和文檔向量的內(nèi)積值進行排序,這個內(nèi)積值僅僅反映查詢關(guān)鍵字集合中的元素是否包含在文件中,而沒有反映關(guān)鍵字在文件中的出現(xiàn)頻次或重要程度,所以查詢時將導致大量與查詢更相關(guān)的文件并沒有包含在返回的k個文件之中.

根據(jù)用戶需要返回的不同文件數(shù)量進行分組實驗,每組實驗都在規(guī)模為2 000的數(shù)據(jù)集合上完成同一個多關(guān)鍵字查詢,查詢包含8個關(guān)鍵字.查看每組實驗返回的結(jié)果,并與實際應(yīng)該返回的文件進行對比,然后計算rank值,得到top-k查詢準確率(圖6).

圖6 Top-k查詢準確率Fig. 6 Top-k Query Accuracy Rate

從圖6可以看出,STQSSPP總是能正確返回前k個最相關(guān)文件,RSSE中包含的相關(guān)文件隨著用戶需要返回文件數(shù)量的增加而線性減少,MRSE方案在定義的查詢權(quán)重下總是只能返回近50%的最相關(guān)文件.

表2給出了STQSSPP的正確率(Precision Rate,用P表示)和召回率(Recall Rate,用R表示),它們是信息檢索領(lǐng)率中使用最廣泛的2個檢索評價參數(shù).正確率是返回的結(jié)果中相關(guān)文檔所占的比例,定義為P=N/M,其中N表示返回結(jié)果中相關(guān)文檔的數(shù)目,M表示返回結(jié)果的總數(shù).召回率是返回的相關(guān)文檔占所有相關(guān)文檔的比例,定義為R=N/K,其中K表示所有相關(guān)文檔的數(shù)目.

表2 查詢正確率和召回率Table 2 Query Recall Rate and Accuracy Rate %

從表2可以看出：(1)隨著查詢關(guān)鍵字的增多,查詢的正確率有所下降.查詢關(guān)鍵字越多,布魯姆過濾器產(chǎn)生假陽性的可能性就越大,但合適的哈希函數(shù)數(shù)量可以保證假陽性的概率達到最小.(2)召回率一直保持100%.布魯姆過濾器不會產(chǎn)生漏判現(xiàn)象,它總是返回數(shù)據(jù)集合中所有與查詢相關(guān)的文檔.

7 結(jié)語

基于云環(huán)境下的數(shù)據(jù)外包服務(wù)模式,筆者設(shè)計了一個用戶隱私增強的加密數(shù)據(jù)查詢方案.除了典型的半可信威脅模型外,進一步考慮了用戶查詢的隱私性,構(gòu)建了攻擊性更強的合謀攻擊威脅模型,并證明了在此模型下用戶的隱私是安全的.STQSSPP方案構(gòu)造的安全索引具有多項式時間內(nèi)不可區(qū)分性,且支持文件的動態(tài)更新,非常適合開放和數(shù)據(jù)頻繁更新的云環(huán)境.為了增強用戶的查詢體驗,減少網(wǎng)絡(luò)傳輸帶寬,設(shè)計了IND-CCA安全的數(shù)值密文比較方法,實現(xiàn)了能抵御已知背景知識攻擊的密文相關(guān)性排序機制,滿足用戶個性化top-k查詢的需求.STQSSPP方案不足之處在于,隨著查詢關(guān)鍵字的增多,密文索引的構(gòu)建時間隨著查詢關(guān)鍵字個數(shù)呈線性增長,查詢的正確率也有所下降.因此,筆者接下來將在滿足查詢安全性、查詢結(jié)果的相關(guān)性排序的同時,進一步提高查詢效率.