基于改進Merkle-Tree認證方法的可驗證多關鍵詞搜索方案

田有亮，駱琴

（1.公共大數據國家重點實驗室（貴州大學），貴州 貴陽 550025；2.貴州大學計算機科學與技術學院，貴州 貴陽 550025；3.貴州大學密碼學與數據安全研究所，貴州 貴陽 550025；4.貴州大學數學與統計學院，貴州 貴陽 550025）

1 引言

隨著大數據的開放與共享，數據搜索結果的可驗證性顯得尤其重要。搜索結果的可驗證性是指用戶能夠高效地對服務器返回的搜索結果進行認證。現有可搜索加密方案中的結果驗證方法普遍存在成本高、效率低等問題，為實現多關鍵詞搜索結果高效驗證和安全性需求帶來了巨大挑戰。

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

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

關鍵詞陷門和文件擁有者的身份信息組成，可以通過關鍵詞陷門與關鍵詞密文的匹配來產生搜索結果，最初的研究者只關注單關鍵詞搜索方案的實現。

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

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

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

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

2)在認證階段，利用改進的Merkle-Tree認證方法構造搜索方案的驗證及動態更新算法，實現高效認證和動態更新；與經典的MHT相比，計算成本從O(n)降低到O(logn)。

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

2 預備知識

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

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

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

2.1 經典的MHT

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

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

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

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

圖1 經典的MHT

2.2 改進的Merkle-Tree認證方法

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

圖2 改進的Merkle-Tree

3 問題描述

3.1 方案模型

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

圖3 方案模型

3.2 方案定義

本文方案由以下7個算法組成。

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

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

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

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

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

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

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

3.3 安全模型

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

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

Tlist：用于存儲元組(ID,W)，這就意味著與用戶ID的關鍵詞W相關的搜索令牌已被(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和挑戰者C之間進行的。

初始化。挑戰者運行GlobalSetup，輸出公共參數param和主密鑰msk，把公共參數param發送給敵手A1，并且設置列表為空。

階段1。假設A1可以在多項式時間查詢以下預言機，則C可以執行以下算法。

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

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

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

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

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

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

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

挑戰階段。A1提交2個相同長度的不同關鍵詞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選擇一個隨機位λ∈(0,1)，通過運行Encrypt算法對Wλ進行加密并將密文I*返回給A1。

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

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

定義3對于任何概率多項式時間的算法A1，能以不可忽略的優勢贏得Game1，則實現了針對A1的密文不可區分性。

4 方案構造

本節介紹方案的具體構造。首先，基于Miao等[16]提出的VMKS方案構造多關鍵詞的可搜索算法，實現高效精準的多關鍵詞搜索。其次，利用改進的Merkle-Tree認證方法構造搜索方案的驗證及動態更新算法，防止數據篡改、刪除和偽造等不法操作的高效驗證，且時間戳與根節點的連接確保了數據的新鮮度，這是文獻[16]沒有的特點，具體算法如下。

4.1 初始化

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

4.2 密鑰生成

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

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

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

4.3 密文生成

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

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

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

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

4.4 陷門生成

用戶想要搜索感興趣的文件，需要將關鍵詞加密向CSP請求查詢，CSP收到相應的查詢陷門執行搜索算法。

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

4.5 密文搜索

根據用戶提交的相應查詢陷門，CSP執行搜索算法，搜索與陷門匹配的結果。

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

4.6 結果認證

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

2)用戶對文件標簽及根簽名進行驗證，當用戶收到CSP回應的證明信息時，則需要計算以下3個式子來驗證結果的正確性。

5 動態更新

允許數據動態過程是可搜索加密方案中數據完整性查詢的一個重要特性。但是，現有的大多數方案都沒有這個特性，本文將介紹利用改進的Merkle-Tree認證方法構造搜索方案的動態更新算法。

5.1 數據修改

DO向服務器發出請求，并按以下方式對數據進行修改。

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

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

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

5.2 數據添加

若DO想在一個特殊的位置添加一個數據塊f*，則按以下操作執行。

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

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

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

6 方案分析

6.1 正確性分析

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

對于式(1)，有

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

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

圖4 數據添加

6.2 安全性分析

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

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

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

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

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

Game2。在該輪游戲中，A繼續執行Game1中定義的步驟，除了H0是一個抗碰撞的哈希函數外，有

Game3。在該輪游戲中，除了生成的公共參數外，C執行的游戲與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。

公共參數設置為

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

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

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

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

1)對于身份ID，Au(ID)=0且對ParKeyGen預言機進行查詢。

2)對于身份ID，Au(ID)=0且對KeyGen預言機進行查詢。

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

其中，Ω表示用戶ID查詢預言機ParKeyGen的集合，Ω′表示用戶ID查詢預言機KeyGen的集合，ξ1表示查詢預言機ParKeyGen的次數，ξ2表示查詢預言機KeyGen的次數。

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

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

定理1證畢。

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

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

定理3如果敵手AI以ε的優勢在數據塊f[i]上產生時間跨度為t1的偽造，通過模擬GameI，并對哈希查詢進行qH次查詢、簽名查詢進行qS次查詢和系統參數查詢進行qparam次查詢，則用以下的概率和多項式時間解決CDH問題

其中，tsm是G中的一個標量乘法的時間，e是自然對數的底數。

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

AI在GameI的各個階段進行查詢，而B在整個游戲中對AI的所有查詢做出相應答復，B由A維護。

1)系統參數查詢。首先AI請求B進行系統初始化，B回答此查詢如下。B選擇一個隨機數t∈Zp作為密鑰，生成公鑰gt∈G，并將(g,gt,G)發送給AI，t保密。

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

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

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

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

B知道的值，因此B可以計算gab或者可以在多項式時間內解決G中的CDH問題，這與CDH問題困難性的假設相矛盾。

B要成功需要3個事件。

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

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

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

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

證明如上所述，P[cl=1]=(1-δ)，因此B不會終止的概率為(1-δ)，因為它至少進行qS次簽名查詢，所以A查詢后不會終止的概率至少為(1-δ)qS。

I

推論1證畢。

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

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

因此，有

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

推論3證畢。

接下來，進一步證明B在多項式時間內解決CDH問題。

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

2)每個查詢都需要計算群G中等于tsm的求冪運算。

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

定理3證畢。

7 性能分析

7.1 計算量比較

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

表1 符號注釋

表2 計算量比較

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

7.2 功能比較

對文獻[9]方案、文獻[16]方案、文獻[25]方案以及本文方案進行功能比較，如表3所示。

表3 功能比較

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

7.3 仿真分析

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

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

圖5 執行時間

圖6 密鑰生成時間

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

8 結束語

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

圖7 修改數據塊的計算成本