支持聯(lián)合搜索的動態(tài)前向安全可搜索加密方案

湯永利 李靜然 閆璽璽 趙 強

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 預(yù)備知識

2.1 布谷鳥過濾器

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

Fig. 1 Illustration of cuckoo Hash圖1 布谷鳥Hash圖解

本文引用文獻[27]中提出的布谷鳥過濾器.具體細節(jié)為：

(1)

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

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

2.2 密文等值測試

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

簡化的密文等值測試方案PKEET′：

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

3 算法定義和安全模型

3.1 算法定義

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

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

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

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

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

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

3.2 安全模型

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

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

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

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

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

3.3 前向安全

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

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

sp(x)表示搜索模式：

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

qp(x)表示問詢模式：

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

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

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

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

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

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

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

4.1.3 用戶狀態(tài)

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

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

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

4.1.4 布谷鳥過濾器

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

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

1) 插入算法CFInsert(tag).輸入文件標簽tag，無輸出.將指紋f=fingerprint(tag)插入布谷鳥過濾器相應(yīng)的桶中.計算2個候選桶bucket[i1]和bucket[i2]：

(3)

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

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

3) 刪除算法CFDelete(tag).輸入文件標簽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é)對FSSE-CT方案進行詳細說明.

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

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

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

2) 選取由密鑰控制的Hash函數(shù)HFSSE:{0,1}*→{0,1}2μ+ν+1+log N.隨機選取2個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控制的偽隨機函數(shù)FFSSE，輸入輸出字符串長度相等.

4.2.2 更新階段

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

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

用戶端：

① 生成新數(shù)據(jù)塊b.輸入σ，調(diào)用ReGen()得到關(guān)鍵詞w的信息(id,key).根據(jù)op，對W[w].cnt執(zhí)行相應(yīng)操作(W[w].cnt++/--).再次調(diào)用ReGen()得到塊b的標識符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生成標簽tag←Htag(ind).

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

服務(wù)器端：

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

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

用戶端：

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

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

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

服務(wù)器端：

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

⑥ 執(zhí)行Lookup(tag)找到布谷鳥過濾器中對應(yīng)的桶.若op==add直接將C′添加到桶中，若op==del從桶中的第2個元素開始執(zhí)行PKEET′.T(C′,Cb)找到返回為True的Cb并刪除.

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

用戶端：

① 生成2個空集合B←{}，C←{}.

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

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

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

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

服務(wù)器端：

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

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

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

用戶端：

① 生成1個空集合B←{}.

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

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

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

服務(wù)器端：

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

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

4.2.3 搜索階段

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

用戶端：

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

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

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

服務(wù)器端：

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

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

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

5 方案分析

5.1 安全性

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

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

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

證明.設(shè)安全參數(shù)λ，μ，v.這里使用從真實世界衍生出的難以區(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)方案從搜索能力、更新類型等功能方面和搜索時間、更新時間等效率方面，以及用戶端、服務(wù)器端存儲代價3方面進行對比.具體的對比結(jié)果如表1所示:

Table 1 Scheme Comparison表1 方案對比

1) 功能方面.

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

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

2) 效率方面.

3) 存儲代價.

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

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

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

6 實驗結(jié)果

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

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

本實驗以Enron電子郵件數(shù)據(jù)集為測試數(shù)據(jù)集，從布谷鳥過濾器操作時間、整體更新時間、整體搜索時間3個方面進行仿真測試.

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

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

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

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

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

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

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

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

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

6.2 FSSE-CT方案與Scheme-B方案對比實驗

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

Fig. 6 Time consuming comparison between Bloomfilter and cuckoo filter圖6 布隆過濾器和布谷鳥過濾器的耗時對比

Fig. 7 Time consuming comparison of search operation圖7 搜索操作的耗時對比

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

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

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

7 結(jié)束語

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