基于改進(jìn)Merkle-Tree認(rèn)證方法的可驗(yàn)證多關(guān)鍵詞搜索方案

田有亮，駱琴

（1.公共大數(shù)據(jù)國家重點(diǎn)實(shí)驗(yàn)室（貴州大學(xué)），貴州 貴陽 550025；2.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；3.貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025；4.貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 貴陽 550025）

1 引言

隨著大數(shù)據(jù)的開放與共享，數(shù)據(jù)搜索結(jié)果的可驗(yàn)證性顯得尤其重要。搜索結(jié)果的可驗(yàn)證性是指用戶能夠高效地對服務(wù)器返回的搜索結(jié)果進(jìn)行認(rèn)證?，F(xiàn)有可搜索加密方案中的結(jié)果驗(yàn)證方法普遍存在成本高、效率低等問題，為實(shí)現(xiàn)多關(guān)鍵詞搜索結(jié)果高效驗(yàn)證和安全性需求帶來了巨大挑戰(zhàn)。

可搜索加密的目的是解決云存儲[1-3]條件下密文的高效搜索問題，一個(gè)安全的可搜索加密方案可以使云服務(wù)器在不知道用戶明文數(shù)據(jù)信息的情況下，實(shí)現(xiàn)對密文的搜索。最早由Song等[4]提出的方案使用對稱加密算法對文檔中的每個(gè)單詞進(jìn)行加密，搜索時(shí)對關(guān)鍵詞也同樣加密，然后通過全文掃描，將加密的搜索關(guān)鍵詞與加密的文檔進(jìn)行比對，匹配到具有相同密文單詞的文件則是用戶想要的文件。但是這種方法檢索的效率較低，耗時(shí)較多。Goh[5]基于“文件-關(guān)鍵詞”的思想，通過利用布隆過濾器來建立文件索引，對每個(gè)文件包含的關(guān)鍵詞使用偽隨機(jī)函數(shù)映射到該文件的布隆過濾器索引中，搜索時(shí)提交查詢陷門，根據(jù)每個(gè)文件的索引判斷該文件是否包含特定的查詢關(guān)鍵詞。這種建立安全索引的方法使搜索效率得到了顯著提高，但云服務(wù)器需要與用戶進(jìn)行兩次交互才能完成搜索，增加了用戶的通信開銷。Chang等[6]利用隨機(jī)比特建立

關(guān)鍵詞的索引，并在搜索時(shí)通過恢復(fù)索引的部分信息來匹配關(guān)鍵詞。Curtmola等[7]提出了在整個(gè)文件集合上建立加密關(guān)鍵詞的Hash索引，搜索令牌由

關(guān)鍵詞陷門和文件擁有者的身份信息組成，可以通過關(guān)鍵詞陷門與關(guān)鍵詞密文的匹配來產(chǎn)生搜索結(jié)果，最初的研究者只關(guān)注單關(guān)鍵詞搜索方案的實(shí)現(xiàn)。

考慮到單關(guān)鍵詞不能精準(zhǔn)定位到用戶想要的文件，Golle等[8]提出2個(gè)連接關(guān)鍵詞搜索方案。該方案假設(shè)對每次搜索的每個(gè)文件都有固定數(shù)量的關(guān)鍵詞域，第一個(gè)方案需要為每個(gè)文件進(jìn)行兩次模冪運(yùn)算，其陷門的大小與加密文件的總數(shù)成線性關(guān)系。第二個(gè)方案雖然使陷門的大小固定，但是卻與關(guān)鍵詞域的數(shù)量成正比。而且第二個(gè)方案的存儲開銷是第一個(gè)方案的兩倍。Zheng等[9]提出加密數(shù)據(jù)的無證書關(guān)鍵詞搜索（CLKS,certificateless keyword search on encrypted data）方案，該方案不僅支持對加密數(shù)據(jù)進(jìn)行多關(guān)鍵詞搜索，而且由于無證書加密技術(shù)避免了證書管理問題，但通信開銷比較大。Zhang等[10]提出了一種排序的多關(guān)鍵詞搜索方案，該方案支持在多所有者模型中進(jìn)行結(jié)果相關(guān)性排序搜索，降低了返回所有搜索結(jié)果的需要，但不能對惡意云服務(wù)器返回的虛假搜索結(jié)果進(jìn)行驗(yàn)證。

因此，應(yīng)使用某種驗(yàn)證方法來確保用戶搜索結(jié)果的正確性[11-12]。Sun等[13]提出了一種有效的基于樹的索引結(jié)構(gòu)來實(shí)現(xiàn)真實(shí)性驗(yàn)證。Wang等[14]提出了一個(gè)完全實(shí)現(xiàn)查詢完整性驗(yàn)證的方案，該方案利用布隆過濾器[15]、MHT（Merkle Hash Tree）等數(shù)據(jù)結(jié)構(gòu)，借助偽隨機(jī)置換、哈希函數(shù)等工具來驗(yàn)證查詢完整性。但該方案只適用于靜態(tài)數(shù)據(jù)庫，不支持?jǐn)?shù)據(jù)庫的動態(tài)更新。文獻(xiàn)[16]提出了一種可驗(yàn)證的多關(guān)鍵詞搜索方案，該方案借助私人審計(jì)服務(wù)器來驗(yàn)證搜索結(jié)果的正確性，但也不能實(shí)現(xiàn)動態(tài)性?？紤]到用戶需要經(jīng)常更新存儲到云端的數(shù)據(jù)，支持動態(tài)操作的可搜索加密方案[17-20]得到研究者們的廣泛研究。Kurosawa[21]演示了如何以驗(yàn)證的方式支持文檔的更新操作，以及檢測惡意云服務(wù)器的攻擊行為。

在傳統(tǒng)的有效驗(yàn)證方案中，用戶需要委托第三方來驗(yàn)證搜索結(jié)果，此方法雖然保證了搜索結(jié)果的正確性，但是增加了計(jì)算和通信開銷。針對上述問題，本文采用文獻(xiàn)[16]所提的驗(yàn)證思想，基于改進(jìn)的Merkle-Tree認(rèn)證方法[22]提出搜索結(jié)果高效驗(yàn)證的多關(guān)鍵詞搜索方案，主要貢獻(xiàn)如下。

1)在搜索階段，基于Miao等[16]提出的（VMKS,verifiable multiple keywords search）方案構(gòu)造多關(guān)鍵詞的可搜索算法，實(shí)現(xiàn)高效精準(zhǔn)的多關(guān)鍵詞搜索，并且通過方案分析，證明其可行性。

2)在認(rèn)證階段，利用改進(jìn)的Merkle-Tree認(rèn)證方法構(gòu)造搜索方案的驗(yàn)證及動態(tài)更新算法，實(shí)現(xiàn)高效認(rèn)證和動態(tài)更新；與經(jīng)典的MHT相比，計(jì)算成本從O(n)降低到O(logn)。

3)對所提方案的正確性、安全性和性能進(jìn)行了詳細(xì)證明與分析，并在決策線性假設(shè)和CDH（computational Diffie-Hellman）假設(shè)下證明所提方案滿足密文不可區(qū)分性和不可偽造性。

2 預(yù)備知識

BLS（Boneh-Lynn-Shacham）短簽名由文獻(xiàn)[23]定義，它是用于消息簽名的身份驗(yàn)證，使用雙線性對[16]進(jìn)行簽名身份認(rèn)證。與本文方案安全性相關(guān)的安全假設(shè)描述如下。

定義1CDH假設(shè)。假設(shè)G是階為p的乘法循環(huán)群，g是G的生成元，給定三元組g,ga,gb∈G，且隨機(jī)選擇2個(gè)元素，對于任何概率多項(xiàng)式時(shí)間的敵手A，以不可忽略的優(yōu)勢ε，計(jì)算gab∈G是不可行的，其中A的優(yōu)勢滿足

定義2決策線性假設(shè)。假設(shè)G是階為p的群，g是G的生成元，給定元組和，其中u,v,l∈G，概率多項(xiàng)式時(shí)間敵手A的主要目標(biāo)是區(qū)分與在群G里的隨機(jī)元素l，如果A在打破DL（decisional linear）問題上的優(yōu)勢可以忽略不計(jì)，其優(yōu)勢定義為

2.1 經(jīng)典的MHT

MHT是著名的二叉樹數(shù)據(jù)結(jié)構(gòu)，其中除葉子節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)都是其葉子節(jié)點(diǎn)的串聯(lián)，頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)。MHT中的葉子節(jié)點(diǎn)表示數(shù)據(jù)塊的哈希值，根節(jié)點(diǎn)的身份驗(yàn)證可確保所有節(jié)點(diǎn)的完整性。圖1描述了具有8個(gè)葉子節(jié)點(diǎn)的MHT，如果要對h(f[3])處的數(shù)據(jù)節(jié)點(diǎn)進(jìn)行完整性驗(yàn)證，則需要知道輔助信息（AI,auxiliary information）和AI(f[3]):{(hC,L),h(f[3]),(h(f[4]),R),(hB,R)}，為了驗(yàn)證數(shù)據(jù)塊f[3]的完整性，認(rèn)證者執(zhí)行以下操作。

1)計(jì)算hD←(h(f[3])||h(f[4]))。

2)計(jì)算hA←(hC||hD)。

3)計(jì)算根hR←(hA,hB)。

圖1 經(jīng)典的MHT

2.2 改進(jìn)的Merkle-Tree認(rèn)證方法

為了降低在運(yùn)用MHT驗(yàn)證過程中節(jié)點(diǎn)搜索的計(jì)算成本，本文結(jié)合文獻(xiàn)[22]改進(jìn)的Merkle-Tree認(rèn)證方法，將計(jì)算成本從經(jīng)典的MHT的O(n)降低到O(logn)，樹的每個(gè)節(jié)點(diǎn)都有2個(gè)信息：一個(gè)是數(shù)據(jù)塊的哈希值；另一個(gè)是相對索引。與節(jié)點(diǎn)T關(guān)聯(lián)的相對索引是指屬于T的子樹的葉子節(jié)點(diǎn)的數(shù)量，葉子節(jié)點(diǎn)的相對索引值設(shè)置為1。例如，如果L和R是左右子節(jié)點(diǎn)，其哈希值分別為ha和hb，相對索引字段分別為父節(jié)點(diǎn)T的ra和rb，則節(jié)點(diǎn)T的哈希值為(ha||hb)且相對索引字段值為(ra+rb)。時(shí)間戳字段與樹的根節(jié)點(diǎn)串聯(lián)，該時(shí)間戳是與根哈希值串聯(lián)的樹創(chuàng)建的日期和時(shí)間。改進(jìn)的Merkle-Tree如圖2所示，有hR:(hA||hB||dt)，其中dt是Merkle-Tree創(chuàng)建的日期和時(shí)間。由于hR總是針對樹中任何數(shù)據(jù)塊做任何修改而更新，因此最后修改的日期和時(shí)間會反映在hR，從而確保了數(shù)據(jù)的新鮮度。

圖2 改進(jìn)的Merkle-Tree

3 問題描述

3.1 方案模型

如圖3所示，模型中有4個(gè)實(shí)體，即密鑰生成中心（KGC,key generation center）、數(shù)據(jù)擁有者（DO,data owner）、用戶（DU,data user）以及云服務(wù)器（CSP,cloud service provider）。首先，KGC根據(jù)用戶相應(yīng)標(biāo)識生成部分私鑰，其余部分私鑰由用戶自己生成。其次，DO先對文件加密并為文件創(chuàng)建索引，將文件F分割成n個(gè)數(shù)據(jù)塊(f[1],f[2],…,f[n])，數(shù)據(jù)塊f[i]作為Merkle-Tree的葉子節(jié)點(diǎn)生成完整的樹并對根進(jìn)行簽名，然后將這些發(fā)送給CSP存儲。DU按照自己的需求向服務(wù)器提交相應(yīng)的查詢陷門，CSP根據(jù)每個(gè)文件的索引判斷該文件是否包含特定的查詢關(guān)鍵詞搜索匹配的結(jié)果。當(dāng)用戶收到服務(wù)器返回的結(jié)果時(shí)，向服務(wù)器提出質(zhì)詢消息驗(yàn)證結(jié)果的完整性。

圖3 方案模型

3.2 方案定義

本文方案由以下7個(gè)算法組成。

1)GlobalSetup(λ)。輸入安全參數(shù)λ，發(fā)布公共參數(shù)，保存主密鑰，輸出系統(tǒng)公共參數(shù)param和主密鑰msk。

2)ParKeyGen(msk,ID)。給定用戶ID，KGC運(yùn)行該算法并為用戶ID返回相應(yīng)的部分私鑰pskID=(psk1,psk2)。

3)KeyGen(param,pskID,ID,msk)。輸入msk、ID、param、pskID，最后為用戶輸出公私鑰(pk,sk)。

4）Encrypt(F,W,pk,pskID,ID)。給出數(shù)據(jù)文件集F和關(guān)鍵詞集W，DO執(zhí)行該算法，輸出密文集CT、索引集I、文件標(biāo)簽τ和簽名集δ，DO將這些元組(CT,I,τ,δ)上傳至CSP中存儲。

5)Trapdoor(sk,pkID,W',pk,ID)。輸入搜索查詢W'，用戶DO執(zhí)行該算法，生成搜索令牌TW'并發(fā)送給CSP。

6)Search(pk,TW',I,CT)。CSP收到用戶的搜索請求后，搜索與關(guān)鍵詞陷門TW'匹配的索引I的相關(guān)文件CT'及其相應(yīng)的身份標(biāo)識ID'，然后將(CT',ID')發(fā)送給用戶。

7)Verify(CT',pk,ρ)。用戶收到搜索結(jié)果CT'，向服務(wù)器提交質(zhì)詢消息，服務(wù)器返回相應(yīng)的輔助消息，驗(yàn)證結(jié)果的完整性，如果CT'通過認(rèn)證算法，用戶輸出1；否則，輸出0。

3.3 安全模型

與方案[16,24]相似，本文首先假設(shè)CSP是半誠實(shí)且好奇的，這意味著它將誠實(shí)地執(zhí)行算法，但會嘗試學(xué)習(xí)盡可能多的私有信息。其次，假設(shè)不能完全信任KGC，那么KGC誠實(shí)地遵循算法規(guī)定，但可能會嘗試使用其獲得的信息來滲透更多的信息。本文考慮2種類型的敵手，即A1和A2。A1表示外部攻擊者，除了主密鑰msk以外允許控制用戶ID的公鑰；A2表示內(nèi)部攻擊者，可以訪問主密鑰KGC，而不需要控制用戶ID的公鑰。

本文通過下面的2個(gè)安全游戲來說明本文方案對以上2種不利因素都是安全的。設(shè)A1為Game1中的敵手，A2為Game2中的敵手，C是維護(hù)下面2個(gè)列表的挑戰(zhàn)者。

Tlist：用于存儲元組(ID,W)，這就意味著與用戶ID的關(guān)鍵詞W相關(guān)的搜索令牌已被(A1,A2)查詢。

Ulist：用于存儲元組(ID,psk,sk,pk,?1,?2,?3)，?1=1表示psk被(A1,A2)查詢；否則，表示未被查詢。同樣地，?2=1和?3=1表示sk,pk被(A1,A2)查詢；否則，表示敵手不會查詢sk,pk。具體來說，本文的安全游戲是在敵手A1和挑戰(zhàn)者C之間進(jìn)行的。

初始化。挑戰(zhàn)者運(yùn)行GlobalSetup，輸出公共參數(shù)param和主密鑰msk，把公共參數(shù)param發(fā)送給敵手A1，并且設(shè)置列表為空。

階段1。假設(shè)A1可以在多項(xiàng)式時(shí)間查詢以下預(yù)言機(jī)，則C可以執(zhí)行以下算法。

ParKeyGen。給定來自A1的用戶標(biāo)識ID，在Ulist中的psk不為空，C返回psk；否則，挑戰(zhàn)者利用主密鑰msk執(zhí)行ParKeyGen算法以獲得psk，將元組(ID,psk,*,*,1,0,0)添加到列表Ulist中，并將psk發(fā)送給A1，其中符號“*”表示為空。

KeyGen。給定A1的ID，如果sk不為空，則挑戰(zhàn)者從Ulist中選擇sk；如果psk在Ulist中不為空，則挑戰(zhàn)者調(diào)用ParKeyGen算法利用psk生成sk，然后挑戰(zhàn)者在Ulist中添加sk。假設(shè)上面2種情況都不成立，則C執(zhí)行ParKeyGen和KeyGen算法獲得psk和sk。然后，C在Ulist中添加元組(ID,psk,sk)。最后，C更新與用戶ID關(guān)聯(lián)的Ulist中的?1=1，?2=1并將sk發(fā)送給A1。

Ulist中的pk不為空，那么挑戰(zhàn)者檢索pk；如果Ulist中的sk不為空，則檢索sk且挑戰(zhàn)者運(yùn)行KeyGen以輸出pk并將其添加到與ID有關(guān)的Ulist中。

如果Ulist中的psk不為空，則C將檢索psk，運(yùn)行KeyGen生成sk和pk，并將sk、pk添加到Ulist中。

否則，C將同時(shí)運(yùn)行ParKeyGen和KeyGen算法以生成psk、sk和pk，并將元組(ID,psk,sk,pk,0,0,0)添加到Ulist中，C將pk發(fā)送給A1。

Rplace-pk。給定用戶ID和來自A1的替換公鑰pk，C將Ulist中的pk更新為pk'，并針對ID設(shè)置?3=1。

Trapdoor。給定用戶ID和A1的關(guān)鍵詞W，挑戰(zhàn)者在Ulist中檢索sk，執(zhí)行Trapdoor算法，將元組(ID,W)添加到Tlist中，然后將陷門發(fā)送給A1。

挑戰(zhàn)階段。A1提交2個(gè)相同長度的不同關(guān)鍵詞W0,W1以及用戶ID。給定Ulist中的(ID*,psk*,sk*,?1,?2,?3)，如果?1=0，?2=0，仍然要求psk*和sk*不能被A1查詢。此外，(ID*,W0)和(ID*,W1)都沒有存儲在Tlist中。如果?3=0則可以替換pk*，否則無法替換。C選擇一個(gè)隨機(jī)位λ∈(0,1)，通過運(yùn)行Encrypt算法對Wλ進(jìn)行加密并將密文I*返回給A1。

階段2。該階段與階段1相似，唯一的限制是不能進(jìn)行以下查詢：A1不能查詢ParKeyGen(ID*)、KeyGen(ID*)、Trapdoor(ID*,W0)或者Trapdoor(ID*,W1)。

猜測。A1輸出為λ*，A1贏得游戲的條件是λ*=λ。

定義3對于任何概率多項(xiàng)式時(shí)間的算法A1，能以不可忽略的優(yōu)勢贏得Game1，則實(shí)現(xiàn)了針對A1的密文不可區(qū)分性。

4 方案構(gòu)造

本節(jié)介紹方案的具體構(gòu)造。首先，基于Miao等[16]提出的VMKS方案構(gòu)造多關(guān)鍵詞的可搜索算法，實(shí)現(xiàn)高效精準(zhǔn)的多關(guān)鍵詞搜索。其次，利用改進(jìn)的Merkle-Tree認(rèn)證方法構(gòu)造搜索方案的驗(yàn)證及動態(tài)更新算法，防止數(shù)據(jù)篡改、刪除和偽造等不法操作的高效驗(yàn)證，且時(shí)間戳與根節(jié)點(diǎn)的連接確保了數(shù)據(jù)的新鮮度，這是文獻(xiàn)[16]沒有的特點(diǎn)，具體算法如下。

4.1 初始化

GlobalSetup(λ)。輸入安全參數(shù)λ，假設(shè)e:G×G→GT是雙線性映射，G是生成元為g、階數(shù)為p的一個(gè)群，KGC選擇隨機(jī)元素u,u1,…,un∈G，并且計(jì)算gx,gy，最后，選擇2個(gè)哈希函數(shù)并且定義一個(gè)哈希函數(shù)，其中ID={ID1,ID2,…,IDn}，此外，KGC生成公私鑰對(pk,sk)。系統(tǒng)公共參數(shù)param={g,h,H0,H1,g0,u,u1,…,un,gx,gy}，主密鑰msk={x,y}，將系統(tǒng)參數(shù)param發(fā)布出來，msk由KGC自己保存。

4.2 密鑰生成

密鑰生成分為2個(gè)步驟。首先，KGC在ParKeyGen算法中為用戶ID生成部分私鑰；其次，用戶ID在KeyGen算法中為自己生成最終的私鑰。

1)ParKeyGen(msk,ID)。給出特定用戶DU的身份ID，KGC選取隨機(jī)元素，計(jì)算并將其通過安全通道發(fā)送給用戶DU，則它的部分私鑰為pskID=(psk1,psk2)。

2)KeyGen(param,pskID,ID,msk)。DU隨機(jī)選取2個(gè)元素并且計(jì)算DU的公私鑰對為

4.3 密文生成

DO將存儲在服務(wù)器中的數(shù)據(jù)文件F分割成n個(gè)數(shù)據(jù)塊(f[1],f[2],…,f[n])，并在上傳之前對其加密，具體算法如下。

1)FileTagGen(fname,t,n,dt)。由DO執(zhí)行該算法，為文件F生成標(biāo)簽，選擇隨機(jī)元素μ∈G，生成系統(tǒng)日期和時(shí)間，記為dt，系統(tǒng)日期和時(shí)間連接在文件標(biāo)簽τ后，確保文件的新鮮度，使π=(fname||n||μ||dt)，其中π∈G且τ=sigt(π)是文件F的標(biāo)簽，連接的字符串π被存儲在本地是為了以后對文件標(biāo)簽的驗(yàn)證。

2)BlockSigGen(t,h(f[i]),dt,μ)。生成文件標(biāo)簽之后，DO每個(gè)文件塊f[i]生成的BLS簽名為?i=(h(f[i])μf[i])t，i∈{1,2,…,n}，簽名集為δ={?i},1≤i≤n，DO用h(f[i])作為葉子節(jié)點(diǎn)生成樹，其中，根節(jié)點(diǎn)hR是與系統(tǒng)日期和時(shí)間連接的，即hR=hR||dt，根的簽名為ρ←(hR)t。

3)Encrypt(F,W,pk,pskID,ID)。DO從文件f[i]中提取關(guān)鍵詞集Wi?W={w1,…,wn}并為這些文件創(chuàng)建索引Ii。DO選擇2個(gè)隨機(jī)數(shù)并且計(jì)算，最后，DO將{I,C,τ,δ,ρ}和相應(yīng)的身份標(biāo)識ID={ID1,…,IDd}上傳給CSP。

4.4 陷門生成

用戶想要搜索感興趣的文件，需要將關(guān)鍵詞加密向CSP請求查詢，CSP收到相應(yīng)的查詢陷門執(zhí)行搜索算法。

Trapdoor(sk,pkID,W',pk,ID)。給定查詢的關(guān)鍵詞集，用戶DU選擇元素s∈Zp，然后計(jì)算陷門TW'={T1,T2,T3,T4}，其中，

4.5 密文搜索

根據(jù)用戶提交的相應(yīng)查詢陷門，CSP執(zhí)行搜索算法，搜索與陷門匹配的結(jié)果。

Search(pk,TW',I,C)。收到陷門TW'之后，CSP計(jì)算三元組(σ1,σ2,σ3)，其中σ1=e(I2,T3)，CSP通過判斷式(1)是否成立，來匹配陷門TW'和索引I，最后，返回相關(guān)的密文

4.6 結(jié)果認(rèn)證

Verify(C′,pk,ρ)。用戶收到結(jié)果C'時(shí)，向CSP提出質(zhì)詢消息返回相應(yīng)輔助消息來驗(yàn)證C'的正確性，用戶首先選擇k個(gè)元素集Q={?1,…,?k},k∈[1,n]且?i∈Q，其次選擇一個(gè)隨機(jī)元素bi∈Zp，最后，發(fā)送質(zhì)詢消息M←(i,bi)i∈Q給CSP。

2)用戶對文件標(biāo)簽及根簽名進(jìn)行驗(yàn)證，當(dāng)用戶收到CSP回應(yīng)的證明信息時(shí)，則需要計(jì)算以下3個(gè)式子來驗(yàn)證結(jié)果的正確性。

5 動態(tài)更新

允許數(shù)據(jù)動態(tài)過程是可搜索加密方案中數(shù)據(jù)完整性查詢的一個(gè)重要特性。但是，現(xiàn)有的大多數(shù)方案都沒有這個(gè)特性，本文將介紹利用改進(jìn)的Merkle-Tree認(rèn)證方法構(gòu)造搜索方案的動態(tài)更新算法。

5.1 數(shù)據(jù)修改

DO向服務(wù)器發(fā)出請求，并按以下方式對數(shù)據(jù)進(jìn)行修改。

首先，DO為新的文件生成標(biāo)簽?'=(h(f[i]')μf[i]')t。

接下來，DO生成新的文件標(biāo)簽τ'←sigk(fname||n||μ||dt)，來驗(yàn)證修改的日期和時(shí)間，以確保數(shù)據(jù)的新鮮度。

數(shù)據(jù)修改的框架為(X,i,f[i]',h(f[i]'),?',τ')，將這些信息傳送給CSP，其中X表示修改操作，i表示要修改的數(shù)據(jù)塊。收到以上消息后，CSP將執(zhí)行以下替換：首先，用替換fi；其次，分別用φ'和τ′替換φ和τ；最后，用h(f[i]')替換h(f[i])。最終，CSP生成新的根哈希值R'并用h(f[i]')進(jìn)行Merkle-Tree重建，CSP將修改過程的證明提供給數(shù)據(jù)擁有者進(jìn)行驗(yàn)證，即Pf={?,(h(f[i]),AI(i)),ρ,SIB(i),R'}，數(shù)據(jù)擁有者從CSP收到數(shù)據(jù)修改證明后，首先驗(yàn)證τ，其次通過式(3)使用{h(f[i]'),AI(i))i,ρ}驗(yàn)證根。如果認(rèn)證成功，數(shù)據(jù)擁有者使用{h(f[i]'),AI(i))i}計(jì)算新生成的根并且將其與R'進(jìn)行比較，若比較成功，數(shù)據(jù)擁有者通過簽名私鑰t認(rèn)證R'，因此生成根的簽名ρ'=h(R')t，并把它發(fā)送到CSP存儲。最后，DO為新的數(shù)據(jù)塊運(yùn)行驗(yàn)證算法，如果結(jié)果為真，DO可以從本地刪除{f[i]',τ',ρ'}。

5.2 數(shù)據(jù)添加

若DO想在一個(gè)特殊的位置添加一個(gè)數(shù)據(jù)塊f*，則按以下操作執(zhí)行。

首先，為新的數(shù)據(jù)塊生成簽名?*=(h(f*)μf*))t。

其次，生成新的文件標(biāo)簽τ*←sigt(fname||n||μ||dt)。若DO插入（如圖4所示）的數(shù)據(jù)消息為(I,V,i,f*,?',τ')，其中，I表示數(shù)據(jù)插入，字段V表示要插入的新塊的位置，V←A表示第i個(gè)位置之后的插入，V←B表示第i個(gè)位置之前的插入，并且把這些消息發(fā)送到CSP，收到消息后，CSP保存f*和對應(yīng)的葉子節(jié)點(diǎn)h(f*)，CSP在Merkle-Tree中找到h(f[i])并保留AI(i)插入葉子節(jié)點(diǎn)h(f*)，如果將字段V設(shè)置為A，則具有哈希值(h(f[i])||h(f*))的內(nèi)部節(jié)點(diǎn)將被連接到原始樹中；如果將字段V設(shè)置為B，將具有哈希值(h(f*)||h(f[i]))的內(nèi)部節(jié)點(diǎn)添加到索引設(shè)置為2的原始樹中。

最后，CSP修改從第i個(gè)節(jié)點(diǎn)到最高節(jié)點(diǎn)（根節(jié)點(diǎn)）的路徑上每個(gè)節(jié)點(diǎn)的詳細(xì)信息。由于重新生成了Merkle-Tree，CSP產(chǎn)生了一個(gè)新的根R并且為DO提供了插入操作的證明消息，表示為Pf={?,(h(f[i]),AI(i)),SIB(i),ρ,R'}，其中AI(i)表示先前樹中f[i]的輔助信息。在收到插入過程的證明時(shí)，DO首先驗(yàn)證τ，驗(yàn)證成功后，使用{h(f[i]),AI(i)}產(chǎn)生根，然后通過式(3)驗(yàn)證這個(gè)新生成的根，如果式(3)成立，那么DO可以驗(yàn)證CSP是否正確地完成了文件插入過程，從而使用{h(f[i]),AI(i)，,h(f*)}生成新的根并與R'進(jìn)行比較，若結(jié)果成功，DO將R'的認(rèn)證(h(R'))t發(fā)送給CSP更新。最后，DO為新的數(shù)據(jù)塊運(yùn)行認(rèn)證算法，如果結(jié)果為真，數(shù)據(jù)擁有者就可以從本地存儲中移除{ρ',f*,τ'}。

6 方案分析

6.1 正確性分析

為了實(shí)現(xiàn)方案的安全性，本文必須保證CSP能夠誠實(shí)地執(zhí)行密文檢索操作，通過驗(yàn)證式(1)和式(4)的成立，確定沒有篡改結(jié)果。

對于式(1)，有

如果W'?W，有σ1=σ2σ3，因此式(1)成立，對搜索結(jié)果的完整性驗(yàn)證則需要驗(yàn)證式(4)的正確性。

則有式(4)成立，因此本文方案是正確的。

圖4 數(shù)據(jù)添加

6.2 安全性分析

在決策線性假設(shè)和CDH假設(shè)下，實(shí)現(xiàn)了密文不可區(qū)分性和簽名的不可偽造性，半誠實(shí)且好奇的CSP無法偽造有效的證明信息。通過利用與文獻(xiàn)[22]方案相同的安全游戲?qū)崿F(xiàn)安全目標(biāo)。本文通過以下定理來保證本文方案的安全性。

定理1假設(shè)第1型敵手最多ξ1次查詢預(yù)言機(jī)ParKeyGen，ξ2次查詢預(yù)言機(jī)KeyGen，表示敵手A打破哈希函數(shù)H0的優(yōu)勢，AdvDL(λ)表示敵手A打破DL假設(shè)的優(yōu)勢，則第1型敵手打破密文不可區(qū)分性的優(yōu)勢為

證明設(shè)Si表示敵手A想要贏得游戲i的事件，Advi表示敵手A的優(yōu)勢。假設(shè)除了預(yù)定義的事件EP發(fā)生，i+1輪游戲終止并輸出一個(gè)隨機(jī)位外，i+1輪游戲與i輪游戲執(zhí)行相同的操作。如果EP是不可忽略的且它獨(dú)立于Si，則有

接下來，本文將展示一系列安全游戲模擬。

Game1。在該輪游戲中，敵手A按照Game1中定義的步驟執(zhí)行，即挑戰(zhàn)者C生成主密鑰、公共參數(shù)和用戶部分私鑰。令是挑戰(zhàn)階段用戶的身份和公鑰，是返回給敵手A的密文。

Game2。在該輪游戲中，A繼續(xù)執(zhí)行Game1中定義的步驟，除了H0是一個(gè)抗碰撞的哈希函數(shù)外，有

Game3。在該輪游戲中，除了生成的公共參數(shù)外，C執(zhí)行的游戲與Game2相同。

1)C選擇和ηu∈{0,…,p}，使ηu(n+1)＜p。

2)C選擇其中Kuj∈Zηu,1≤j≤n。

3)C選擇其中Tuj∈Zηu,1≤j≤n。

公共參數(shù)設(shè)置為

可以看到，生成過程中并沒有改變公共參數(shù)，因此，有Pr[S3]=Pr[S2]且Adv3=Adv2。

Game4。在該輪游戲中，除了猜測階段，C執(zhí)行的游戲與Game3相同，其中C為輸入ID=ID1,…,IDn。定義2個(gè)函數(shù)分別為

在猜測階段，C檢查Au(ID*)是否等于零，如果為零，則C終止并且輸出b'∈{0,1}作為A的猜測；否則，C執(zhí)行與Game3相同的步驟。

Game5。在該輪游戲中，除了猜測階段，C執(zhí)行的游戲與Game4相同，C檢查以下2種情況是否發(fā)生。

1)對于身份ID，Au(ID)=0且對ParKeyGen預(yù)言機(jī)進(jìn)行查詢。

2)對于身份ID，Au(ID)=0且對KeyGen預(yù)言機(jī)進(jìn)行查詢。

如果以上2種情況發(fā)生了，則C終止并且輸出b'∈{0,1}作為A的猜測，由于上述情況的發(fā)生不獨(dú)立于Game4，則本文將估計(jì)Pr[?E5]的下確界，即

其中，Ω表示用戶ID查詢預(yù)言機(jī)ParKeyGen的集合，Ω′表示用戶ID查詢預(yù)言機(jī)KeyGen的集合，ξ1表示查詢預(yù)言機(jī)ParKeyGen的次數(shù)，ξ2表示查詢預(yù)言機(jī)KeyGen的次數(shù)。

如果ηu=2(ξ1+ξ2)，則因此，

Game6。在該輪游戲中，除了使用gx,gy作為公鑰外，其中x,y是C不知道的，C執(zhí)行的游戲與Game5相同；除了預(yù)言機(jī)ParKeyGen，C根據(jù)算法規(guī)范處理預(yù)言機(jī)。

定理1證畢。

定理2假設(shè)第2型敵手最多ξ2次查詢預(yù)言機(jī)KeyGen，ξ3次查詢預(yù)言機(jī)Trapdoor，表示敵手A打破哈希函數(shù)H0的優(yōu)勢，AdvDL(λ)表示敵手A打破DL假設(shè)的優(yōu)勢，則第2型敵手打破密文不可區(qū)分性的優(yōu)勢為

定理2的證明過程與定理1相似，在此省略。

定理3如果敵手AI以ε的優(yōu)勢在數(shù)據(jù)塊f[i]上產(chǎn)生時(shí)間跨度為t1的偽造，通過模擬GameI，并對哈希查詢進(jìn)行qH次查詢、簽名查詢進(jìn)行qS次查詢和系統(tǒng)參數(shù)查詢進(jìn)行qparam次查詢，則用以下的概率和多項(xiàng)式時(shí)間解決CDH問題

其中，tsm是G中的一個(gè)標(biāo)量乘法的時(shí)間，e是自然對數(shù)的底數(shù)。

證明A為攻擊者，A通過使用算法B模擬GameI與AI交互以解決CDH問題，這里哈希函數(shù)H被視為隨機(jī)預(yù)言機(jī)，列表LH由B維護(hù)，該列表最初為空。

AI在GameI的各個(gè)階段進(jìn)行查詢，而B在整個(gè)游戲中對AI的所有查詢做出相應(yīng)答復(fù)，B由A維護(hù)。

1)系統(tǒng)參數(shù)查詢。首先AI請求B進(jìn)行系統(tǒng)初始化，B回答此查詢?nèi)缦?。B選擇一個(gè)隨機(jī)數(shù)t∈Zp作為密鑰，生成公鑰gt∈G，并將(g,gt,G)發(fā)送給AI，t保密。

2)哈希查詢。AI可以在任何時(shí)間進(jìn)行哈希查詢，為了跟蹤AI所查詢過的每個(gè)數(shù)據(jù)塊f[i]，B生成一個(gè)列表LH:{f[i],wi,ki,cl}，該列表最初是空的。要回答此查詢B需執(zhí)行以下操作。B檢查列表LH對數(shù)據(jù)塊f[i]之前是否查詢過，如果找到，則B響應(yīng)H(f[i])=wi作為答復(fù)；否則，B隨機(jī)選擇cl∈{0,1}使cl=0的概率為=δ。B選擇一個(gè)隨機(jī)數(shù)，并計(jì)算然后將元組添加到列表LH中，并響應(yīng)作為AI回答。

3)簽名查詢。AI為數(shù)據(jù)塊f[i]制作簽名查詢，B對此查詢進(jìn)行以下回答。B首先發(fā)出哈希查詢以獲得列表LH，然后檢查cl，如果cl=0，則B報(bào)告失敗并停止；否則，如果，并設(shè)置B對AI的偽造響應(yīng)為σi，最終AI生成，假設(shè)AI為數(shù)據(jù)塊f[k]生成一個(gè)偽造的簽名，且沒有為f[k]發(fā)出簽名查詢，現(xiàn)在B執(zhí)行以下步驟生成一個(gè)偽造簽名。

①B為f[k]發(fā)出哈希查詢來獲取列表LH，B檢查cl的值，如果cl=1，B停止操作。

② 如果cl=0且h(f[k])=wi=gb?(g)k，則有

B知道的值，因此B可以計(jì)算gab或者可以在多項(xiàng)式時(shí)間內(nèi)解決G中的CDH問題，這與CDH問題困難性的假設(shè)相矛盾。

B要成功需要3個(gè)事件。

E1：AI的任何簽名查詢都不會終止。

E2：AI為數(shù)據(jù)塊f[k]生成真實(shí)且不重復(fù)的簽名σk。

E3：AI會產(chǎn)生有效且不重要的偽造簽名，B不終止是可能的。

推論1AI的任何簽名查詢都不會終止AI的概率至少為

證明如上所述，P[cl=1]=(1-δ)，因此B不會終止的概率為(1-δ)，因?yàn)樗辽龠M(jìn)行qS次簽名查詢，所以A查詢后不會終止的概率至少為(1-δ)qS。

I

推論1證畢。

推論2AI簽名查詢后并為f[k]生成一個(gè)有效的簽名且沒有終止的概率為P(E2|E1)≥ε。

推論3在事件E1和E2發(fā)生并且B沒有終止的情況下，AI產(chǎn)生有效且不重復(fù)偽造的概率為P(E3|(E1∩E2))≥δ。

因此，有

為了找到ε'的最小值，對式(5)求偏微分

推論3證畢。

接下來，進(jìn)一步證明B在多項(xiàng)式時(shí)間內(nèi)解決CDH問題。

1)算法B的運(yùn)行時(shí)間等于敵手AI的運(yùn)行時(shí)間與對哈希查詢(qH+qS)的響應(yīng)時(shí)間以及簽名查詢(qS)的回應(yīng)時(shí)間之和。

2)每個(gè)查詢都需要計(jì)算群G中等于tsm的求冪運(yùn)算。

根據(jù)1)和2)，算法B解決CDH問題的總時(shí)間為t1+tsm(qH+2qS)≤tc。

定理3證畢。

7 性能分析

7.1 計(jì)算量比較

在此，對文獻(xiàn)[9,16,25]方案以及本文方案進(jìn)行計(jì)算量比較。符號注釋如表1所示。假設(shè)CSP能夠誠實(shí)地執(zhí)行操作，返回的結(jié)果為非空集合，本文對各個(gè)方案算法的計(jì)算量進(jìn)行比較，如表2所示。

表1 符號注釋

表2 計(jì)算量比較

通過表2可知，本文方案在搜索算法中的效率比文獻(xiàn)[9]方案、文獻(xiàn)[16]方案和文獻(xiàn)[25]方案高。

7.2 功能比較

對文獻(xiàn)[9]方案、文獻(xiàn)[16]方案、文獻(xiàn)[25]方案以及本文方案進(jìn)行功能比較，如表3所示。

表3 功能比較

由表3可知，文獻(xiàn)[9]方案和文獻(xiàn)[16]方案不支持動態(tài)更新，雖然文獻(xiàn)[25]方案和本文方案能夠?qū)崿F(xiàn)同樣的功能，但是文獻(xiàn)[25]方案是利用代理重加密技術(shù)更新數(shù)據(jù)擁有者以及部分密文實(shí)現(xiàn)方案的動態(tài)更新，大大增加了開銷。而本文方案通過對Merkle-Tree的操作實(shí)現(xiàn)數(shù)據(jù)的動態(tài)更新（數(shù)據(jù)的添加和刪除操作）。

7.3 仿真分析

在兩臺機(jī)器上進(jìn)行了實(shí)驗(yàn)，其中一臺CPU為Intel Core i5 3230M，內(nèi)存為4 GB，操作系統(tǒng)為Windows10；另一臺CPU為Intel Core i5 10210U，內(nèi)存為8 GB。選用C++作為編程語言，分別來模擬運(yùn)行Encrypt算法和Search算法。如圖5所示，本文使用從0到1 000的不同數(shù)量的關(guān)鍵詞運(yùn)行了6個(gè)實(shí)驗(yàn)，比較了加密所有關(guān)鍵詞和查找具有給定搜索令牌的匹配關(guān)鍵詞密文的執(zhí)行時(shí)間。結(jié)果顯示，加密整個(gè)關(guān)鍵詞與查找匹配的關(guān)鍵詞密文相比，加密整個(gè)關(guān)鍵詞的成本更高。但加密整個(gè)關(guān)鍵詞只執(zhí)行一次，而找到匹配的密文則需要對每個(gè)搜索請求執(zhí)行一次。

由圖6可知，在KeyGen算法中，文獻(xiàn)[25]方案的計(jì)算成本幾乎隨著DO的數(shù)量線性增加，由于文獻(xiàn)[25]方案利用代理重加密技術(shù)實(shí)現(xiàn)對數(shù)據(jù)擁有者和部分密文的更新，則對于不同的DO需要生成不同的密鑰，因此增加了計(jì)算開銷。而本文方案通過對Merkle-Tree的操作實(shí)現(xiàn)數(shù)據(jù)的動態(tài)更新，不需要對數(shù)據(jù)擁有者進(jìn)行變更，所以本文方案在密鑰生成算法中計(jì)算開銷相對平穩(wěn)，優(yōu)于文獻(xiàn)[25]方案。

圖5 執(zhí)行時(shí)間

圖6 密鑰生成時(shí)間

為了實(shí)現(xiàn)一個(gè)高效的動態(tài)方案，本文利用改進(jìn)的Merkle-Tree對文獻(xiàn)[16]方案進(jìn)行拓展實(shí)現(xiàn)動態(tài)更新。圖7為更新數(shù)據(jù)塊的數(shù)目在50到500變化的情況下進(jìn)行文件更新的模擬實(shí)驗(yàn)。本文模擬了10個(gè)實(shí)驗(yàn)。從圖7中可以看出，隨著修改數(shù)據(jù)塊數(shù)目的增加，計(jì)算成本逐漸增加，最后趨于平穩(wěn)。故本文方案在計(jì)算成本上有一定的優(yōu)勢。

8 結(jié)束語

本文提出了搜索結(jié)果高效驗(yàn)證的多關(guān)鍵詞搜索方案，實(shí)現(xiàn)了文獻(xiàn)[16]方案不能實(shí)現(xiàn)的動態(tài)更新功能。首先，利用改進(jìn)的Merkle-Tree認(rèn)證方法構(gòu)造搜索方案的驗(yàn)證及更新算法，不但防止了數(shù)據(jù)篡改、刪除和偽造等不法操作的高效驗(yàn)證，而且時(shí)間戳字段與根節(jié)點(diǎn)的連接保證了數(shù)據(jù)的新鮮度；其次，對方案的正確性和安全性進(jìn)行了詳細(xì)的分析與證明，證明了本文方案滿足密文不可區(qū)分性和不可偽造性；最后，性能分析表明，本文方案滿足高效驗(yàn)證需求下具有低計(jì)算成本和更多安全功能的優(yōu)勢。

圖7 修改數(shù)據(jù)塊的計(jì)算成本