湯永利 李靜然 閆璽璽 趙 強(qiáng)

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南焦作 454003)

可搜索加密(searchable encryption, SE)是保護(hù)云存儲(chǔ)數(shù)據(jù)安全性的重要加密技術(shù)，用戶將需要存儲(chǔ)的數(shù)據(jù)加密后外包到云，防止云端數(shù)據(jù)泄露，同時(shí)支持云端搜索密文[1-6].然而，在實(shí)際應(yīng)用中，新的安全問(wèn)題日益凸顯.例如向數(shù)據(jù)庫(kù)添加文件時(shí)，可能會(huì)泄露之前搜索的關(guān)鍵詞有哪些包含在更新文件中.為了避免這種信息泄露問(wèn)題，提出前向安全可搜索加密方案，并應(yīng)用于現(xiàn)實(shí)生活中的各種場(chǎng)景[7-13].Stefanov等人[14]于2014年首次系統(tǒng)地定義了前向安全可搜索加密(forward secure searchable encryption, FSSE)的概念，并給出一個(gè)具體的FSSE方案，但該方案更新開(kāi)銷巨大.2016年Bost[15]提出基于陷門(mén)置換的公鑰加密FSSE方案∑oφoζ，該方案具有良好的更新能力和搜索復(fù)雜度.但因該方案由非對(duì)稱原語(yǔ)構(gòu)造，所以在索引、更新和令牌生成過(guò)程中都具有較大的消耗.2019年Wei等人[16]對(duì)∑oφoζ進(jìn)行改進(jìn)，基于對(duì)稱原語(yǔ)的密鑰塊鏈技術(shù)提出一種前向安全的可搜索加密方案.2019年Hu等人[17]提出支持聯(lián)合關(guān)鍵詞搜索的前向安全可搜索加密方案，其基礎(chǔ)方案在用戶端加入布隆過(guò)濾器，服務(wù)器將聯(lián)合問(wèn)詢關(guān)鍵詞中某一個(gè)關(guān)鍵詞的單關(guān)鍵詞搜索結(jié)果發(fā)送給用戶端，然后用戶端使用布隆過(guò)濾器對(duì)所得文檔進(jìn)行二次篩選，得到搜索結(jié)果.該方案增加用戶端的額外存儲(chǔ)量，通信開(kāi)銷較差，且因使用布隆過(guò)濾器，更新能力和文件存儲(chǔ)量受限，只能用于數(shù)量一定的小型文件數(shù)據(jù)庫(kù).其增強(qiáng)方案，為查詢的每個(gè)關(guān)鍵詞添加1個(gè)向量，導(dǎo)致效率不佳.2020年盧冰潔等人[18]提出一種增強(qiáng)的多用戶前向安全可搜索加密方案，在保持前向安全性的同時(shí)將性能擴(kuò)展到多用戶，并且該方案可以抵抗竊聽(tīng)攻擊和重放攻擊.

本文提出一種支持聯(lián)合搜索的方法，在支持單關(guān)鍵詞搜索FSSE方案的基礎(chǔ)上，將搜索能力擴(kuò)展成聯(lián)合搜索.所提方法在服務(wù)器端添加1個(gè)簡(jiǎn)化的布谷鳥(niǎo)過(guò)濾器，同時(shí)使用密文等值測(cè)試技術(shù)加密索引信息，并將加密后的索引存儲(chǔ)于布谷鳥(niǎo)過(guò)濾器中.搜索協(xié)議將查詢關(guān)鍵詞分為2種：1)最低頻的關(guān)鍵詞(與該關(guān)鍵詞相關(guān)的文件最少)；2)其他關(guān)鍵詞.對(duì)最低頻的關(guān)鍵詞執(zhí)行基礎(chǔ)FSSE方案得到查詢結(jié)果，隨后使用布谷鳥(niǎo)過(guò)濾器存儲(chǔ)的信息篩選查詢結(jié)果，最終得到滿足聯(lián)合問(wèn)詢的結(jié)果.本文基于文獻(xiàn)[16]的FSSE-ε方案(其他支持單關(guān)鍵詞搜索的方案同樣有效)，構(gòu)造支持聯(lián)合搜索的前向安全可搜索加密方案FSSE-CT.主要貢獻(xiàn)有4個(gè)方面.

1) 構(gòu)造一種支持聯(lián)合搜索的方法，在任意單關(guān)鍵詞FSSE方案[16]的基礎(chǔ)上，于服務(wù)器端新增1個(gè)擴(kuò)展結(jié)構(gòu)，以存儲(chǔ)加密后的關(guān)鍵詞信息.該結(jié)構(gòu)用于對(duì)聯(lián)合問(wèn)詢的關(guān)鍵詞進(jìn)行二次篩選，且支持更靈活的文件-關(guān)鍵詞對(duì)更新.

2) 在服務(wù)器端采用布谷鳥(niǎo)過(guò)濾器，增強(qiáng)方案的搜索能力和搜索效率.基于布谷鳥(niǎo)過(guò)濾器自身添加/刪除和快速查詢的功能，本方案支持4種更新方式：文件-關(guān)鍵詞集合添加、刪除，單個(gè)文件-關(guān)鍵詞對(duì)添加、刪除工作，并在一定程度上提升方案效率.

3) 采用密文等值測(cè)試技術(shù)，對(duì)需要存于布谷鳥(niǎo)過(guò)濾器相應(yīng)桶中的關(guān)鍵詞使用密文等值測(cè)試技術(shù)構(gòu)造加密信息，實(shí)現(xiàn)搜索階段對(duì)聯(lián)合關(guān)鍵詞進(jìn)行有效篩選的同時(shí)，完成對(duì)關(guān)鍵詞信息的隱藏.

4) 給出所提方案的安全性證明和性能對(duì)比.結(jié)果表明，該方案滿足自適應(yīng)模型下不可區(qū)分性安全.與其他方案性能對(duì)比分析表明，該方案在搜索方式、更新類型等功能方面更加全面且靈活.并且將聯(lián)合搜索方案的更新時(shí)間降至對(duì)稱加密操作耗時(shí)O(ts)，同時(shí)在用戶端存儲(chǔ)代價(jià)不變的基礎(chǔ)上，將服務(wù)器端存儲(chǔ)代價(jià)降至.對(duì)每人關(guān)鍵詞-文件對(duì)存儲(chǔ)ind長(zhǎng)度和2個(gè)群G中元素長(zhǎng)度O(N)×(λ+2|G|).

1 相關(guān)工作

1.1 前向安全可搜索加密方案

前向安全可搜索加密希望達(dá)成的目標(biāo)是：惡意服務(wù)器在文件更新階段不泄露任何數(shù)據(jù)庫(kù)中已有數(shù)據(jù)的信息.2005年Chang等人[19]的方案已支持前向安全，該文指出文件更新時(shí)，新增文件可能與之前已查詢過(guò)的關(guān)鍵詞相關(guān)，從而泄露某些信息.2014年前向安全可搜索加密的概念由Stefanov等人[14]系統(tǒng)提出，同時(shí)還提出后向安全的概念.隨后學(xué)者們相繼提出各種的方案[20-23]，但這些方案普遍具有開(kāi)銷過(guò)大或者無(wú)法在現(xiàn)實(shí)世界中實(shí)現(xiàn)的問(wèn)題.2016年Bost[15]提出了第1個(gè)具有良好的通信開(kāi)銷和計(jì)算復(fù)雜度的FSSE方案——∑oφoζ，該方案在建立索引的過(guò)程中通過(guò)陷門(mén)置換隱藏文件標(biāo)簽和關(guān)鍵詞之間的關(guān)系，在新的文件注入時(shí)，不泄露之前已查詢文件的信息.2019年Wei等人[16]提出基于對(duì)稱原語(yǔ)的密鑰塊鏈技術(shù)，該技術(shù)不依賴獨(dú)立索引生成規(guī)則，可以與任意形式的索引結(jié)構(gòu)聯(lián)用，擴(kuò)展了前向安全可搜索加密的靈活性，且在快速搜索和令牌生成方面具有較高的效率.

1.2 支持多關(guān)鍵詞的前向安全可搜索加密方案

2018年Zuo等人[24]提出2種支持范圍查詢的前向安全可搜索加密方案：1)將∑oφoζ與樹(shù)狀結(jié)構(gòu)結(jié)合以支持范圍搜索；2)將替換為Paillier加密的字符串，同時(shí)支持前向/向后安全.隨后Hu等人[17]提出支持聯(lián)合搜索的前向安全可搜索加密方案.給出2種解決方法，基礎(chǔ)方案在用戶端引入布隆過(guò)濾器篩選文件，加強(qiáng)方案使用內(nèi)積加密(inner-product encryption, IPE)方法代替布隆過(guò)濾器.Wu等人[25]構(gòu)建了1個(gè)基于虛擬二叉樹(shù)的結(jié)構(gòu)(virtual binary tree, VBTree)，有效地實(shí)現(xiàn)前向安全的聯(lián)合關(guān)鍵詞搜索.當(dāng)從葉到根的所有節(jié)點(diǎn)都包含所有查詢的關(guān)鍵詞時(shí)，服務(wù)器可以自上而下執(zhí)行聯(lián)合關(guān)鍵詞搜索并返回葉節(jié)點(diǎn)作為搜索結(jié)果.但該方案中服務(wù)器可通過(guò)對(duì)每個(gè)查詢的關(guān)鍵詞執(zhí)行搜索來(lái)直接獲取大量泄露.Wang等人[26]構(gòu)造2種有效的聯(lián)合關(guān)鍵詞FSSE方案，且不會(huì)產(chǎn)生明顯的泄露.其基礎(chǔ)方案因引入XSet表格，存儲(chǔ)開(kāi)銷增加；增強(qiáng)方案因在基礎(chǔ)方案上添加RC表格，在計(jì)算過(guò)程中需要對(duì)XSet表格中的信息剝除一次外殼，計(jì)算開(kāi)銷和存儲(chǔ)開(kāi)銷都有所增加.

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

2.1 布谷鳥(niǎo)過(guò)濾器

布谷鳥(niǎo)過(guò)濾器是一種基于Hash函數(shù)的新形式概率數(shù)據(jù)結(jié)構(gòu)，用于測(cè)試集合中的元素資格，它包含1個(gè)由桶組成的數(shù)組.插入到布谷鳥(niǎo)過(guò)濾器中的每個(gè)元素a有2個(gè)候選桶，分別由Hash函數(shù)h1(a)和h2(a)確定.查找a時(shí)，對(duì)由Hash函數(shù)計(jì)算出的2個(gè)桶進(jìn)行查找，看其中一個(gè)是否包含此項(xiàng).圖1左部分顯示了將新元素a插入到包含8個(gè)桶的簡(jiǎn)易布隆過(guò)濾器的示例，其中a可以放在桶2或桶6中.如果a的2個(gè)桶中的任何一個(gè)為空，則算法將a插入到該空閑桶中，插入完成.如果2個(gè)存儲(chǔ)桶都不為空，如本例中的情況，則項(xiàng)目選擇1個(gè)候選存儲(chǔ)桶(如桶6)，踢出現(xiàn)有項(xiàng)目(如a)，并將此項(xiàng)目重新插入到其自己的備用位置.該過(guò)程可能會(huì)重復(fù)，直到如圖1右部分所示找到空桶，或直到達(dá)到最大位移數(shù).如果未找到空桶，則認(rèn)為此Hash表已滿，無(wú)法插入.

Fig. 1 Illustration of cuckoo Hash圖1 布谷鳥(niǎo)Hash圖解

本文引用文獻(xiàn)[27]中提出的布谷鳥(niǎo)過(guò)濾器.具體細(xì)節(jié)為：

(1)

其中,j∈R[b],∈R表示從集合中隨機(jī)選擇1個(gè)元素.重置i,j索引的k，tij=??tij=k(i=i⊕h(k)，j∈[b]).若不存在這樣的tij，則重復(fù)上述過(guò)程，從式(1)中得k.

測(cè)試集合成員a∈S：首先檢測(cè)是否存在i,j，使i∈{h(a),h(a)⊕h(fp(a))}，j∈[b]且tij=fp(a).若條件成立則稱大概率a∈S(a?S的概率忽略不計(jì))；若條件不成立則稱a?S.錯(cuò)誤率與存儲(chǔ)在布谷鳥(niǎo)過(guò)濾器中的指紋大小相關(guān)，指紋越長(zhǎng)錯(cuò)誤率越低.從S中刪除a時(shí)，僅需檢測(cè)是否存在i,j滿足tij=fp(a)，i∈{h(a),h(a)⊕h(fp(a))}，j∈[b].若存在，將tij置為空.

2.2 密文等值測(cè)試

簡(jiǎn)單地講，密文等值測(cè)試就是檢查2個(gè)密文是否由同一明文加密[28].本文對(duì)文獻(xiàn)[29]中的密文等值技術(shù)進(jìn)行簡(jiǎn)化.使用雙線性映射技術(shù)，對(duì)不同公鑰生成的2個(gè)密文進(jìn)行等值測(cè)試.

簡(jiǎn)化的密文等值測(cè)試方案PKEET′：

2)PKEET′.T(C1,C2).給定密文C1=(U1,V1)和C2=(U2,V2).若e(U1,V2)=e(U2,V1)，則返回True，否則返回False.

3 算法定義和安全模型

3.1 算法定義

基于文獻(xiàn)[16]的FSSE-ε方案、文獻(xiàn)[27]的布谷鳥(niǎo)過(guò)濾器和文獻(xiàn)[29]的密文等值測(cè)試技術(shù)，構(gòu)造一種支持聯(lián)合搜索的前向安全可搜索加密方案FSSE-CT.該方案由1個(gè)算法和2個(gè)協(xié)議組成：Π=(Setup,Update,Search).

1) 系統(tǒng)初始化算法.Setup(1λ)→(uk,W,T,CF).該算法輸入安全參數(shù)λ；輸出密鑰uk、空映射W、空樹(shù)T、空布谷鳥(niǎo)過(guò)濾器CF.

2) 更新協(xié)議.Update()=(Update(),UpKW(),AddInd(),DelInd()).該協(xié)議根據(jù)不同的操作要求由4個(gè)算法組成.

① 更新樹(shù)算法UpdateTree(op,(w,ind),σ)→(T).用戶端、服務(wù)器端合作完成.輸入更新操作op∈{add,del}(添加或刪除)、文件-關(guān)鍵詞對(duì)(w,ind)、用戶狀態(tài)σ={w,W[w].cnt}；服務(wù)器輸出更新后的樹(shù)T.

② 文件-關(guān)鍵詞對(duì)更新算法UpKW(op,w,ind,σ)→(T,CF).用戶端、服務(wù)器端合作完成.用戶端輸入操作op∈{add,del}、該文件包含的關(guān)鍵詞集合w={w1,w2,…,wn}、待添加文件ind、用戶狀態(tài)σ；服務(wù)器端輸出更新后的數(shù)據(jù)庫(kù)樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

③ 文件添加算法AddInd(op=add,w={w1,w2,…,wn},ind,σ)→(T,CF).用戶端、服務(wù)器端合作完成.用戶端輸入操作op=add、該文件包含的關(guān)鍵詞集合w={w1,w2,…,wn}、待添加文件ind、用戶狀態(tài)σ；服務(wù)器端輸出更新后的數(shù)據(jù)庫(kù)樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

④ 文件刪除算法DelInd(op=del,w={w1,w2,…,wm},ind,σ)→(T,CF).用戶端、服務(wù)器端合作完成.用戶端輸入刪除操作op=del、該文件包含的關(guān)鍵詞集合w={w1,w2,…,wm}、待添加文件ind、用戶狀態(tài)σ；服務(wù)器端輸出更新后的數(shù)據(jù)庫(kù)樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

3) 搜索協(xié)議.Search(w1∧w2∧…∧wd,σ)→(T,Q).用戶端、服務(wù)器端合作完成.用戶端輸入待問(wèn)詢聯(lián)合關(guān)鍵詞(w1∧w2∧…∧wd)、用戶狀態(tài)σ，服務(wù)器端輸出更新后的數(shù)據(jù)庫(kù)樹(shù)T和問(wèn)詢結(jié)果文件En(ind)集合Q.

3.2 安全模型

FSSE-CT的安全模型由現(xiàn)實(shí)世界SSEReal和理想世界SSEIdeal的游戲定義.SSEReal等同于FSSE-CT方案中的操作，SSEIdeal由模擬器S構(gòu)造.定義泄露函數(shù)L=(LSetup,LUpdate,LSearch)，表示敵手A可以從Setup()，Update()，Search()算法中獲取的泄露信息，且敵手能獲取信息的范圍不會(huì)超出泄露函數(shù)L.

在現(xiàn)實(shí)世界游戲SSEReal中，敵手A運(yùn)行Setup()并獲得EDB.隨后A執(zhí)行搜索問(wèn)詢或更新問(wèn)詢以獲取信息.在理想世界游戲SSEIdeal中，模擬器S輸入LSetup(λ,DB).隨后敵手A進(jìn)行搜索或更新問(wèn)詢，模擬器S相應(yīng)地通過(guò)泄露函數(shù)LSearch(q)或LUpdate(op,in)回復(fù)問(wèn)詢，給A提供信息.最終，A輸出b∈{0,1}表示對(duì)SSEReal和SSEIdeal的區(qū)分.

定義1.L-自適應(yīng)安全(L-adaptively-secure).如果存在1個(gè)模擬器S，使得對(duì)于任意概率多項(xiàng)式時(shí)間PPT敵手，都有：

|P[SSERealA(λ)=1]-
P[SSEIdealA,S(λ)=1]|≤negl(λ),

則該對(duì)稱可搜索加密方案是L-自適應(yīng)安全的.

3.3 前向安全

前向隱私是防止動(dòng)態(tài)對(duì)稱可搜索加密方案(dynamic searchable symmetric sncryption, DSSE)泄露的強(qiáng)大屬性.簡(jiǎn)單地講，這意味著更新不會(huì)泄露已更新關(guān)鍵詞的任何信息.本文引用文獻(xiàn)[16]中前向隱私技術(shù)的定義.

1) 泄露.泄露函數(shù)L=(LSetup,Search,LUpdate)表示FSSE協(xié)議泄露給敵手的信息量.泄露函數(shù)L將問(wèn)詢列表LQ(到目前為止所有問(wèn)詢的列表)看作狀態(tài).將每次對(duì)關(guān)鍵詞w的問(wèn)詢表示為(i,w)，或?qū)⑤斎胫禐镮N的更新問(wèn)詢OP表示為(i,OP,IN).其中整數(shù)i表示初始值為0的時(shí)間戳，隨問(wèn)詢次數(shù)的增加而增加.

sp(x)表示搜索模式：

sp(x)={j:(j,x)∈LQ}(僅匹配搜索問(wèn)詢).

qp(x)表示問(wèn)詢模式：

qp(x)={j:(j,x)∈LQor (j,op,in)∈LQ
且x出現(xiàn)在IN中}.

2) 前向安全.引用文獻(xiàn)[15]中的定義.

定義2.若更新泄露函數(shù)LUpdate可以表示為式(2)，則L-自適應(yīng)安全的方案∑是前向安全的.

LUpdate(OP,IN)=L′(OP,{(indi,ui)}),

(2)

其中,{(indi,ui)}表示修改后的文檔集合，ui表示被更新文件indi的修改數(shù)量.

4 方案構(gòu)造

本節(jié)具體描述支持聯(lián)合搜索的動(dòng)態(tài)前向安全可搜索加密方案FSSE-CT.原理上該方案可以將任何支持單關(guān)鍵詞搜索的FSSE擴(kuò)展成支持聯(lián)合關(guān)鍵詞搜索的方案，且不會(huì)造成重大的泄露.即，構(gòu)造一種聯(lián)合搜索的方法：在服務(wù)器端添加1個(gè)簡(jiǎn)化的布谷鳥(niǎo)過(guò)濾器，將經(jīng)密文等值測(cè)試技術(shù)構(gòu)造后的加密關(guān)鍵詞存于該過(guò)濾器中，以篩選聯(lián)合關(guān)鍵詞，得到所需結(jié)果.本文以與FSSE-ε方案[16]結(jié)合為例完成完整的方案.

4.1 存儲(chǔ)結(jié)構(gòu)

4.1.1 倒排索引構(gòu)造SE

4.1.2 構(gòu)造二叉索引樹(shù)

構(gòu)造二叉索引樹(shù)T，存儲(chǔ)加密后的文件信息.

3) 生成1個(gè)塊鏈.執(zhí)行CInit()初始化鏈C.對(duì)每個(gè)待存入鏈C的塊b執(zhí)CAddHead().鏈接這些塊，將1個(gè)塊的ptr和key設(shè)置為下一個(gè)塊的數(shù)據(jù)標(biāo)識(shí)符和加密密鑰(尾部塊中為⊥)；加密塊的標(biāo)識(shí)符和加密密鑰并存儲(chǔ)在先前的塊中(將頭塊中的ptr和key存儲(chǔ)于用戶端)以隱藏關(guān)系.

4.1.3 用戶狀態(tài)

使用對(duì)稱加密原語(yǔ)構(gòu)造單向置換函數(shù)P:{0,1}λ→{0,1}λ，Pkρ(x)為由密鑰kρ控制的置換函數(shù).選取由密鑰控制的偽隨機(jī)函數(shù)FFSSE，輸入輸出值長(zhǎng)度相同.定義偽隨機(jī)函數(shù)PRF G: W→{0,1}λ，W表示關(guān)鍵詞或關(guān)鍵詞的唯一標(biāo)識(shí)符iw≤W.選取由密鑰控制的Hash函數(shù)HRG，輸出值為μbit的字符串.

重新生成算法ReGen(w,c)：

1) 若W[w].cnt==-1，分別設(shè)置id，key為⊥.

4.1.4 布谷鳥(niǎo)過(guò)濾器

在服務(wù)器端構(gòu)造簡(jiǎn)化的布谷鳥(niǎo)過(guò)濾器，存儲(chǔ)快速篩選文件ind的信息.具體地，隨機(jī)選取2個(gè)Hash函數(shù)fingerprint:{0,1}*→{0,1}m，Hc:{0,1}*→{0,1}l，構(gòu)建布谷鳥(niǎo)過(guò)濾器的布谷鳥(niǎo)Hash表，基礎(chǔ)單元為entry.Hash表由多個(gè)存儲(chǔ)桶bucket數(shù)組組成.每個(gè)存儲(chǔ)桶bucket可以存儲(chǔ)多個(gè)entry.每個(gè)桶的首個(gè)entry用于存放索引該桶的指紋f=fingerprint(tag)，其余的entry用于存放加密后的關(guān)鍵詞.在本方案中每個(gè)桶代表1個(gè)文件，由文件標(biāo)簽tag索引，桶中存放該文件包含的所有關(guān)鍵詞(經(jīng)加密的).

服務(wù)器端為所有的tag分配桶.具體操作為：

1) 插入算法CFInsert(tag).輸入文件標(biāo)簽tag，無(wú)輸出.將指紋f=fingerprint(tag)插入布谷鳥(niǎo)過(guò)濾器相應(yīng)的桶中.計(jì)算2個(gè)候選桶bucket[i1]和bucket[i2]：

(3)

若存在bucket[i2]或bucket[i1]為空，則將指紋f添加到該桶的第1個(gè)塊中.若都不為空，則i←R{i1,i2}.取出桶bucket[i]中存放的指紋f；計(jì)算i=i⊕Hc(f)；若bucket[i]為空，則添加f到bucket[i].循環(huán)這個(gè)步驟，找到合適的位置，插入指紋.循環(huán)次數(shù)需小于最大踢出量MaxNumKicks，若達(dá)到MaxNumKicks則插入失敗.

2) 查詢算法CFLookup(tag).輸入文件標(biāo)簽tag，判斷若tag存在則返回True，否則返回False.即，生成f=fingerprint(tag)，執(zhí)行式(3)，得到相應(yīng)的桶bucket[i1]，bucket[i2].若桶中含有f則返回True，否則返回False.

3) 刪除算法CFDelete(tag).輸入文件標(biāo)簽tag，刪除相應(yīng)桶中的指紋f，成功返回True，否則返回False.即生成f=fingerprint(tag)，執(zhí)行式(3)，得到相應(yīng)的桶bucket[i1]，bucket[i2].若桶中含有f則移除并返回True，否則返回False.

4.2 方案結(jié)構(gòu)

本節(jié)對(duì)FSSE-CT方案進(jìn)行詳細(xì)說(shuō)明.

4.2.1 系統(tǒng)初始化階段

Setup(1λ).輸入：安全參數(shù)λ，μ，ν，ο.輸出：密鑰uk←R{0,1}λ，uk*←R{0,1}λ、用戶狀態(tài)σ、空樹(shù)T、空簡(jiǎn)化布谷鳥(niǎo)過(guò)濾器CF.

1) 定義G1，G2是q上的2個(gè)乘法循環(huán)群，階為素?cái)?shù)q，g為群G的生成元，定義雙線性映射e:G1×G1→G2.

2) 選取由密鑰控制的Hash函數(shù)HFSSE:{0,1}*→{0,1}2μ+ν+1+log N.隨機(jī)選取2個(gè)Hash函數(shù)Htag:{0,1}*→{0,1}ν，HRG:{0,1}*→{0,1}μ.

3) 生成密鑰uk←R{0,1}λ，uk*←R{0,1}λ.

4) 為單向置換函數(shù)P選擇密鑰kP.

5) 選取由密鑰uk控制的偽隨機(jī)函數(shù)FFSSE，輸入輸出字符串長(zhǎng)度相等.

4.2.2 更新階段

本方案支持3種更新操作：文件添加、文件刪除、關(guān)鍵詞更新.每個(gè)操作分為2步：1)更新樹(shù)T；2)更新布谷鳥(niǎo)過(guò)濾器中的桶.

1) 更新樹(shù)T階段UpdateTree(op,(w,ind),σ;EDB).用戶端、服務(wù)器端合作完成.輸入：更新操作op←{add/del}、(w,ind)對(duì)、用戶狀態(tài)σ={w,W[w].cnt}，W[w]表示關(guān)鍵詞w的映射.輸出：加密后的數(shù)據(jù)庫(kù)樹(shù)T.即通過(guò)在服務(wù)器端插入由用戶端構(gòu)建的塊b，實(shí)現(xiàn)(w,ind)對(duì)的更新.

用戶端：

① 生成新數(shù)據(jù)塊b.輸入σ，調(diào)用ReGen()得到關(guān)鍵詞w的信息(id,key).根據(jù)op，對(duì)W[w].cnt執(zhí)行相應(yīng)操作(W[w].cnt++/--).再次調(diào)用ReGen()得到塊b的標(biāo)識(shí)符id*和加密密鑰key*.b.value=tag‖En(ind)‖op，b.key=key，b.ptr=id.生成mask←HFSSE(key*,id*)，用于加密b.value，b.key，b.ptr.

② 為文件ind生成標(biāo)簽tag←Htag(ind).

③ 將構(gòu)建好的塊b發(fā)送到服務(wù)器端.

服務(wù)器端：

④ 將從用戶端接收到的塊b插入樹(shù)T.

2) 單個(gè)關(guān)鍵詞更新階段UpKW(op,w′,ind,σ;T，CF).用戶端、服務(wù)器端合作完成.輸入：更新操作op、待更新關(guān)鍵詞w′、文件ind、用戶狀態(tài)σ.輸出：更新后的樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

用戶端：

① 修改用戶狀態(tài)σ中關(guān)鍵詞w′索引的文件個(gè)數(shù)(根據(jù)op，W[w].cnt++/--)，調(diào)用UpdateTree()生成b.

③ 生成文件ind的標(biāo)簽tag←Htag(ind).

④ 將{b,(C′,op),tag}發(fā)送給服務(wù)器端.

服務(wù)器端：

⑤ 服務(wù)器端接收到{b,(C″,op),tag}后，將塊b插入到樹(shù)T中.

⑥ 執(zhí)行Lookup(tag)找到布谷鳥(niǎo)過(guò)濾器中對(duì)應(yīng)的桶.若op==add直接將C′添加到桶中，若op==del從桶中的第2個(gè)元素開(kāi)始執(zhí)行PKEET′.T(C′,Cb)找到返回為T(mén)rue的Cb并刪除.

3) 文件添加階段AddInd(op=add,{w1,w2,…,wn},ind,σ;EDB,CF).用戶端、服務(wù)器端合作完成.用戶端輸入添加操作op=add、待添加文件ind、關(guān)鍵詞集合{w1,w2,…,wn}、用戶狀態(tài)σ；服務(wù)器端輸出更新后的樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

用戶端：

① 生成2個(gè)空集合B←{}，C←{}.

② 修改文件ind中每個(gè)wi(i∈{1,2,…,n})相關(guān)文件個(gè)數(shù)W[w].cnt++，然后調(diào)用UpdateTree()生成n個(gè)塊{b1,b2,…,bn}，并將這n個(gè)塊存入集合B中.

③ 執(zhí)行PKEET′.E(wi)為加密wi.即，隨機(jī)選擇ri←R計(jì)算Ui=gri，Vi=，得到待測(cè)試內(nèi)容為Ci=(Ui,Vi)，將Ci存于集合C中.

④ 生成文件ind的標(biāo)簽tag←Htag(ind).

⑤ 最后將{B,C,tag}發(fā)送給服務(wù)器端.

服務(wù)器端：

⑥ 服務(wù)器端接收到{B,C,tag}后，先將B中的塊b逐個(gè)插入到樹(shù)T中.

⑦ 執(zhí)行CFInsert(tag)找到布谷鳥(niǎo)過(guò)濾器中對(duì)應(yīng)的桶，并將C中內(nèi)容逐個(gè)插入該桶.

4) 文件刪除階段DelInd(op=del,w={w1,w2,…,wm},ind,σ;T，CF).用戶端、服務(wù)器端合作完成.用戶端輸入操作op=del、關(guān)鍵詞集合w={w1,w2,…,wm}、文件ind、用戶狀態(tài)σ；服務(wù)器端輸出更新后的樹(shù)T和布谷鳥(niǎo)過(guò)濾器CF.

用戶端：

① 生成1個(gè)空集合B←{}.

② 對(duì)文件ind的每個(gè)(wtag,ind)，t∈{1,2,…,m}，修改wt相關(guān)文件的個(gè)數(shù)W[w].cnt--，然后調(diào)UpdateTree()共生成n個(gè)塊{b1,b2,…,bn}，并將這n個(gè)塊存入集合B中.

③ 生成文件ind的標(biāo)簽tag←Htag(ind).

④ 將{B,tag}發(fā)送給服務(wù)器端.

服務(wù)器端：

⑤服務(wù)器端接收到{B,tag}后，先將B中的塊b逐個(gè)插入到樹(shù)T中.

⑥執(zhí)行CFDelete(tag)，刪除布谷鳥(niǎo)過(guò)濾器相應(yīng)桶中的所有元素.

4.2.3 搜索階段

Search((w1∧w2∧…∧wd),σ;EDB,R).用戶端、服務(wù)器端合作完成.用戶端輸入問(wèn)詢聯(lián)合關(guān)鍵詞集合(w1∧w2∧…∧wd)，用戶狀態(tài)σ；服務(wù)器端輸出更新的樹(shù)T和問(wèn)詢結(jié)果文件En(ind)集合R.

用戶端：

1) 生成空集合Q←{}.

2) 查詢?chǔ)业玫絳w1,w2,…,wd}中W[w].cnt最小的關(guān)鍵詞w(設(shè)為w1).調(diào)用ReGen(w1,W[w1].cnt)得到W[w1].id，W[w1].key.

3) 對(duì)除w1外的其他關(guān)鍵詞ws(s∈{2,3,…,m})執(zhí)行PKEET′.E(ws)，選取rs←R(值可以相同或不同)，計(jì)算Us=grs，Vs=得到測(cè)試內(nèi)容為Qs=(Us,Vs)，將Qs存于集合Q中.

4) 生成令牌t←{W[w1].id,W[w1].key,Q}.

服務(wù)器端：

5) 生成3個(gè)空集合S←{}，C←{}，R←{}.

7) 對(duì)所有b.value∈S，先執(zhí)行CFLookup(tag)找到布谷鳥(niǎo)過(guò)濾器中相應(yīng)的桶，將桶中除首個(gè)entry(f)外的所有元素添加到集合C中.對(duì)所有的Qs∈Q與C′∈C進(jìn)行PKEET′.T(Qs,C′)操作.若所有的對(duì)比結(jié)果都為False，則說(shuō)明該b.value對(duì)應(yīng)的文件ind不滿足聯(lián)合問(wèn)詢；若每個(gè)Qs都查出存在C中的元素與其對(duì)比結(jié)果為T(mén)rue，則說(shuō)明該b.value對(duì)應(yīng)的文件ind滿足聯(lián)合問(wèn)詢，將其中的En(ind)存入集合R.

8) 最終將聯(lián)合搜索的結(jié)果R返回給用戶端.

5 方案分析

5.1 安全性

在隨機(jī)預(yù)言機(jī)模型下證明本方案滿足自適應(yīng)性安全.

方案中LSetup=⊥，即初始化不泄露任何信息.在搜索協(xié)議中，用戶端將關(guān)鍵詞w1的搜索令牌，和其他關(guān)鍵詞經(jīng)密文等值測(cè)試構(gòu)造的加密信息一起發(fā)送到服務(wù)器.在這一過(guò)程中僅會(huì)泄露問(wèn)詢關(guān)鍵詞的個(gè)數(shù)，由于每個(gè)關(guān)鍵詞都經(jīng)過(guò)加密，且用于加密的r都是隨機(jī)產(chǎn)生的，所以不會(huì)泄露除w1的部分信息外的信息.在更新過(guò)程中，所有的函數(shù)都是輸入更新操作、關(guān)鍵詞、文件標(biāo)識(shí)符、用戶狀態(tài)，后經(jīng)用戶端計(jì)算，輸出加密后的集合B，C和相關(guān)文檔標(biāo)識(shí)符，并將得到的結(jié)果發(fā)送給服務(wù)器.服務(wù)器端僅需將B和C中的元素插入到相應(yīng)的位置，因此服務(wù)器無(wú)法得知更新后的文檔與先前查詢的關(guān)鍵詞之間的匹配關(guān)系LUpdate=⊥.

此外，定義Hist(w)表示關(guān)鍵詞w的歷史.它列出了一段時(shí)間內(nèi)對(duì)DB(w)做的所有修改.FFSSE表示由密鑰控制的偽隨機(jī)函數(shù)，輸入λbit隨機(jī)字符串和密鑰uk，輸出λbit字符串.HFSSE，Htag，HRG均是建模于隨機(jī)預(yù)言機(jī)模型的安全Hash函數(shù).

證明.設(shè)安全參數(shù)λ，μ，v.這里使用從真實(shí)世界衍生出的難以區(qū)分的游戲幫助證明該定理.

① tag←{0,1}ν;② if Htag(ind)≠⊥ then③ Bad←True,tag←Htag(ind);④ end if⑤ tag[ind]←tag;⑥ Htag(ind);⑦ u←Htag(ind);⑧ if u=⊥ then⑨ u←R{0,1}ν;⑩ if ?ind,s.t. tagind∈tag[] then Bad←True,u←tag[ind]; end if Htag(ind)←u;end if return u.

結(jié)論：根據(jù)以上游戲和模擬器S.由于HFSSE，Htag，HRG都是Hash函數(shù)，可得：

證畢.

5.2 性能分析

將本方案與相關(guān)方案從搜索能力、更新類型等功能方面和搜索時(shí)間、更新時(shí)間等效率方面，以及用戶端、服務(wù)器端存儲(chǔ)代價(jià)3方面進(jìn)行對(duì)比.具體的對(duì)比結(jié)果如表1所示:

Table 1 Scheme Comparison表1 方案對(duì)比

1) 功能方面.

① 搜索能力.文獻(xiàn)[15]∑οφοζ方案和文獻(xiàn)[16]FSSE-ε方案僅支持單關(guān)鍵詞搜索，其余方案連同本文FSSE-CT方案均可實(shí)現(xiàn)聯(lián)合關(guān)鍵詞搜索.

② 更新類型.Hu等人[17]的Scheme-E方案僅支持對(duì)整個(gè)文件的更新操作.其余方案均僅支持文件-關(guān)鍵詞對(duì)的更新操作.而本文方案，不僅支持單個(gè)文件-關(guān)鍵詞對(duì)的更新操作，也支持對(duì)整體文件信息的更新操作，相對(duì)于其他方案有較靈活的更新能力.

2) 效率方面.

3) 存儲(chǔ)代價(jià).

① 用戶端存儲(chǔ)代價(jià)，除Scheme-B方案外，其余方案都是對(duì)每個(gè)關(guān)鍵詞包含的文件個(gè)數(shù)進(jìn)行存儲(chǔ)(其余的信息通過(guò)后期計(jì)算得到)，具有相同的空間復(fù)雜度O(W′logD)，Scheme-B方案在此基礎(chǔ)上額外存儲(chǔ)了1個(gè)布隆過(guò)濾器.

② 服務(wù)器端存儲(chǔ)代價(jià)，∑οφοζ方案、FSSE-ε方案因僅支持單關(guān)鍵詞查詢空間復(fù)雜度為O(N)×λ.Scheme-B方案將布隆過(guò)濾器放置在用戶端，服務(wù)器端空間復(fù)雜度也為O(N)×λ.Scheme-E方案額外為每個(gè)元件存儲(chǔ)用于IPE計(jì)算的向量，空間復(fù)雜度為O(N)×λ×W′.OXT-E方案額外存儲(chǔ)3個(gè)表格用于篩選聯(lián)合搜索的關(guān)鍵詞空間復(fù)雜度為O(N)×(λ+2|本文方案僅額外增加1個(gè)布谷鳥(niǎo)過(guò)濾器，空間復(fù)雜度減少至O(N)×(λ+2|G|).顯然本文具有一定的存儲(chǔ)優(yōu)勢(shì).

綜上所述，本文支持聯(lián)合搜索，并且具有相對(duì)靈活的更新操作，即本文可以對(duì)單個(gè)文件-關(guān)鍵詞對(duì)進(jìn)行更新操作，也可以對(duì)整個(gè)文件集合進(jìn)行操作,且更新效率較佳.同時(shí)，在支持聯(lián)合搜索的方案中，本文方案無(wú)論是用戶端存儲(chǔ)還是服務(wù)器端存儲(chǔ)都具有優(yōu)勢(shì).

6 實(shí)驗(yàn)結(jié)果

本節(jié)對(duì)FSSE-CT方案進(jìn)行實(shí)驗(yàn)性能分析，分別從基于大數(shù)據(jù)集的實(shí)驗(yàn)和與Scheme-B[17]對(duì)比實(shí)驗(yàn)2個(gè)方面，對(duì)本文方案進(jìn)行實(shí)驗(yàn)評(píng)估.因FSSE-CT方案基于FSSE-ε，所以僅對(duì)擴(kuò)展聯(lián)合搜索性能的部分進(jìn)行評(píng)估，并用將擴(kuò)展開(kāi)銷與FSSE-ε開(kāi)銷相加的方式來(lái)計(jì)算方案的總體性能.

6.1 基于大數(shù)據(jù)集的FSSE-CT方案實(shí)驗(yàn)

本實(shí)驗(yàn)以Enron電子郵件數(shù)據(jù)集為測(cè)試數(shù)據(jù)集，從布谷鳥(niǎo)過(guò)濾器操作時(shí)間、整體更新時(shí)間、整體搜索時(shí)間3個(gè)方面進(jìn)行仿真測(cè)試.

Enron電子郵件數(shù)據(jù)集含有51.7萬(wàn)個(gè)文檔，從中提取出167.20萬(wàn)個(gè)關(guān)鍵詞、0.86億個(gè)關(guān)鍵詞-文件對(duì)，其中超過(guò)100萬(wàn)個(gè)關(guān)鍵詞僅匹配1個(gè)文檔，且大多數(shù)文檔的匹配關(guān)鍵詞數(shù)少于10個(gè)(本方案以關(guān)鍵詞數(shù)量為10為例設(shè)置參數(shù))，將整個(gè)數(shù)據(jù)集插入到1個(gè)空的rocksdb數(shù)據(jù)庫(kù)中.

本實(shí)驗(yàn)的硬件環(huán)境為Intel Core i5-3337 CPU和8 GB DDR3 RAM的個(gè)人計(jì)算機(jī).使用FSSE-ε給出的開(kāi)源代碼進(jìn)行基礎(chǔ)FSSE方案構(gòu)造.對(duì)稱密鑰長(zhǎng)度λ=256 b，關(guān)鍵詞-文件對(duì)的最大數(shù)量Nmax=232，標(biāo)識(shí)符ind長(zhǎng)度μ=64 b.塊長(zhǎng)度為480 b(值416 b，塊標(biāo)識(shí)符64 b).擴(kuò)展部分為在服務(wù)器端添加1個(gè)經(jīng)加密的布谷鳥(niǎo)過(guò)濾器，在其中存儲(chǔ)每個(gè)關(guān)鍵詞用于密文等值測(cè)試的加密原語(yǔ).使用文獻(xiàn)[27]提出的ssCF布谷鳥(niǎo)過(guò)濾器，大小為2.7 MB，包含9種Hash函數(shù)每項(xiàng)12 b，Hash表具有m=217個(gè)存儲(chǔ)桶，每個(gè)存儲(chǔ)桶由4個(gè)12 b條目和32 b的地址組成.該過(guò)濾器約可存1.3億個(gè)元件，其假陽(yáng)性率為0.09%，構(gòu)建效率為3.13×106個(gè)元件/s.為每個(gè)關(guān)鍵詞存儲(chǔ)的用于進(jìn)行密文等值測(cè)試的加密原語(yǔ)為32 b，總存儲(chǔ)大小為6.4 MB.FSSE-CT方案中對(duì)布谷鳥(niǎo)過(guò)濾器的占用率最多達(dá)到約50%，所以執(zhí)行布谷鳥(niǎo)過(guò)濾器中文件更新和查找操作所消耗的時(shí)間可忽略不計(jì).實(shí)驗(yàn)結(jié)果如圖3～5所示.

Fig. 3 Time of setting/checking cuckoo filter圖3 布谷鳥(niǎo)過(guò)濾器執(zhí)行設(shè)置/查找操作所消耗的時(shí)間

Fig. 4 Average time spent on update operations圖4 更新操作平均消耗的時(shí)間

Fig. 5 Average time spent by search operations圖5 搜索操作平均消耗的時(shí)間

圖3展示在不同規(guī)模的大數(shù)據(jù)集中(Enron電子郵件數(shù)據(jù)集的倍數(shù))，布谷鳥(niǎo)過(guò)濾器執(zhí)行設(shè)置/查找操作所消耗的時(shí)間.橫坐標(biāo)分別取Enron電子郵件數(shù)據(jù)集的20～24倍，分別約0.86億、1.73億、3.46億、6.92億和13.84億個(gè)關(guān)鍵詞-文件對(duì).對(duì)Enron電子郵件數(shù)據(jù)集本身(約0.86億個(gè)關(guān)鍵詞-文件對(duì))執(zhí)行布谷鳥(niǎo)過(guò)濾器設(shè)置/查找操作所消耗的時(shí)間約為0.17 s.21倍時(shí)(約1.73億個(gè)關(guān)鍵詞-文件對(duì))，耗時(shí)約為0.32 s；22倍時(shí)(約3.46億個(gè)關(guān)鍵詞-文件對(duì))，耗時(shí)約為0.63 s；23倍時(shí)(約6.92億個(gè)關(guān)鍵詞-文件對(duì))，耗時(shí)約為1.25 s；24倍時(shí)(約13.84億個(gè)關(guān)鍵詞-文件對(duì))，耗時(shí)約為2.42 s.由圖3可見(jiàn)時(shí)間消耗的增加幾乎與數(shù)據(jù)集的大小成線性關(guān)系.

圖4展示在不同規(guī)模的大數(shù)據(jù)集(Enron電子郵件數(shù)據(jù)集的倍數(shù))中，F(xiàn)SSE-CT方案對(duì)單個(gè)文件-關(guān)鍵詞對(duì)執(zhí)行更新操作所消耗的時(shí)間.即，執(zhí)行FSSE-ε更新操作所消耗的時(shí)間，加上對(duì)關(guān)鍵詞進(jìn)行密文等值測(cè)試加密并將其插入至布谷鳥(niǎo)過(guò)濾器所消耗的時(shí)間.數(shù)據(jù)集大小為Enron電子郵件數(shù)據(jù)集本身時(shí)(約0.86億個(gè)關(guān)鍵詞-文件對(duì))，執(zhí)行更新操作消耗的時(shí)間為0.124 ms；數(shù)據(jù)集大小為1.73億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為0.147 ms;數(shù)據(jù)集大小為3.46億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為0.160 ms；數(shù)據(jù)集大小為6.92億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為0.190 ms；數(shù)據(jù)集大小為13.84億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為0.236 ms.圖3顯示出隨數(shù)據(jù)集的擴(kuò)大，更新操作所消耗的時(shí)間呈線性增長(zhǎng).

圖5展示了在不同規(guī)模的大數(shù)據(jù)集(Enron電子郵件數(shù)據(jù)集的倍數(shù))中，F(xiàn)SSE-CT方案執(zhí)行搜索操作所消耗的時(shí)間.隨著單次聯(lián)合搜索中關(guān)鍵詞數(shù)量的增多，搜索所消耗的時(shí)間會(huì)有所增多.本實(shí)驗(yàn)以對(duì)2個(gè)關(guān)鍵詞進(jìn)行聯(lián)合搜索為例.數(shù)據(jù)集大小為Enron電子郵件數(shù)據(jù)集本身時(shí)(約0.86億個(gè)關(guān)鍵詞-文件對(duì))，執(zhí)行搜索操作消耗的時(shí)間約為14.290 9 ms；數(shù)據(jù)集大小為1.73億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為14.299 3 ms;數(shù)據(jù)集大小為3.46億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為14.293 3 ms；數(shù)據(jù)集大小為6.92億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為14.304 9 ms；數(shù)據(jù)集大小為13.84億個(gè)關(guān)鍵詞-文件對(duì)時(shí)，耗時(shí)約為14.347 7 ms.搜索效率主要受單個(gè)文件包含的關(guān)鍵詞數(shù)量的影響.

綜上所述，本方案實(shí)際性能測(cè)試和理論性能分析一致，且無(wú)論是布谷鳥(niǎo)過(guò)濾器執(zhí)行操作消耗的時(shí)間還是更新、搜索操作消耗的時(shí)間，都是毫秒級(jí)別，在實(shí)際應(yīng)用過(guò)程中具有較高的可操作性.

6.2 FSSE-CT方案與Scheme-B方案對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)的硬件環(huán)境和FSSE-CT方案的參數(shù)設(shè)置與7.1節(jié)相同.將FSSE-CT方案與Scheme-B方案進(jìn)行具體的實(shí)驗(yàn)對(duì)比分析，實(shí)驗(yàn)結(jié)果如圖6～7所示.

Fig. 6 Time consuming comparison between Bloomfilter and cuckoo filter圖6 布隆過(guò)濾器和布谷鳥(niǎo)過(guò)濾器的耗時(shí)對(duì)比

Fig. 7 Time consuming comparison of search operation圖7 搜索操作的耗時(shí)對(duì)比

1) 布隆過(guò)濾器與布谷鳥(niǎo)過(guò)濾器實(shí)驗(yàn)對(duì)比.圖6顯示了Scheme -B方案中使用的布隆過(guò)濾器和FSSE-CT方案中使用的布谷鳥(niǎo)過(guò)濾器的耗時(shí)對(duì)比.如圖6所示，橫坐標(biāo)分別為包含100～1 000個(gè)索引的數(shù)據(jù)集，間隔為100.當(dāng)索引數(shù)為100時(shí)FSSE-CT方案和Scheme-B方案的耗時(shí)分別為0.319 ms和12.723 ms，Scheme-B方案的耗時(shí)高于FSSE-CT方案.2個(gè)方案的耗時(shí)均隨著索引數(shù)的增加而增加.由圖6可見(jiàn)，Scheme-B方案的耗時(shí)增長(zhǎng)速度大于FSSE-CT方案.綜上，F(xiàn)SSE-CT方案使用布谷鳥(niǎo)過(guò)濾器，不論是在時(shí)間消耗量還是在增長(zhǎng)趨勢(shì)方面都具有一定的優(yōu)勢(shì).

2) 搜索操作實(shí)驗(yàn)對(duì)比.圖7顯示了Scheme-B方案和FSSE-CT方案的搜索算法的耗時(shí)比較.橫坐標(biāo)分別為包含100～1 000個(gè)索引的數(shù)據(jù)集，間隔為100.當(dāng)索引數(shù)為100時(shí)，F(xiàn)SSE-CT方案和Scheme-B方案的耗時(shí)分別為10.730 ms和25.058 ms，Scheme-B方案的耗時(shí)高于FSSE-CT方案.Scheme-B方案搜索操作耗時(shí)隨索引數(shù)的增加而增加，而FSSE-CT方案的搜索耗時(shí)在8～15 ms之間浮動(dòng).FSSE-CT方案在時(shí)間消耗和增長(zhǎng)趨勢(shì)上都優(yōu)于Scheme-B方案.

結(jié)果表明，F(xiàn)SSE-CT方案具有良好的計(jì)算效率.且Hu等人.Scheme -B方案中布隆過(guò)濾器存儲(chǔ)在用戶端，增加了用戶端的存儲(chǔ)負(fù)擔(dān)和計(jì)算開(kāi)銷.FSSE-CT方案使用的布谷鳥(niǎo)過(guò)濾器存儲(chǔ)在服務(wù)器端，在不給客戶端增加存儲(chǔ)和計(jì)算負(fù)擔(dān)的同時(shí)，提高計(jì)算效率.

7 結(jié)束語(yǔ)

本文方案在支持單關(guān)鍵詞搜索的前向安全可搜索加密方案的基礎(chǔ)上，采用布谷鳥(niǎo)過(guò)濾器技術(shù)和密文等值測(cè)試技術(shù)，構(gòu)造一種支持聯(lián)合搜索的動(dòng)態(tài)前向安全可搜索加密方案，實(shí)現(xiàn)前向安全基礎(chǔ)下，對(duì)關(guān)鍵詞進(jìn)行聯(lián)合搜索，并且支持更加靈活的更新操作，即支持對(duì)整個(gè)文件信息的添加/刪除和對(duì)單個(gè)文件-關(guān)鍵詞對(duì)的添加/刪除工作.此外本文方案滿足自適應(yīng)模型下不可區(qū)分的安全性.采用密文等值測(cè)試技術(shù)加密保證在對(duì)關(guān)鍵詞進(jìn)行二次篩選時(shí)，不泄露關(guān)鍵詞的相關(guān)信息.同時(shí)由于使用布谷鳥(niǎo)過(guò)濾器進(jìn)行存儲(chǔ)，降低了服務(wù)器端的存儲(chǔ)開(kāi)銷.理論性能分析和實(shí)際性能分析表明，本文方案與相關(guān)方案相比，在更新類型的靈活性、更新時(shí)間、用戶端/服務(wù)器端存儲(chǔ)方面有一定的性能提升.下一步將考慮如何進(jìn)行輕量級(jí)優(yōu)化，提升搜索能力并在實(shí)際應(yīng)用場(chǎng)景中實(shí)現(xiàn).