支持雙向驗證的動態密文檢索方案

杜瑞忠 王 一 李明月

1(河北大學網絡空間安全與計算機學院 河北保定 071002) 2(河北省高可信信息系統重點實驗室(河北大學) 河北保定 071002) 3(南開大學計算機學院 天津 300350)

云存儲的按需索取和高效便捷等特點，使其在全世界范圍內得到普及.為了保護數據的隱私性，在數據上傳到云服務器之前，需要對其進行加密.然而，加密操作大大限制了外包數據的可用性.如何在保證數據隱私的前提下對加密數據進行搜索，成為亟待解決的問題.

可搜索加密技術支持用戶在密文中進行關鍵字檢索，且不會泄露關于原文的任何信息.早期的方案需要掃描整個加密數據集合才能返回結果，時長隨著文件增加而呈現線性增長.為了提高搜索效率，許多學者對可搜索加密技術進行了改進，通過提取關鍵詞構建索引，使得方案復雜度只與文件集中所包含的關鍵詞相關.

早期的可搜索加密方案由于沒有考慮實際的應用情況，都是基于靜態環境下設計的.但是在現實情況中，存儲在云服務器的數據并不是一成不變的，可能會對云服務器中存儲的數據具有動態更新的要求.為了滿足這些需求，動態可搜索加密技術應運而生.然而由于攻擊者可以在更新期間觀察數據庫的變化，從而發現查詢關鍵字與文件之間的關系，使得動態搜索加密技術的安全分析更加復雜.隨著學者對其安全性的研究，前向安全與后向安全的概念被提出.前向安全保證了新添加的文檔不會泄露之前搜索過的關鍵字信息；后向安全保證了刪除的文檔不會因為后續的搜索泄露信息.

除了保證方案的安全性以外，還需要對服務器的結果的正確性進行驗證.目前，已經有很多可驗證搜索加密方案被提出，這些方案均假定用戶為誠實可信的實體，將驗證操作交由用戶去執行.但是惡意用戶出于自私的目的，否認云服務器返回的正確結果，進而拒絕向其支付服務費.考慮到上述問題，本文提出了一種雙向驗證的動態密文檢索方案，旨在解決動態環境下對用戶與云服務器雙向驗證的問題.本文的主要貢獻包括3個方面：

1) 利用位圖技術構建索引，將文件標識符映射為位圖中的項，并引入同態加密技術對索引進行加密，在滿足前向安全與后向安全的同時，提高了搜索以及更新效率.

2) 將搜索與驗證過程進行分離，由云服務器進行鏈下搜索，將驗證過程交由區塊鏈去處理.利用聚合消息認證碼對關鍵字對應的加密結果進行驗證，在保證用戶與云服務器誠實操作外，使得區塊鏈的存儲安全且輕量.

3) 通過將本方案部署到本地私有測試網絡Ganache中，并且對數據進行分梯度實驗.實驗結果分析表明，本方案在索引生成、搜索、驗證以及更新效率方面均優于其他方案.

1 相關工作

Song等人[1]提出對稱可搜索加密技術，但由于其搜索過程需要掃描整個數據集合才可以返回結果，其時長也隨文件增加而呈現出線性增長的情況.Goh[2]通過布隆過濾器構建索引，在進行搜索時可以直接對索引進行匹配.雖然提升了搜索效率，但是由于布隆過濾器本身的特性，導致返回結果存在誤差.Curtmola等人[3]提出一種倒排索引的搜索加密方案，這種方法提升了搜索效率，使得方案復雜度只與文件集中所包含的關鍵詞相關.

隨著動態可搜索加密技術[4]的提出，學者將注意力轉移到了這個更加靈活的方案中.但是由于數據的更新可能帶來更多信息泄露，為了防止這種情況發生，Stefanov等人[5]提出了關于前向安全和后向安全的概念.2016年，Bost[6]對前向安全進行了正式定義，并設計了第1個滿足前向安全的方案.2017年，Bost等人[7]提出了同時滿足前向安全和后向安全的可搜索加密方案，并在文中對后向安全等級從低到高分為Type-Ⅲ，Type-Ⅱ，Type-Ⅰ這3種類型.2018年，Sun等人[8]構造一種新型加密方式——對稱刺穿加密，該方式使得服務器喪失對刪除文檔包含關鍵字的搜索能力，達到了后向安全.同年，Chamani等人[9]提出了3種方案，分別滿足后向安全的3種類型，對其效率和安全性進行了分析對比.Zuo等人[10]提出一種滿足更強后向安全的方案，并在補充方案中進行了分塊操作，實現了大量數據更新.Vo等人[11]利用SGX硬件結合批處理數據和壓縮狀態技術，減少了SGX與服務器的通信開銷.He等人[12]與Demertzis等人[13]就減少客戶端存儲開銷問題，分別提出自己的方案.Zuo等人[14]將文獻[10]拓展到范圍查詢，在保證安全性的前提下豐富了動態搜索加密技術的功能.

在實際應用中發現，云服務器可能會因為外部攻擊或者內部配置錯誤，變成惡意服務器返回給用戶錯誤結果或者不完整結果.鑒于這種情況，Chai等人[15]提出第1個可驗證搜索加密方案，基于單詞構造樹為索引，對結果進行驗證.隨后，Soleimanian等人[16]利用偽隨機函數和單向函數，完成了對結果驗證的公開化.Zhang等人[17]在方案中引入多值Hash函數，提高了其方案的驗證效率.Liang等人[18]利用改進的k近鄰算法技術對文檔與關鍵詞進行相關度分數計算，最后通過向量內積的方法對文檔是否包含關鍵詞進行驗證.2020年，Tong等人[19]將Merkle Hash Tree與k均值聚類相結合，提出了2種方案，在提升驗證效率的同時也提高了安全性.Miao等人[20]將公共審計技術引入到方案中，由可信第三方進行審計并如實報告給用戶.2020年，Yang等人[21]通過將驗證過程轉化為線性編程任務，解決了語義環境下的相關性驗證問題.

Fig. 1 Bitmap index and basic operations圖1 位圖索引及基本操作

以上方案均假定用戶是可信的，會誠實地執行驗證過程并發布驗證結果.但是有些用戶可能否認云服務器返回的正確結果，達到拒絕支付服務費的目的.隨著區塊鏈的出現，將可搜索加密技術與區塊鏈相結合，確保了返回結果的正確性，從而無需用戶進行驗證.Shamshad等人[22]將私有鏈與聯盟鏈結合，將索引存儲在聯盟鏈中，而將密文存儲在私有鏈中.Zhang等人[23]將基于屬性的索引上傳到區塊中，當用戶滿足屬性策略時會獲得區塊地址，從而獲得密文數據.Hoang等人[24]通過創建隱藏數據列表，使得用戶在獲取數據時不會泄露身份以及交易信息.Li等人[25]將二叉樹存儲在區塊鏈中，并對其進行分塊處理，實現了區塊鏈中多關鍵字的搜索.但是以上方案都是在區塊鏈中存儲加密索引，由于區塊鏈的燃料限制以及價格昂貴，在實際應用中受到了很多限制.最近，Guo等人[26]將索引以及搜索過程交由鏈下處理，區塊鏈僅對結果進行驗證，并且實現了前向安全.Li等人[27]分別對關鍵字和文檔標識符構造索引，實現了對文檔的鏈下刪除.雖然以上方案在不同程度解決了云服務器與用戶的驗證問題，但是對動態更新安全并沒有進行深入的考慮.

2 預備知識

2.1 位圖索引技術

以往方案都是基于倒排索引構造，對于一次性更新大量數據效率低下且繁瑣.基于上述問題的考慮，位圖索引技術由此誕生.每個關鍵字對應一個字符串，字符串的長度代表數據庫支持的最大文件數.其中若該關鍵字存在于文檔fi，則將其對應第i位變為1，否則設置為0.為了方便闡述其構造，我們用圖1進行舉例說明.如圖1(a)是一個長度為6的字符串，此時表示關鍵字存在f4和f2兩篇文檔.如圖1(b)所示，現在我們想增加一篇文檔f0包含該關鍵字，需要構造其對應的字符串為20=000001，然后與原始字符串進行加法.如圖1(c)所示，如果想刪除文檔f4，首先構造其對應的字符串為-24=-010000.由于以上索引計算都需要將結果與26進行模運算，所以可以將-24轉化為-24=26-24=48，其對應二進制字符串為110000，隨后與原始字符串相加，得到最終結果.通過上述運算，我們可以發現無論刪除增加都可以利用模加法完成.

2.2 同態加法對稱加密

由于位圖索引的特殊構造，無論刪除還是增加文檔，都可以使用加法來實現，我們可以采用同態加法對稱加密技術對數據進行處理，這樣可以保證云服務器上加密數據的安全更新，保證了后向安全.同態加法對稱加密方案Ⅱ主要由4個算法組成.

1)n←Setup(λ).輸入安全參數λ，輸出公共參數n，其中n=2m代表整個明文消息空間大小，m為整個方案支持的最大文件數目.

2)ct←Enc(msg,sk,n).輸入公共參數n，明文消息msg(0≤msg

3)msg←Dec(ct,sk,n).輸入公共參數n，密文ct以及密鑰sk，然后通過計算msg=ct-skmodn計算明文消息.

(1)

完美安全性[28]：如果對于任何敵手A，在完美安全游戲中的優勢可以忽略，或者存在以下不等式.

(2)

其中n←Setup(λ)，negl(λ)可忽略不計的，則本方案具有完美安全性.由于篇幅限制，同態加法對稱加密可以在文獻[28]中找到詳細的完美安全性證明，本文不再贅述.

2.3 符號定義

符號的定義如表1所示.

2.4 區塊鏈及智能合約

以太坊[29]是一種基于區塊鏈的分布式可計算平臺，其支持圖靈完備的編程語言.以太坊的安全性主要依靠解決困難問題(或者說是區塊)，礦工會通過解決困難問題來獲得獎勵，保證了以太坊中的任何操作都是透明且可靠的.而智能合約作為以太坊中的一部分，也隨之提出.

Table 1 Systematic Parameters

智能合約[30]是一種伴隨著狀態變化的應用，存在于區塊鏈中.發布智能合約本質上就是將一筆交易發布到區塊鏈，區塊鏈中所有礦工會進行工作，當挖出包含此智能合約的區塊時，智能合約也會有自己對應的地址，并且區塊鏈中的所有節點都會保存此智能合約.而礦工的也會得到獎勵，獎勵由gaslimit×gasprice所決定，其中gaslimit為發送方可以支出的最多燃料，gasprice為發送方為每個燃料支付的費用.正是由于這種特性，保證了智能合約的工作可靠性.對于所有需要在可信環境下進行的操作，理論上都可以使用智能合約來執行.

2.5 聚合消息認證碼

聚合消息認證碼(aggregate message authentication code, aggregate MAC)是一種通過減少數據消息認證碼數量，達到高效地驗證多條數據的技術.舉例而言，給定2個數據消息認證碼對(m1,δ1)和(m2,δ2)，其中δi=Auth(K,mi)，i∈{1,2}.將2個消息認證碼進行異或操作，得到聚合消息認證碼δ*=δ1⊕δ2，當對這2條數據(m1,m2)進行驗證時，只需對聚合消息認證碼δ*驗證即可.利用這種技術，可以大大減少以太坊中數據量，避免超過gaslimit的限制.

3 系統模型

3.1 系統簡介

系統模型如圖2所示，分為3個實體部分，分別為客戶端、云服務器以及區塊鏈.

Fig. 2 Scheme model圖2 方案模型圖

1) 客戶端.客戶端既是數據擁有者也是用戶，主要負責對數據以及索引進行加密，并將索引進行認證處理得到消息認證碼.密文以及索引上傳到云服務器，消息認證碼上傳到區塊鏈中.同時，也可以對云服務器發送搜索請求，或者對原有數據進行動態更新.

2) 云服務器.云服務器主要負責存儲索引和密文數據，并且會向客戶端提供搜索服務，將結果發送到區塊鏈中進行驗證.

3) 區塊鏈.區塊鏈系統主要負責對云服務器上傳的結果進行驗證，如果結果正確并通過驗證，說明結果是正確的，將搜索服務費支付給云服務器，并將結果永久保存.隨后，客戶端從區塊鏈中獲取加密結果.

為了保證系統內所有操作不可篡改且無法否認，所有的操作都是以交易的形式發布.區塊鏈中的任何節點都可以對交易中的內容進行驗證，使得客戶端不可謊稱結果錯誤而拒絕支付服務費，云服務器必須誠實執行搜索服務.

3.2 威脅模型

本文為了應對更加復雜的情況，假設整個方案置于不可信的環境進行設計，存在3種強有力的攻擊者：

1) 由于區塊鏈的公開透明特性，對于存儲的數據以及進行操作都是公開的，可能存在潛在攻擊者會對數據以及操作進行分析，獲取各自之間的聯系，進而對數據安全以及用戶隱私產生威脅.

2) 客服端在請求服務器進行搜索服務后，可能會出于自私的目的，否認服務器返回的正確結果，進而拒絕向其支付服務費.

3) 云服務器可能會對存儲本地的數據進行分析，獲取一些敏感信息，還可能會出于某些自私的原因，提供給用戶不可信的操作，其中主要涉及到更新以及搜索服務.當客戶端提出請求后，云服務器拒絕提供服務并返回錯誤結果.

3.3 安全目標

基于3.2節所述的威脅模型，本方案應遵循以下安全目標，以達到保護用戶隱私以及數據安全的目的.

1) 隱私性.由于云服務器和其他潛在的攻擊者可能會對數據和索引進行分析，所以需要預先對數據以及索引進行加密處理，避免攻擊者獲取任何敏感信息.

2) 前向安全.前向安全指的是客戶端上傳了一篇新文檔，這篇文檔中包含之前搜索過的關鍵字，攻擊者無法通過之前的陷門搜索到該文檔，也就無法得到關鍵字與文檔之間的關系.

3) 后向安全.后向安全指的是先前添加的文檔被刪除后，后續的搜索操作不會泄露該文檔的信息.其中后向安全在文獻[7]被分為3種類型，本方案比Type-Ⅰ類型還要安全，即攻擊者除了更新時間以及最后結果外，無法獲得任何信息.

4) 驗證性.需要對惡意用戶以及惡意云服務器進行雙向驗證，將驗證過程交由區塊鏈去執行，保證了各個實體的誠實操作.

4 系統描述

4.1 設計理念

前向安全與后向安全作為動態搜索加密方案中的2個重要的安全屬性，在更新時需要生成新的關鍵字令牌，并且保證攻擊者無法知曉結果涉及的文檔插入時間.而結果完整性驗證則需要知道結果是否涉及同一關鍵字，這與前向安全和后向屬性產生沖突.由于存儲空間以及計算能力的限制，將結果交由用戶驗證是不切實際的.此外，用戶還可能謊稱錯誤結果，進而拒絕支付服務費.因此，本方案需要解決2個問題：1)前向安全、后向安全與結果驗證之間的沖突；2)結果驗證的可信問題.

根據后向安全的簡單定義，只需要保證云服務器在搜索某個關鍵字時，無法搜索到先添加后刪除的文檔即可.我們可以改變索引以及加密方式，使得云服務器無法識別刪除操作與增加操作的區別來達到后向安全.由于位圖索引的增加和刪除操作都可以使用模加法表示，然后使用同態加法對稱加密技術對位圖索引進行加密，使得在云服務器看來都是在添加加密數據，也就無法知道關鍵字與刪除的文檔之間的關系.通過以上方法，將問題簡化為前向安全與結果驗證之間的沖突以及結果驗證的可信問題.

首先，為了解決結果驗證的可信問題，引入區塊鏈系統作為第三方可信實體，客戶端將預先定義的檢查列表上傳到智能合約中，對云服務器返回的加密結果進行驗證.由于區塊鏈的公開驗證以及不可否認性，保證了驗證結果的絕對可信，使得云服務器無法返回錯誤結果，客戶端也無法謊稱正確結果為錯誤的.

接下來需要解決前向安全與結果驗證之間的沖突問題.對于本方案，我們需要保證云服務器存儲的索引和區塊鏈中存儲的檢查列表滿足前向安全.根據前向安全的簡單定義，我們可以簡化為該加密數據在搜索過后進行了更新，需要生成新的標志指向該加密數據，而沒有搜索過就進行更新的數據，則不需要生成新的標志.檢查列表在每次更新時都需要生成新的標志，主要原因是：1)如果該關鍵字是搜索之后的首次更新，需要生成新的標志指向新的檢查列表，防止智能合約搜索到之前的檢查列表對結果進行驗證，產生錯誤的驗證結果.2)如果該關鍵字不是搜索之后的首次更新，需要搜索之前的檢查列表，將新的加密索引對應的MAC與之前檢查列表進行聚合，這種情況也需要生成新的標志指向新的檢查列表.并且對于以上2種原因，為了防止攻擊者測試從未查詢過的加密結果與檢查列表之間的關系，每次更新后檢查列表需要插入一個新的隨機數α.同樣，對于存儲在云服務器中的加密索引，索引標志只有在搜索之后才會更新.

最后，對于驗證通過的加密結果將被永久保存在區塊鏈中，在該關鍵字沒有發生更新的情況下，客戶端可以直接從區塊鏈中獲取加密結果，避免了云服務器的重復搜索操作，提高了搜索效率.

Fig. 3 Design structure圖3 設計結構

4.2 具體方案

1)Setup(1λ).客戶端在本地初始化系統，輸入參數λ，輸出主密鑰K←{0,1}λ和一個整數n=2m，其中m為此方案可以容納的最大文件數.初始化空集Map和EDB，其中Map用來記錄更新以及搜索狀態，EDB用來存儲加密數據集.

2)Buildindex(w,bs,Map,EDB).輸入關鍵字w及其對應的字符串bs.將更新次數c以及搜索次數cs置為0，搜索狀態S置為N表示沒有被搜索.首先生成搜索令牌K1、密鑰令牌K2和檢查列表標志lc.利用搜索令牌K1生成新的索引指針UTc，由于初始化時該指針為首個指針，并不存在以前的指針，所以將之前的指針置為空，并進行異或操作得到密文CTc.隨后，用密鑰令牌K2與當前更新次數c生成一次性密鑰Skc，對字符串bs加密.客戶端生成隨機數αc，與密文Ec進行Hash認證.最后，將加密數據庫EDB以及檢查列表LT分別發送到云服務器和區塊鏈，客戶端本地更新Map.

該算法中搜索狀態S和搜索次數cs是為了實現前向安全而設置的參數，通過對搜索狀態S判斷云服務器是否執行過搜索算法，進而考慮搜索次數cs是否需要更新，而更新次數c負責對更新字符串的加密，所以只要發生更新過程，更新次數就需要加1.

算法1.構建索引算法.

輸入：需要構建索引的關鍵字w、關鍵字對應的位圖索引bs、本地狀態映射Map以及加密數據庫EDB;

輸出：檢查列表LT以及加密數據庫EDB.

客戶端:

① 生成一個隨機數αc;

② {c,cs}← 0,S←“N”,lc←F(K,cs‖c);

③K1←F(K,w‖cs),K2←F(K,w‖⊥);

④UTc←H1(K1,c);

⑤CTc←H2(K1,UTc)⊕⊥;/*初始化時并

不存在之前的指針，UTc-1置為空*/

⑥Skc←H3(K2,c);

⑦Ec←Enc(Skc,bs,n);

⑧Vc←H4(Ec,αc);

⑨ 將[UTc:CTc,Ec,αc]發送到服務器，將

[lc:Vc]發送到區塊鏈;

⑩ 更新Map[w]←{c,cs,S,UTc};

云服務器:

區塊鏈:

Fig. 4 Search status圖4 搜索狀態

客戶端得到密文結果后，本地計算密鑰Sumsk， 解密獲得最終字符串bs以及匹配文檔標識符.

算法2.搜索算法.

輸入：需要搜索的關鍵字w、本地狀態映射Map以及加密數據庫EDB;

輸出：關鍵字w對應的最終結果bs.

客戶端:

① 獲取{c,cs,S,UT}←Map[w],K1←F(K,

w‖cs);

② ifS==“Y” then

③ 將K1發送到區塊鏈中；

④ 區塊鏈進行搜索{Sume}←MEI[K1];

⑤ returnSume;

⑥ else

⑦UTc←H1(K1,c),lc←F(K,cs‖c),

⑨ end if

服務器:

⑩ fori=0 untilEDB[UTi]=⊥ do

αc-i}發送到區塊鏈;

區塊鏈:

/*如果不存在，則需要初始化*/

客戶端:

算法3.更新算法.

輸入：需要更新的關鍵字w、關鍵字對應的位圖索引bs、本地狀態映射Map以及加密數據庫EDB;

輸出：更新后的檢查列表LT和加密數據庫EDB.

客戶端:

① 獲取{c,cs,S,UT}←Map[w];

②lc+1←F(K,cs‖c+1);

③K2←F(K,w‖⊥),生成一個隨機數αc+1;

④Skc+1←H3(K2,c+1);

⑤Ec+1←Enc(Skc+1,bs,n);

⑥Vc+1←H4(Ec+1,αc+1);

⑦ ifS==“Y” then/*對當前關鍵字對應的

搜索狀態進行判斷*/

⑧cs=cs+1;

引指針為更新后的首個索引指針*/

/*仍然使用之前的密鑰*/

引指針連接到之前的索引指針上*/

客戶端:

區塊鏈:

5 安全分析

5.1 安全模型

本方案采用文獻[10]安全模型，通過現實模型Real和理想模型Ideal完成.Real模型與本方案行為一致；而Ideal模型則反映了模擬器S的行為，模擬器S以泄露函數L=(LSetup,LUpdate,LSearch)作為輸入.需要特別說明，由于Buildindex算法與Update算法只是在客戶端存在差異，但是對于敵手A是相同的行為，所以二者的泄露函數沒有區別.然后，我們給出Real模型與Ideal模型的定義.

RealA(λ)：首先運行Setup算法輸出EDB，敵手A執行搜索查詢sr(或者更新查詢(op,in))，隨后A輸出結果b∈{0,1}.

IdealA,S(λ)：模擬器S輸入泄露函數LSetup，敵手A進行搜索查詢sr(或者更新查詢(op,in))，模擬器S輸入泄露函數LSearch或者LUpdate作為回答，敵手A輸出結果b∈{0,1}.

如果對于任何概率多項式敵手A存在高效模擬器S以及輸入L，使得:

|Pr[RealA(λ)=1]-Pr[IdealA,S(λ)]|≤
negl(λ),

(3)

其中negl(λ)是可以忽略的函數，則說明本方案滿足L-自適應安全.

5.2 前向安全

對于任何敵手而言，前向安全保證了更新不會泄露新添加的文檔與之前搜索查詢的匹配信息.如果更新泄露函數LUpdate可以寫成

LUpdate(op,in)=L′(op,{(fi,μi)}),

(4)

{(fi,μi)}是1組發生過更改的關鍵字-文件標識符對，μi是文檔fi包含的關鍵詞數量，op為具體更新操作.在本文中，泄露函數可以寫成

LUpdate(op,w,bs)=L′(op,bs),

(5)

其中w為更新過的關鍵字，bs為新添加的字符串.

5.3 后向安全

后向安全保證了當之前添加的文檔被刪除后，在添加之前的搜索和刪除后的搜索不會泄露關于這篇文檔的信息.文獻[7]定義了3種不同級別的后向安全，從低到高分為Type-Ⅲ，Type-Ⅱ，Type-Ⅰ.

本方案采用位圖索引，達到了更強的后向安全Type-Ⅰ-，下面給出Type-Ⅰ-與Type-Ⅰ的區別.

Type-Ⅰ-：對于關鍵字w的2次搜索，只會泄露該關鍵字最終匹配文檔結果，以及該關鍵字的更新次數和更新時間.

Type-Ⅰ：對于關鍵字w的2次搜索，除了泄露該關鍵字最終匹配文檔結果和更新次數，還會泄露結果中文檔的添加時間.

在正式定義Type-Ⅰ-之前，需要構建一個新的泄露函數Time.對于關鍵字w的一次搜索查詢，Time(w)會列出其對應的每次更新時間戳t.對于一系列的更新查詢Q′：

Time(w)=(t:(t,op,(w,bs))∈Q′).

(6)

如果搜索泄露函數以及更新泄露函數可以寫成下面2個公式：

(7)

即滿足Type-Ⅰ-后向安全.其中sp(w)為搜索模式且sp(w)={t:(t,op)∈Q}，Q為一系列的搜索查詢;rp(w)=bs*為結果模式，bs*代表當前w匹配的所有文檔標識符;L′與L″表示2個無狀態的函數.

5.4 具體安全分析

定理1.如果偽隨機函數F是安全的，所有Hash函數具有抗碰撞性質，II=(Setup,Enc,Dec,Add)是具有完美安全性的同態加法對稱加密算法，則定義本方案泄露函數L=(LUpdate,LSearch)，其中LUpdate(op,w,bs)=⊥，LSearch(w)=L″(sp(w),rp(w),Time(w))，那么本方案為滿足自適應安全、前向安全以及Type-Ⅰ-后向安全的定義.本文與文獻[10]中方案類似，由此給出以下安全分析：從模型Real到Ideal設置一系列游戲，每個游戲都與上一個游戲有所不同，但是對于敵手A無法區分2個游戲，最后使用定理1中泄露函數模擬Ideal，從而得到敵手A無法區分模型Real和Ideal.在游戲中敵手A會嘗試破壞本方案的安全，挑戰者C負責生成搜索令牌以及密文，模擬器S則從始至終模擬A與C的交互.

游戲G0與現實模型游戲RealA(λ)相同，所以有

Pr[RealA(λ)=1]=Pr[G0=1].

(8)

在游戲G1中，當查詢使用F生成關鍵字w的密鑰時，如果該密鑰之前沒有被搜索過，挑戰者C則選擇一個新的隨機密鑰返回給敵手A，并保存在表KeyL中，否則返回KeyL表中關鍵字w對應的密鑰.如果敵手A可以區分G0與G1的優勢，則

(9)

在游戲G2中，對于Update算法我們采用隨機字符串作為索引指針UTc，并將其保存在表UTL中，即UTL[w,c]=UTc.隨后在搜索算法中，我們將這些隨機字符串處理為隨機預言機H1的輸出，其中H1(K1,c)=UTL[w,c].當敵手A把(K1,c)輸入H1進行查詢時，挑戰者C會輸出UTL[w,c]并保存在HL表中以應對接下來的查詢.如果(K1,c+1)已經存在HL表中，那么就不會輸出UTL[w,c+1]并且游戲中止.由于UTc為挑戰者C隨機選擇的字符串，所以敵手A可以猜測到正確的索引指針的概率為1/2λ，假設A可以進行多項式q次查詢，那么其概率為q/2λ，所以得出:

Pr[G2=1]-Pr[G1=1]≤q/2λ.

(10)

在游戲G3中，我們將Hash函數H2也轉化為隨機預言機，由于G3與G2類似，可以得出:

Pr[G3=1]-Pr[G2=1]≤q/2λ.

(11)

在游戲G4中，同樣將Hash函數H3轉化為隨機預言機.由于敵手A不知道密鑰K2，所以其猜測正確一次性密鑰的概率為1/2λ.假設A可以進行多項式q次查詢，那么其概率為q/2λ，所以得出:

Pr[G4=1]-Pr[G3=1]≤q/2λ.

(12)

在游戲G5中，我們使用一個全為0的字符串bs#去代替字符串bs，并且二者的長度相同均為m.如果敵手A可以區分G5與G4，則其獲得的優勢概率為

(13)

接下來，我們將使用模擬器S從敵手A的視角進行模擬，使用泄露函數sp(w)代替關鍵字w.使用第1個時間戳w*←minsp(w)，并且移除對于敵手A沒有影響的部分.對于Update算法很明顯看出，在G5游戲中每次更新都會選取新的隨機字符串.在Search算法中，S會從當前的索引指針UT開始，并選取隨機字符串作為之前的索引指針，然后通過H2得出更新密文CT，將bs*轉化為索引指針UT，并將剩余所有0字符H3轉為剩下的一次性密鑰.隨后，我們將(w,i)映射到全局計數器t上，然后將索引指針表UTL、更新密文表CT以及Update算法中隨機選取的一次性密鑰sk，作為Search算法(w,i)對應的值.可以得出:

Pr[G5=1]=Pr[IdealA,S(λ)=1].

(14)

最后，我們可以總結為如下等式

(15)

由于本方案采用偽隨機函數是安全的，Hash函數具有抗沖突性質且同態加法對稱加密具有完美安全性，所以可以得出敵手A區分出Real模型和Ideal模型的優勢為可以忽略的函數negl(λ).綜上所述，本方案滿足自適應安全以及前向安全和后向安全定義.

6 方案分析

6.1 功能分析

將本文方案與文獻[10,17,26-27]進行了功能上的對比，如表2所示.文獻[10]達到了前向安全與后向安全，但是對于云服務器返回的結果并沒有驗證其正確性，并且無法保證云服務器是否如實地刪除了之前狀態的索引，是否將最終結果誠實記錄在最新狀態下.文獻[17]支持對結果正確性的驗證，但是其安全性僅支持前向安全，每次更新狀態只對應一個關鍵字-文檔標識符對，造成了很大的存儲以及計算開銷.

Table 2 Comparison of Function

文獻[26-27]均基于區塊鏈平臺，將搜索過程與驗證過程進行分離，達到了對惡意用戶和云服務器的雙向驗證，但是二者均不支持后向安全.文獻[26]中的方案，只給出了增加文檔的具體算法，對于刪除操作并沒有進行詳細說明.文獻[27]方案中的刪除算法需要在搜索算法執行之后才能進行，所以可能導致最后結果中包含已經刪除的文檔，使其變成了錯誤結果.

從功能上說，本方案實現了前向安全與后向安全，對于用戶與云服務器進行了雙向驗證，保證了整個方案的誠實執行.將最終結果保存在區塊鏈中，用戶在獲取結果后本地進行解密，保證了刪除文檔不會被搜索.本方案在提高安全性的同時減少了用戶本地的計算存儲開銷，提高了云服務器的搜索以及更新效率.

6.2 理論分析

在理論分析方面，我們給出了本文方案與其他方案在計算開銷復雜度方面的對比，為了簡單明了地展示對比結果，對比參數均設定在一次更新的情況下進行，其中ND表示關鍵字w需要更新的文檔數量.如表3所示，由于本方案采用了位圖索引，所以不需要對所有的包含關鍵字w的更新文檔進行操作，復雜度僅為O(1).

Table 3 Comparison of Computational Complexity

6.3 實現分析對比

本方案實驗環境參數為64 b Windows 操作系統，Intel?CoreTMi5-4570 CPU 3.20 GHz、內存16.00 GB.使用Enron Email數據集作為原始數據集，提取出子集作為測試數據集.實驗中智能合約使用Solidity語言，與智能合約交互語言為Python語言.加密算法基于SHA-256構建，MAC生成算法與偽隨機函數均采用HMAC-SHA256.最后將智能合約部署到Ganache網絡.由于文獻[10,17]并非基于區塊鏈構建的方案，且不能對用戶和云服務器進行雙向驗證，所以我們將本方案與文獻[26-27]分別在索引生成、搜索、更新以及驗證4個方面進行了性能對比.

如圖5所示，隨著關鍵字數量的增加，構建索引時間呈現線性增長趨勢.但是本方案的索引構建時間遠小于其他方案，主要因為文獻[26-27]需要對每個關鍵字-文檔標識符對進行加密操作，隨后將該關鍵字對應的所有文檔標識符密文進行連接處理，而本方案只需要對關鍵字對應的字符串進行加密即可，減少了計算開銷.

Fig. 5 Build index time圖5 構建索引時間

對于搜索方面的性能對比，將關鍵字涉及的更新次數設置為參數，即在不同方案中關鍵字w取相同的更新次數，每次更新的關鍵字-文檔標識符對數量也相同.如圖6所示，本方案的搜索時間成本低于其他方案，主要原因在于本方案的搜索時間與更新次數呈線性相關，每次搜索過程中只需對位圖索引進行匹配即可，而其他方案則需要對關鍵字w涉及到的所有加密數據進行匹配.并且，由于本方案會將驗證通過后的位圖索引加密結果記錄在區塊鏈中，客戶端可以直接對其進行搜索，減少了重復驗證的過程，進而提高了搜索效率.

Fig. 6 Search time圖6 搜索時間

對于更新方面，我們以關鍵字w的1次更新涉及的文檔數量為參數，即在對比試驗中不同方案都只更新1次，在更新中涉及到的關鍵字-文檔標識符對數量相同.如圖7所示，文獻[26-27]中方案的更新時間隨著文檔數量的增加而增加，造成這種現象的主要原因在于，這2個方案的索引采用鏈式結構，在更新過程中，需要對每個文檔標識符重復加密2次，并且為了最后可以對其進行驗證，還需要對每個文檔標識符進行Hash運算.而本方案由于其特殊的索引構造，在每次更新過程中只需要對索引進行1次加密和Hash運算即可，與文檔標識符數量無關，導致更新時間不會發生劇烈變化，且更新時間遠低于其他方案.

Fig. 7 Update time圖7 更新時間

如圖8所示，驗證時間隨著更新次數的增加而增加.本方案在進行驗證時只需要對返回的加密字符串進行Hash運算即可，而其他方案需要對所有文檔標識符進行計算，導致了大量的計算開銷.最后區塊鏈需要將加密字符串進行加法操作，從而得到最終的加密結果，雖然在一定程度上影響了本方案的驗證時間，但是對比其他方案仍具有一定優勢.

Fig. 8 Verification time圖8 驗證時間

7 總 結

本方案將區塊鏈與可搜索加密技術進行結合，提出了一種雙向驗證的動態密文檢索方案.本方案主要應用于需要確保數據絕對安全的私有云環境，例如機密機構的數據庫.由于一個位圖索引可以表示多個文件標識符，減少了關鍵詞對應的加密數據，提高了搜索效率以及更新效率，并使用同態加法對稱加密技術，實現了云服務器對數據的安全更新.將驗證過程交由區塊鏈去處理，實現了對用戶與云服務器的雙向驗證，保證了結果不可否認.同時針對方案中索引生成、搜索、更新以及驗證4個方面進行了實驗測試，測試結果顯示本方案具有較高的效率.

未來工作將會針對可搜索加密如何在區塊鏈環境下實現1對多用戶模型的雙向驗證，并且安全地實現數據擁有者對數據用戶的訪問控制.

作者貢獻聲明：杜瑞忠負責論文方案的構思以及論文的撰寫與分析，并對論文整體進行把關；王一負責論文的撰寫、修改；李明月對方案提出了改進意見.