一種增強(qiáng)的多用戶前向安全動(dòng)態(tài)對(duì)稱(chēng)可搜索加密方案

盧冰潔 周 俊 曹珍富

(上海市高可信計(jì)算重點(diǎn)實(shí)驗(yàn)室(華東師范大學(xué)) 上海 200062)

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2.1 雙線性映射

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

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

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

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

2.2 偽隨機(jī)函數(shù)

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

2.3 偽隨機(jī)置換

3)F和F-1可以通過(guò)確定性多項(xiàng)式算法高效地計(jì)算.

3 系統(tǒng)模型

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

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

2) 云服務(wù)器是“誠(chéng)實(shí)且具有好奇心的”，用于存儲(chǔ)加密文件、對(duì)應(yīng)的索引以及用戶信息，同時(shí)對(duì)代理服務(wù)器提交的查詢(xún)請(qǐng)求進(jìn)行響應(yīng)，并將查詢(xún)結(jié)果返回給對(duì)應(yīng)用戶.

3) 代理服務(wù)器是“誠(chéng)實(shí)的”，負(fù)責(zé)為關(guān)鍵字生成狀態(tài)信息，存儲(chǔ)每個(gè)關(guān)鍵字對(duì)應(yīng)的最新?tīng)顟B(tài)值和用戶驗(yàn)證信息，負(fù)責(zé)驗(yàn)證數(shù)據(jù)使用者的身份，并為數(shù)據(jù)使用者生成搜索令牌提交給云服務(wù)器.

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

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

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

4.1 形式化定義

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

定義1.動(dòng)態(tài)對(duì)稱(chēng)可搜索加密(dynamic symmetric searchable encryption, DSSE)方案由多項(xiàng)式時(shí)間算法構(gòu)成：

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

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

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

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

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

4.2 泄露函數(shù)

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

1)sp(w)={t:(t,w)∈Q}.搜索模式存儲(chǔ)了查詢(xún)和關(guān)鍵字之間的映射，該映射用于判斷查詢(xún)是否針對(duì)同一個(gè)關(guān)鍵字，其中t代表時(shí)間戳.

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

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

4.3 安全性定義

4.4 前向安全

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

5 MFS方案分析

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

5.1 MFS方案

5.1.1 初始化算法Setup(1λ)

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

1)DataOwner(SK,f)：給定一個(gè)文件f，文件標(biāo)識(shí)符indf，文檔中包含的所有關(guān)鍵字W(f)，從G1中隨機(jī)選取rf，計(jì)算文件加密密鑰ekf=h3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，將(Cf,rf)發(fā)送給云服務(wù)器.此外，對(duì)于每個(gè)關(guān)鍵字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ā)送給代理服務(wù)器.

2)ProxyServer(AddTuple,W)：代理服務(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ā)送給云服務(wù)器.

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

5.1.3 用戶注冊(cè)算法Register(u)

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

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

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

① ifUcqt[uid]≠⊥ then

②qkc←Ucqt[uid];

③ else

④ 非授權(quán)用戶，程序結(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ā)送給云服務(wù)器;

3)CloudServer(SearchTrapdoor,uid,qkc,EDB)：初始化2個(gè)集合ResultSet和rst用于存放查詢(xún)結(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(wàn);

⑥ end for

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

5.2 安全性問(wèn)題

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

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

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

5.3 攻擊方法

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

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

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

6 EMFS方案

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

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

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

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

6.2 具體構(gòu)造

6.2.1 初始化算法Setup(1λ)

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

1)DataOwner(SKo,f)：給定一個(gè)文件f，文件標(biāo)識(shí)符indf，文檔中包含的所有關(guān)鍵字W(f)，從G1中隨機(jī)選取rf，計(jì)算文件加密密鑰ekf=H3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，將(Cf,rf)發(fā)送給云服務(wù)器. 此外，初始化一個(gè)集合τupd，對(duì)于每個(gè)關(guān)鍵字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ā)送給代理服務(wù)器.

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

① for eachupdw∈τupddo

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

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

④ ifFiles[w]≠c+1 then

⑤ return “無(wú)效令牌”;

⑥ else ifc=0 then

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

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

⑨ else

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

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

① for each (u,e)∈τtddo

②T[u]=e;

③ end for

6.2.3 用戶注冊(cè)算法Register(u)

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

1)DataUser(w,SKu)：給定搜索的關(guān)鍵字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ā)送給代理服務(wù)器.

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

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

③ ifs≠sc+1 then

④ return “無(wú)效令牌”;

⑤ end if

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

⑦τw←(tw,stc);

⑧ ifstc=⊥ then

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

⑩ else

3)CloudServer(uid,Udqt,τw)：給定搜索用戶的uid以及搜索令牌τw=(tw,stc)，云服務(wù)器初始化3個(gè)集合Δ，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

⑩ 刪除當(dāng)前塊;

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

1)DataUser(id(f),W(f),SKo)：對(duì)于每個(gè)關(guān)鍵字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ā)送給代理服務(wù)器.

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

3)CloudServer(τtd,EDB)：云服務(wù)器執(zhí)行算法見(jiàn)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(wàn);

⑥ end for

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

7 安全性分析和證明

7.1 安全性分析

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

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

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

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

7.2 安全性證明

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

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

①k←AES.KeyGen(1λ);

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

③ 初始化字典KeyStore存放模擬關(guān)鍵字標(biāo)識(shí)符;

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

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

② fori=1 toμfdo

③ 隨機(jī)生成(u,e)對(duì);

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

⑥ end for

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

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

②rst←rp(w);

③ ifKeyStore[w]=null then

④ 隨機(jī)生成KeyStore[w];

⑤ end if

⑥tw=KeyStore[w];

⑦ ifST[w]=null then

⑧ 隨機(jī)生成stc;

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

⑩ else ifrst?ST[w].allrstthen

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

② 從Dict中隨機(jī)選取一個(gè)包含μf個(gè)關(guān)鍵字的文件id(f);

③ fori=1 toμfdo

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

⑤ 隨機(jī)生成新的(udel,edel)對(duì);

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

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

⑧ end for

證畢.

8 性能分析

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

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

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

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

Table 2 Performance Comparison Between MFS and IMFS

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

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

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

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

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

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

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

9 總 結(jié)

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