盧冰潔 周 俊 曹珍富

(上海市高可信計算重點實驗室(華東師范大學) 上海 200062)

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)的飛速增長使得維護、管理和利用數(shù)據(jù)逐漸變得困難.因此，越來越多的企業(yè)和個人都傾向于將數(shù)據(jù)外包到云上以節(jié)省本地存儲和維護數(shù)據(jù)的開銷.為了保護敏感數(shù)據(jù)，數(shù)據(jù)擁有者往往會選擇將數(shù)據(jù)加密后再上傳至云服務器，然而這會導致檢索數(shù)據(jù)變得困難.因此，如何在加密的數(shù)據(jù)庫上實現(xiàn)安全且高效的關鍵字搜索成為一個亟待解決的問題.

對稱可搜索加密技術(symmetric searchable encryption, SSE)[1]是一種允許第三方對用戶上傳的加密數(shù)據(jù)進行檢索，同時不會泄露除搜索模式和搜索結(jié)果外任何信息的一種密文技術.早期的對稱可搜索加密往往僅適用于靜態(tài)環(huán)境，即加密數(shù)據(jù)一旦上傳至云服務器就不再進行修改與更新.但在實際應用中，用戶往往希望能夠?qū)崿F(xiàn)數(shù)據(jù)庫的更新，例如文件的插入、刪除等，為此提出了動態(tài)對稱可搜索加密的概念[2].然而在動態(tài)SSE環(huán)境下，數(shù)據(jù)的添加和刪除將會比搜索泄露更多的隱私信息.最近，Zhang等人[3]提出了一種針對動態(tài)可搜索加密方案的攻擊，敵手可以通過向服務器注入少量文件來破壞用戶的查詢隱私.為了抵抗這種攻擊，前向安全[4-5]的定義和方案相繼被提出.這種方案可以防止舊的搜索令牌對新添加的密文文檔進行搜索，因此大大降低了暴露令牌和數(shù)據(jù)集隱私的可能性.

目前大部分的動態(tài)對稱可搜索加密方案僅支持單用戶，不適用于多用戶環(huán)境.這是由于這些方案往往要求客戶端在本地維護關鍵字的狀態(tài)信息以生成最新的限門.在這種設計下，其他用戶只能向數(shù)據(jù)擁有者詢問最新的關鍵字狀態(tài)信息才能夠生成限門，這就要求數(shù)據(jù)擁有者始終保持在線狀態(tài).為了解決這個問題，最近，Wang等人[6]提出了一種支持多用戶且前向安全的動態(tài)可搜索加密方案MFS，該方案通過引入代理服務器來存儲關鍵字信息和用戶的訪問控制權限，解決了前向安全的多用戶加密數(shù)據(jù)搜索問題.然而，MFS方案中僅給出了簡單的安全性分析，缺乏形式化的安全性定義和證明；并且，我們注意到MFS方案中并未考慮數(shù)據(jù)擁有者和用戶在與代理服務器通信時產(chǎn)生的信息泄露，主要包括2點：

1) 敏感信息泄露.為了使代理服務器得到最新的關鍵字信息，數(shù)據(jù)擁有者需要在每次文件更新發(fā)生時向服務器發(fā)送一些輔助信息，但是這些信息會泄露更新文件中包含的關鍵字與舊的搜索令牌之間的關聯(lián)，使方案無法保持前向安全性.

2) 搜索令牌可關聯(lián).一個用戶對于同一個關鍵字生成的搜索令牌始終是固定值.

針對上述存在的問題，我們提出了一個增強的多用戶前向安全動態(tài)可搜索加密方案.本文的主要貢獻包括3個方面:

1) 指出了MFS方案中存在敏感信息泄露和搜索令牌可關聯(lián)的安全問題，并基于這2個安全問題提出了攻擊的方法.

2) 提出了增強的多用戶前向安全動態(tài)可搜索加密方案EMFS，通過增加用戶與代理服務器之間的通信密鑰，保證了搜索令牌的不可關聯(lián)性.并且，我們還將關鍵字狀態(tài)信息生成全權授權給代理服務器，避免了狀態(tài)信息在傳遞中造成的泄露.此外，我們的方案還采用了一種新的索引結(jié)構，能夠大大提升刪除的效率.

3) 給出了EMFS方案的安全性證明和性能對比，實驗結(jié)果表明盡管我們的方案在查找復雜度上有略微增加，但刪除復雜度從O(nw)降低到O(1)，因此在實際應用中具有更高的效率.

1 相關工作

可搜索對稱加密是一種非常有效的加密工具，能在實現(xiàn)隱私保護的同時保證可搜索性[7].具體來說，一個SSE方案允許數(shù)據(jù)所有者對自己的數(shù)據(jù)進行加密，并將加密的數(shù)據(jù)庫外包給云服務器，之后云服務器在接收到有效的查詢請求時可以對密文進行搜索操作.首個對稱可搜索方案由Song等人[8]提出，通過順序掃描技術來實現(xiàn)搜索操作.此后，諸多SSE方案被不斷提出[9-15]，大大豐富SSE的查詢表達性，提升了方案安全性和性能.

隨后，為了滿足數(shù)據(jù)動態(tài)性的要求，文獻[2]提出了首個動態(tài)可搜索加密方案，實現(xiàn)了搜索和更新操作.但是，動態(tài)可搜索加密在數(shù)據(jù)添加和數(shù)據(jù)刪除過程中會泄露額外的信息.例如敵手可以分析新添加或刪除的文檔是否包含先前搜索的關鍵字.Cash等人[16]對動態(tài)SSE方案的泄露進行了研究，表明即使是最小的泄露也能夠被攻擊者利用來揭示用戶查詢的內(nèi)容，導致泄露濫用攻擊.最近Zhang等人[3]提出的一種惡意攻擊稱為文件注入攻擊，通過向數(shù)據(jù)庫中注入少量文件來破壞用戶的查詢隱私.為了抵抗上述攻擊，Stefanov等人[4]首先提出了2個安全性概念，即前向安全和后向安全，并提出了一個類ORAM構造的前向安全的動態(tài)可搜索加密方案.隨后，Bost[5]在2016年提出了一個基于陷門原語支持增添前向安全動態(tài)可搜索加密方案,并正式給出了前向安全的定義.2017 年Bost等人[17]給出了后向安全由強到弱3種正式定義，并給出了一個支持單關鍵字搜索且滿足前向和后向安全的動態(tài)可搜索加密方案.

在前向安全方面，文獻[18]提出了可驗證的前向安全動態(tài)可搜索加密方案，使方案適用于惡意服務器環(huán)境.文獻[19]通過樹狀結(jié)構實現(xiàn)了一種支持范圍搜索的前向安全動態(tài)可搜索加密方案.文獻[20-21]提出了一種支持多關鍵字搜索的前向安全動態(tài)可搜索加密方案.

在后向安全方面，文獻[22]提出了一種實現(xiàn)了第3類后向安全的對稱可搜索加密方案，作者構造了一種新的密碼學原語稱為對稱可穿刺加密，大大降低了通過穿刺實現(xiàn)后向加密所需的計算開銷.文獻[23]采用了一次一密的方式構造了一種后向安全的對稱可搜索加密方案，該方案不僅高效，還能實現(xiàn)比第1類后向安全更高的安全性，缺陷是無法支持大量數(shù)據(jù).文獻[24]從第2類、第3類后向安全入手，分別提出了2種滿足后向安全的對稱可搜索加密方案，表明了實現(xiàn)后向安全的成本大大低于實現(xiàn)前向安全的成本.

盡管多用戶在動態(tài)對稱可搜索加密方案中并不少見，如文獻[25]實現(xiàn)了一個支持多用戶的動態(tài)對稱可搜索加密方案，通過密鑰分發(fā)和重新加密技術避免了密鑰共享帶來的一系列問題.文獻[26]將客戶端的授權信息合并到搜索令牌和索引中提出了一個支持布爾型查詢的動態(tài)多用戶可搜索方案.但是，前向安全和后向安全方案在目前大多僅支持單用戶模型.為了支持多用戶環(huán)境，Wang等人[6]首次從單用戶模型進行擴展，提出了一種支持多用戶的前向安全動態(tài)可搜索加密方案MFS，這為現(xiàn)有的單用戶前向安全可搜索方案擴展提供了一種新的思路.然而，MFS方案中仍然存在無法抵抗竊聽攻擊或重放攻擊等安全缺陷，且搜索與刪除效率也有待進一步提高.我們認為這是單用戶擴展至多用戶前向安全動態(tài)對稱可搜索加密方案時必須解決的關鍵問題之一，為此我們提供了一種解決思路并給出了一個新的方案.

2 預備知識

2.1 雙線性映射

設G1,G2均為階為素數(shù)p的乘法循環(huán)群，其中g是G1的生成元. 雙線性映射e：G1×G1→G2具有3條性質(zhì)：

1) 雙線性.對于任意u,v∈G1，a,b∈Zp，有e(ua,vb)=e(u,v)ab.

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

3) 可計算性.對于任意u,v∈G1，e(u,v)的計算應該是高效的.

2.2 偽隨機函數(shù)

定義函數(shù)F：{0,1}λ×{0,1}m→{0,1}n，我們稱其為偽隨機函數(shù)，如果對于所有概率性多項式時間的區(qū)分器D有：|Pr[DF(k,.)=1|k←{0,1}λ]-Pr[Dg=1|g←{Func[m,n]}]|≤negl(λ)，其中negl(λ)是一個可忽略函數(shù).

2.3 偽隨機置換

3)F和F-1可以通過確定性多項式算法高效地計算.

3 系統(tǒng)模型

方案中涉及4類實體：數(shù)據(jù)擁有者(data owner, DO)、數(shù)據(jù)使用者(data user, DU)、云服務器(cloud server, CS)和代理服務器(proxy server, PS)，具體系統(tǒng)模型如圖1所示.

1) 數(shù)據(jù)擁有者負責為需要上傳的文檔選取對應關鍵字，加密并上傳文檔，并為文檔生成輔助信息.其中，密文發(fā)送到云服務器，輔助信息發(fā)送到代理服務器.最后，數(shù)據(jù)擁有者還會為授權用戶生成私鑰，并通過安全信道將私鑰分發(fā)給授權用戶.

2) 云服務器是“誠實且具有好奇心的”，用于存儲加密文件、對應的索引以及用戶信息，同時對代理服務器提交的查詢請求進行響應，并將查詢結(jié)果返回給對應用戶.

3) 代理服務器是“誠實的”，負責為關鍵字生成狀態(tài)信息，存儲每個關鍵字對應的最新狀態(tài)值和用戶驗證信息，負責驗證數(shù)據(jù)使用者的身份，并為數(shù)據(jù)使用者生成搜索令牌提交給云服務器.

4) 數(shù)據(jù)使用者是“誠實的”，可以為需要搜索的關鍵字生成驗證令牌，并將令牌提交給代理服務器，最終得到云服務器返回的搜索結(jié)果.

Fig. 1 System model圖1 系統(tǒng)模型

4 動態(tài)可搜索加密

4.1 形式化定義

在本文的構造中，數(shù)據(jù)擁有者能夠與多個用戶共享文件，但是，只有數(shù)據(jù)所有者可以對數(shù)據(jù)集進行添加和刪除.下面，我們給出了動態(tài)對稱可搜索加密方案的定義：

定義1.動態(tài)對稱可搜索加密(dynamic symmetric searchable encryption, DSSE)方案由多項式時間算法構成：

Setup(1λ,DB)→(SKo,stq,EDB).數(shù)據(jù)擁有者選擇安全參數(shù)1λ和數(shù)據(jù)庫DB作為輸入，輸出為數(shù)據(jù)擁有者的私鑰SKo、關鍵字狀態(tài)值stq和加密數(shù)據(jù)庫EDB.其中，關鍵字狀態(tài)值由代理服務器管理.

Register(u,Ucqt,Udqt)→(SKu,Ucqt′,Udqt′).用戶注冊算法，密鑰由數(shù)據(jù)擁有者和用戶共同生成，最終用戶保留密鑰SKu，代理服務器更新用戶搜索表Ucqt，云服務器更新用戶解密表Udqt.

Delete(SKo,id(f),stq,EDB)→(EDB′).數(shù)據(jù)擁有者運行此算法從數(shù)據(jù)集中刪除文件f，存儲在云服務器上的索引和密文會相應地更新.

Search(w,SKu,stq,EDB)→(rstw).用戶運行此算法搜索包含關鍵字w的文件，搜索令牌由代理服務器生成提交到云服務器，云服務器將結(jié)果集返回給用戶.

Decrypt(rst,SKu)→F.用戶收到云服務器返回的數(shù)據(jù)集rst后，可以用私鑰進行解密，得到滿足查詢結(jié)果的文件集F.

4.2 泄露函數(shù)

本節(jié)給出DSSE方案泄露函數(shù)的一般定義：

1)sp(w)={t:(t,w)∈Q}.搜索模式存儲了查詢和關鍵字之間的映射，該映射用于判斷查詢是否針對同一個關鍵字，其中t代表時間戳.

2)rp(w)=rstt.訪問模式被定義為每個搜索查詢的結(jié)果，其中rstt表示當前匹配關鍵字w的所有文件.

3)UpHist(w).以(t,op,ind)的形式記錄了關鍵字w上的所有更新操作，其中t為時間戳，op為操作符，ind為文件索引.

4.3 安全性定義

4.4 前向安全

DSSE方案的前向安全性要求舊的搜索令牌無法匹配到新的更新，換而言之，數(shù)據(jù)的更新操作不能泄露有關關鍵字的任何信息.我們定義前向安全SSE如下：

5 MFS方案分析

為了更好地闡述我們的觀點，本節(jié)首先介紹Wang等人[6]提出的多用戶前向安全動態(tài)可搜索加密方案MFS，并對方案中存在的安全性問題進行了分析，最后介紹了攻擊的方法.

5.1 MFS方案

5.1.1 初始化算法Setup(1λ)

5.1.2 文件添加算法Add(SK，f,W,EDB)

1)DataOwner(SK,f)：給定一個文件f，文件標識符indf，文檔中包含的所有關鍵字W(f)，從G1中隨機選取rf，計算文件加密密鑰ekf=h3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，將(Cf,rf)發(fā)送給云服務器.此外，對于每個關鍵字w∈W(f)，執(zhí)行操作：

①addr(w,indf)=H1(sk1,w‖indf);

②k(w,indf)=H2(sk2,w‖indf);

③tw=F(ks,w);

④Tr(w)=h2(ê(h1(w),g2)wk);

⑤e2=indf⊕F(k(w,indf),tw);

⑥AddTuple←(Tr(w),addr(w,indf),

k(w,indf),tw,e2);

⑦ 將AddTuple發(fā)送給代理服務器.

2)ProxyServer(AddTuple,W)：代理服務器收到AddTuple=(Tr(w),addr(w,indf),k(w,indf),tw,e2)后，執(zhí)行操作：

① ifW[Tr(w)]=null then

②s←{0,1}λ;

③e1=〈0μ‖s〉⊕〈Tr(w)‖F(xiàn)(k(w,indf),

addr(w,indf))〉;

④ else

⑤ (addr(w,indc),k(w,indc),tw)←

W[Tr(w)];

⑥e1=〈addr(w,indc)‖k(w,indc)〉⊕

〈Tr(w)‖F(xiàn)(k(w,indf),addr(w,

indf))〉;

⑦ end if

⑧W[Tr(w)]←(addr(w,indf),k(w,

indf),tw);

⑨AddTuple← (addr(w,indf),e1,e2);

⑩ 將AddTuple發(fā)送給云服務器.

3)CloudServer(AddTr,EDB)：云服務器更新T，使得T[addr(w,indc)]←(e1,e2).

5.1.3 用戶注冊算法Register(u)

5.1.4 搜索算法Search((w,qku),(qkc,stq),(dkc,EDB))

1)DataUser(w,qku)：計算Tru(w)=h1(w)qku，將(uid,Tru(w))發(fā)送給代理服務器.

2)ProxyServer(Tru(w),uid,qkc,W):給定搜索用戶的uid以及查詢令牌Tru(w)，執(zhí)行操作：

① ifUcqt[uid]≠⊥ then

②qkc←Ucqt[uid];

③ else

④ 非授權用戶，程序結(jié)束;

⑤ end if

⑥Tr(w)=h2(ê(Tru(w),qkc));

⑦ ifW[Tr(w)]≠⊥ then

⑧ (addr(w,indf),k(w,indf),tw)←

W[Tr(w)];

⑨SearchTrapdoor←(Tru(w),addr(w,

indf),tw,k(w,indf));

⑩ 將SearchTrapdoor和uid發(fā)送給云服務器;

3)CloudServer(SearchTrapdoor,uid,qkc,EDB)：初始化2個集合ResultSet和rst用于存放查詢結(jié)果及數(shù)據(jù)，并執(zhí)行操作：

① whileaddr(w,indc)≠0μdo

②ind=T[addr(w,indc)].e2⊕F(k(w,

indc),iw);

③ 〈addr(w,indc)‖k(w,indc)〉←

T[addr(w,indc)].e⊕〈Tr(w)‖

F(k(w,indf),addr(w,indf))〉;

④ResultSet←ResultSet∪ind;

⑤ end while

⑥dkc=U[uid];

⑦ for eachind∈ResultSetdo

⑧cdsind=ê(rind,dkc);

⑨rst←rst∪(cdsind,Cind);

⑩ end for

5.1.5 解密算法Decrypt(rst,dku)

用戶收到數(shù)據(jù)集rst后執(zhí)行操作：

①F=null;

② for each (cdsind,Cind)∈rst

④f=AES.Decrypt(dkind,Cind);

⑤F=F∪f;

⑥ end for

最終得到所有符合查詢的結(jié)果.

5.2 安全性問題

MFS方案是首個在單用戶模型下擴展至多用戶模型的前向安全動態(tài)可搜索加密方案，為了解決前向安全和多用戶合并的問題，作者引入了第三方代理服務器來存儲關鍵字信息和用戶的訪問控制權限.然而由于作者將代理服務器設置為半可信，使得數(shù)據(jù)擁有者不得不泄露某些信息以達到托管關鍵字信息的目的.由于代理是半可信的，本質(zhì)上這是把部分泄露轉(zhuǎn)移到了代理服務器上，違背前向安全的性質(zhì).因此盡管MFS方案中考慮了諸多安全因素，其中依然存在2項嚴重的安全性問題，最終致使MFS方案無法保證前向安全性.

1) 敏感信息泄露.在文件添加算法Add中，我們注意到用戶將AddTuple直接發(fā)送給代理服務器，其中包含了關鍵字標識符tw，這是極度不安全的，因為舊的搜索令牌中同樣包含了tw，而前向安全要求隱藏更新文件與舊的搜索令牌之間的關系.

2) 搜索令牌可關聯(lián).對于某一用戶，他搜索同一關鍵字時向代理服務器提交的令牌始終是一個固定值，這使敵手可以輕易偽裝成任何用戶.

5.3 攻擊方法

根據(jù)5.2節(jié)分析的安全性問題，我們給出2種攻擊方法：

1) 竊聽攻擊.敵手通過監(jiān)聽數(shù)據(jù)擁有者向代理服務器發(fā)送的信息來維護一個關鍵字文件表，每當數(shù)據(jù)擁有者向代理服務器發(fā)送更新令牌AddTuple時，敵手將AddTuple中的關鍵字標識符tw和文件ind存放到表中(ind可以通過AddTuple中的其他值計算).對于竊聽敵手來說，盡管他并不知道tw對應的關鍵字，但是他能輕而易舉地將搜索令牌與更新文件進行關聯(lián)(搜索令牌中同樣包含tw)，這對保證方案的前向安全性是十分不利的.

2) 重放攻擊.敵手維護一個用戶令牌表，存放用戶向代理服務發(fā)送的令牌，一旦發(fā)現(xiàn)數(shù)據(jù)擁有者更新了一個新的文件，敵手就將他存儲的所有令牌發(fā)送給代理服務器.在這種情況下，云服務器不斷獲得用戶搜索過的所有關鍵字對應的最新搜索令牌.如果令牌包含了最新的更新索引，那么云服務器就掌握了更新文件所包含的關鍵字.注意此時沒有任何用戶提交有關該文件的搜索請求，云服務器應對該文件中包含的關鍵字保持未知.

6 EMFS方案

6.1 數(shù)據(jù)結(jié)構

我們的方案采用了狀態(tài)鏈構造，如圖2所示，每個關鍵字對應一條狀態(tài)鏈，所有匹配關鍵字w的文件標識符都存放在鏈中，當客戶端想要搜索關鍵字w時，他向服務器發(fā)送最后一個狀態(tài)stc+1，服務器可以從stc+1開始反向遍歷狀態(tài)鏈獲得所有先前狀態(tài)stc,stc-1,…,st1，最終獲得所有查詢結(jié)果.需要注意的是，服務器無法從當前狀態(tài)stc+1獲取下一個狀態(tài)stc+2，這也確保了方案的前向安全性.為了進一步提高搜索和更新的效率，我們采用隨機生成的方式來生成狀態(tài)值.

Fig. 2 Update and search in our scheme圖2 更新和查找圖示

為了使方案適應多用戶環(huán)境，我們選擇引入一個誠實的代理服務器來維護關鍵字的狀態(tài)值，并將狀態(tài)值的生成全權及交給代理服務器，避免用戶生成狀態(tài)值傳遞給服務器導致的信息泄露.需要注意的是，為了保證方案的非交互性，代理服務器除了記錄關鍵字最新的狀態(tài)信息外，還會額外保存各關鍵字對應的文件數(shù)和用戶的搜索次數(shù)用于用戶驗證(令牌的生成與這些信息相關).雖然敵手可能會獲知這些信息，例如某用戶的查詢次數(shù)，但我們認為在未持有密鑰的情況下，敵手偽造令牌的概率僅為一個可忽略值.

6.2 具體構造

6.2.1 初始化算法Setup(1λ)

6.2.2 文件添加算法Add(SKo,f,W,EDB)

1)DataOwner(SKo,f)：給定一個文件f，文件標識符indf，文檔中包含的所有關鍵字W(f)，從G1中隨機選取rf，計算文件加密密鑰ekf=H3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，將(Cf,rf)發(fā)送給云服務器. 此外，初始化一個集合τupd，對于每個關鍵字w∈W(f)，執(zhí)行操作：

①Files[w]=Files[w]+1 ;

②tw=F(ks,w);

③updw=R1(KG,tw‖add‖ind‖F(xiàn)iles[w]);

④τupd=τupd∪updw.

然后，將τupd發(fā)送給代理服務器.

2)ProxyServer(KG,W,τupd)：代理服務器收到τupd后，初始化一個集合τtd，并執(zhí)行操作：

① for eachupdw∈τupddo

updw);*根據(jù)op的不同分別代表文

③ (stc,c)←W[tw];

④ ifFiles[w]≠c+1 then

⑤ return “無效令牌”;

⑥ else ifc=0 then

⑦stc+1←{0,1}λ;

⑧e=H2(tw‖stc+1)⊕(⊥‖op‖ind);

⑨ else

⑩stc+1←{0,1}λ;

3)CloudServer(τtd,EDB)：云服務器根據(jù)收到的τtd執(zhí)行操作：

① for each (u,e)∈τtddo

②T[u]=e;

③ end for

6.2.3 用戶注冊算法Register(u)

6.2.4 搜索算法Search((w,SKu),(qku,W),(dkc,EDB))

1)DataUser(w,SKu)：給定搜索的關鍵字w，執(zhí)行操作：

① (uid,qku,ks,dku,s)←SKu;

②tw=F(ks,w);

③s=s+1;

④τu=R2(qku,tw‖s);

⑤SKu←(uid,qku,ks,dku,s).

將(uid,τu)發(fā)送給代理服務器.

2)ProxyServer(uid,W,Ucqt,τu):給定搜索用戶的uid以及令牌τu，執(zhí)行操作：

① (qku,sc)←Ucqt[uid];

③ ifs≠sc+1 then

④ return “無效令牌”;

⑤ end if

⑥ (stc,c)←W[tw];

⑦τw←(tw,stc);

⑧ ifstc=⊥ then

⑨ 返回消息“none”給用戶u;

⑩ else

3)CloudServer(uid,Udqt,τw)：給定搜索用戶的uid以及搜索令牌τw=(tw,stc)，云服務器初始化3個集合Δ，R和rst并執(zhí)行操作：

①head=H1(tw‖stc);

②flag=false;

③ whilestc≠⊥ do

④u=H1(tw‖stc);

⑤e=T[u];

⑥ (stc‖op‖ind)=e⊕H2(tw‖stc);

⑦ ifop=delthen

⑧Δ=Δ∪ind;

⑨ ifu≠headthen

⑩ 刪除當前塊;

6.2.5 刪除算法Delete(id(f),W(f),SKo,P)

1)DataUser(id(f),W(f),SKo)：對于每個關鍵字w∈W(f)，執(zhí)行操作：：

①Files[w]=Files[w]+1;

②tw=F(ks,w);

③updw=R1(KG,tw‖del‖ind‖F(xiàn)iles[w]);

④τupd=τupd∪updw.

然后，將τupd發(fā)送給代理服務器.

2)ProxyServer(KG,W,τupd)：代理服務器執(zhí)行算法見6.2.2節(jié).

3)CloudServer(τtd,EDB)：云服務器執(zhí)行算法見6.2.2節(jié).

6.2.6 解密算法Decrypt(rst,dku)

用戶收到數(shù)據(jù)集rst后執(zhí)行操作：

①F=null;

② for each (cdsind,Cind)∈rstdo

③dkind=H3(cdsinddku);

④f=AES.Decrypt(dkind,Cind);

⑤F=F∪f;

⑥ end for

最終得到所有符合查詢的結(jié)果.

7 安全性分析和證明

7.1 安全性分析

在給出EMFS方案的安全性證明前，我們首先從文件和索引的安全性、驗證令牌的不可偽造性、搜索令牌的保密性來分析方案的安全性.

1) 文件安全性.文件由數(shù)據(jù)擁有者在本地加密后上傳到云服務器，在本文中，我們選擇用主流的對稱加密算法AES來加密文件.AES 算法的安全性保證了在密鑰不外泄的情況下，敵手無法區(qū)別一串0的加密與文件的加密，保證了文件的安全性.

2) 身份驗證令牌的不可偽造性.方案中采用了可逆?zhèn)坞S機函數(shù)來生成身份驗證令牌，所需的密鑰由代理服務器和用戶持有，并且生成的驗證令牌僅僅能夠使用一次.在密鑰不外泄的情況下，可逆?zhèn)坞S機函數(shù)的安全性保證了敵手無法區(qū)分隨機值和一個驗證數(shù)據(jù)的加密，故我們認為敵手僅有可忽略的概率可以偽造驗證令牌.

3) 搜索令牌的保密性.存儲在云服務器端的索引中保存的并非是真正的關鍵字，而是關鍵字的標識符.在未持有密鑰的情況下，我們認為云服務器無法根據(jù)標識符推測出其中的關鍵字的相關信息.

7.2 安全性證明

混淆0：規(guī)定所有算法都按照協(xié)議運行.

算法1.系統(tǒng)初始化模擬算法.

①k←AES.KeyGen(1λ);

② 初始化字典Dict存放模擬索引;

③ 初始化字典KeyStore存放模擬關鍵字標識符;

④ 初始化字典ST存放模擬狀態(tài)值;

算法2.添加令牌模擬算法.

② fori=1 toμfdo

③ 隨機生成(u,e)對;

④ 將(id(f),(u,e))添加到字典Dict;

⑥ end for

⑦c=ASE.Enc(k,0|f|);

算法3.搜索令牌模擬算法.

②rst←rp(w);

③ ifKeyStore[w]=null then

④ 隨機生成KeyStore[w];

⑤ end if

⑥tw=KeyStore[w];

⑦ ifST[w]=null then

⑧ 隨機生成stc;

⑨ST[w]←(rst,stc);

⑩ else ifrst?ST[w].allrstthen

算法4.刪除令牌模擬算法.

② 從Dict中隨機選取一個包含μf個關鍵字的文件id(f);

③ fori=1 toμfdo

④ 從Dict中取出(id(f),(u,,e))對;

⑤ 隨機生成新的(udel,edel)對;

⑦ 將字典Dict的(id(f),(u,,e))替換為

(id(f),(u,v,udel,edel));

⑧ end for

證畢.

8 性能分析

本節(jié)給出EMFS方案與MFS方案的性能對比.

為了更好地展現(xiàn)實驗結(jié)果，我們首先給出方案的計算通信開銷復雜度對比，如表1所示.其中nw表示當搜索發(fā)生時匹配關鍵字w的文件個數(shù)，aw表示關鍵字w上更新次數(shù)之和.相比于MFS方案，我們方案的刪除操作不需要遍歷數(shù)據(jù)鏈，復雜度僅為O(1)，但由于數(shù)據(jù)鏈中包含部分需要刪除的塊，因此搜索復雜度略微升高.

表2中給出了2個方案的性能對比，為了更簡明地進行對比，我們主要考慮限門生成以及服務器查詢鏈表所需的開銷.其中，tBE表示執(zhí)行雙線性配對(bilinear pairing)和指數(shù)運算(exponential operation)合計所需要的時間，tma表示執(zhí)行異或運算(modular addition)所需要的時間，λ表示安全參數(shù)，n代表插入或刪除文件中包含的關鍵字個數(shù).可以觀察到我們的方案較MFS方案在計算和通信方面的開銷都有所降低，這是由于我們通過偽隨機置換來生成令牌，而MFS方案中生成令牌需要進行雙線性和指數(shù)操作.此外，我們的方案為了減少信息的泄露，去除了部分不必要的數(shù)據(jù)傳輸，因此通信開銷也優(yōu)于MFS方案.

Table 1 Comparison of Search and Update Complexity Between MFS and EMFS

Table 2 Performance Comparison Between MFS and IMFS

我們在Windows 7操作系統(tǒng)上(單核的Intel Core i5 4590 K 3.30 GHz CPU，內(nèi)存4 GB)進行了仿真實驗，采用Java編程語言，并通過jsCrypto庫實例化方案的加密操作.其中，偽隨機函數(shù)的實現(xiàn)采用了128 b HMAC-MD5，Hash函數(shù)的實現(xiàn)用的是160 b HMAC-SHA1，加密文檔使用的是256 b密鑰的對稱加密算法AES，關鍵詞狀態(tài)表則通過Hash表實現(xiàn)，以寫入文件的方式進行存儲，需要使用時再從文件中讀取，加密索引的存儲則采用了持久化的Key-Value數(shù)據(jù)庫Redis以加快存取速度.

Fig. 3 Performance evaluation of search on client side圖3 客戶端搜索效率對比

為了評估2個方案中用戶端搜索關鍵字的效率，我們選取了一系列出現(xiàn)頻率不同的關鍵詞，將匹配數(shù)據(jù)集的大小從10增加到105分別進行搜索，并計算出檢索匹配項所需的平均時間.如圖3所示，當匹配文檔數(shù)量增加時，平均搜索時間會隨之降低，這是由于方案在搜索時需要執(zhí)行一些一次性操作，譬如讀取文件中存放的最新狀態(tài)值和生成搜索令牌等等，這些操作耗費的時間會平均地分配到每個匹配結(jié)果項中.我們方案的搜索效率是優(yōu)于MFS的，這是由于在MFS方案中生成搜索令牌需要通過雙線性配對，耗時較大.而在我們的方案中搜索令牌則通過一個偽隨機置換生成，搜索效率更高.

Fig. 4 Performance evaluation of search on data owner side圖4 數(shù)據(jù)擁有者端搜索效率對比

數(shù)據(jù)擁有者端在搜索關鍵字的效率如圖4所示，需要注意的是，此時云服務器并不需要計算匹配項的文件密鑰，開銷相比于客戶端大幅度降低.同樣，我們的方案在用戶端的搜索效率也是優(yōu)于MFS方案的.

如圖5所示，我們給出方案在云服務器端的刪除效率對比.我們將刪除的數(shù)據(jù)集的大小從104增加到4×104，可以觀察到隨著文件數(shù)的增加，MFS方案的響應時間以一種線性方式增加，這是因為MFS在每次刪除時都需要遍歷數(shù)次鏈表(遍歷次數(shù)與當前文件包含的關鍵字數(shù)有關)，而在EMFS方案中(我們考慮實際鏈表中塊的刪除，即刪除操作與搜索綁定)，我們認為刪除最多需要遍歷N條鏈表，其中N代表刪除數(shù)據(jù)集中包含的關鍵字總數(shù).

Fig. 5 Performance evaluation of delete on cloud server side圖5 云服務器端刪除算法效率對比

9 總 結(jié)

本文發(fā)現(xiàn)了Wang等人[6]提出的MFS方案存在的安全性問題，并針對這些存在問題提出了一個改進的方案EMFS.通過避免關鍵字信息在數(shù)據(jù)擁有者和代理服務器之間的傳遞和增加用戶驗證機制，我們保證了在引入第三方代理服務器時，方案仍能保持前向安全性.此外，我們還給出了方案的安全分析和證明，表明我們的方案具有良好的安全性.最后，通過性能評估，證明我們的方案比EMF方案擁有更高的刪除效率，在實際應用中效果更佳.