一種支持動態可驗證的密文檢索方案

杜瑞忠，王 一，田俊峰

(1.河北大學 網絡空間安全與計算機學院，河北 保定 071002；2.河北大學 河北省高可信信息系統重點實驗室，河北 保定 071002)

云存儲是當下一種主流的在線存儲方式，免去了用戶本地存儲的硬件與管理開銷。但是數據脫離了用戶的物理控制，導致數據安全受到巨大威脅。為了解決云存儲的數據安全問題，學者們提出了可搜索加密作為安全搜索的核心技術。

可搜索加密[1-4]是一種支持用戶在密文中進行關鍵字檢索的新技術，主要解決云存儲環境下如何利用不可信的服務器實現基于關鍵字的安全搜索，使用戶能夠將加密的數據存儲到云中，并通過密文域執行關鍵字搜索，有選擇地從云中檢索感興趣的文檔，為用戶節省了大量開銷。然而以上方案全是假定服務器是誠實、好奇的實體，但在現實世界中，云服務器可能因為外部攻擊或者內部配置錯誤，返回錯誤或者不完整結果，從而對用戶進行欺騙。考慮到以上問題，可驗證搜索加密方案[5-9]進入到學者視野，這些方案使得用戶可以對結果進行驗證，進而判斷服務器是否為惡意服務器。

但是數據集并不是一成不變的靜態環境，如何在動態環境下對結果進行驗證，成為學者需要考慮的首要問題。文獻[10]將時間戳引入到驗證過程中，實現了在文檔動態環境下的驗證，但是其搜索復雜度超過了線性時間。隨后，研究人員通過將索引對應的消息認證碼(Message Authentication Codes，MAC)存儲在樹形結構中[11-12]，通過對根節點的驗證來實現對結果的驗證。但是，每一次更新需要重新計算樹上所有相關節點，對數據擁有者來說計算開銷巨大，并且以上方案是在單用戶模型下實現，僅包括數據擁有者與服務器兩個實體。

在動態可搜索加密方案中，前向安全和后向安全是兩個重要的安全屬性，可以確保在更新數據時不會發生信息泄漏。文獻[13]首先提出了關于前向安全和后向安全的概念。隨后，學者們在具有前向安全的搜索加密方案[14]的基礎之上，設計了一種可驗證的前向隱私搜索加密方案[15]。后向安全作為動態搜索加密方案中一個重要的安全屬性，在文獻[16]中首次被提出，并在文中對后向安全給出了形式化的定義。但是，以上方案不能很好地解決一對多模型下的訪問控制問題。

隨著區塊鏈的興起，因其不可篡改的性質，逐漸進入大家的視野。2017年，LI等[17]提出了一種基于區塊鏈的可搜索加密方案，但是該方案把加密數據和索引全部上傳到區塊鏈中，增大了存儲開銷。HU等[18]提出了更加完善的搜索加密過程，并且實現了索引的動態更新。但是此方案并沒有對云服務器更新之后的數據進行驗證，無法保證用戶得到正確結果。2019年，CHEN等[19]將區塊鏈下可搜索加密應用到具體場景中。同年，JIANG等[20]使用橢圓曲線加密函數，實現了數據擁有者和用戶之間的秘密授權，但是該方案同樣沒有保證用戶得到正確結果。LI等[21]將時間鎖技術和區塊鏈相結合，實現了單關鍵字的加密搜索，但是對于大量數據上傳到區塊鏈中仍然存在困難。最近，CHEN等[22]在其方案中實現了前向和后向安全，但是并沒有很好解決一對多模型下授權訪問問題。李涵等[23]將驗證過程交由區塊鏈處理，但是其方案僅考慮了前向安全，并且對于云服務器是否誠實刪除文檔沒有進行考慮。

基于以上問題，筆者提出了一種基于區塊鏈的動態可驗證密文檢索方案，旨在解決動態環境下可搜索加密的數據隱私和結果正確性問題。主要貢獻如下：

(1) 通過利用以太坊中的智能合約，將搜索和更新操作交給智能合約執行，以確保返回結果的正確性。此過程同時支持前向和后向安全，保證數據更新時不會泄漏任何相關信息。

(2) 利用以太坊外部賬戶的基本特性，提出了一種新的授權訪問模型。通過將授權信息加密打包進一筆交易的方式，完成了一對多模型下的授權訪問。并且在這種模型下，攻擊者無法通過更新之前的陷門獲得數據更新后的任何信息。

(3) 將該方案部署到本地私有網絡(Ganache)中，對大量真實數據集進行分梯度實驗。實驗結果分析表明，該方案在索引生成、搜索效率以及驗證時間具有一定優勢。

1 預備知識

1.1 區塊鏈及相關知識

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

智能合約是部署在區塊鏈上的一些特殊腳本代碼，即使其創建者也無法進行修改，并且可以根據內容自動執行。發布智能合本質上就是將一筆交易發布到區塊鏈中，區塊鏈中所有礦工會進行工作，當挖出包含此智能合約的區塊時，區塊鏈中的所有節點都會保存此智能合約。而礦工也會得到獎勵，獎勵由gaslimit×gasprice決定，其中，gaslimit為發送方可以支出的最多燃料，gasprice為發送方為每個燃料支付的費用。由于每個節點都會存儲智能合約，所有存儲的數據和智能合約的已執行計算對任何用戶都是透明且不可篡改的。對于所有需要在可信環境下進行的操作，理論上都可以使用智能合約來執行。

1.2 外部賬戶

外部賬戶(Externally Owned Account，EOA)也叫賬戶，以太坊中外部賬戶由密鑰生成，可以調用智能合約和發送交易，也可以存放以太幣。每個賬戶都有一個地址，這個地址由私鑰和公鑰所控制。私鑰先經過橢圓曲線數字簽名算法得出對應公鑰，然后公鑰進行Keccak-256哈希運算，截取最后20字節即為賬戶地址。賬戶每次發起的交易，都會顯示發送方地址和接收方地址。

1.3 聚合消息認證碼

由于以太坊中gaslimit的限制，普通消息認證碼的存儲開銷太大且效率低下，并不適用于智能合約。因此，可以通過減少MAC數量的方式，降低智能合約中消息認證碼相關計算量，從而實現提高搜索效率和避免超過gaslimit的目的。基于以上思想，聚合消息認證碼(Aggregate MACs，AMAC)被引入到文中。舉例而言，給定兩個數據消息認證碼對(m1，δ1)和(m2，δ2)，其中，δi=Auth(K，mi)。將兩個消息認證碼進行異或操作，得到聚合消息認證碼，

φ=δ1⊕δ2。

(1)

當對這兩條數據(m1，m2)進行驗證時，只需對φ進行驗證即可。

文中符號說明如表1所示

表1 符號定義

2 系統模型

2.1 系統簡介

圖1 方案模型圖

系統模型主要由4個部分組成。數據擁有者(Data Owner，DO)，云服務器(Cloud Server，CS)，區塊鏈系統(Blockchain)，以及數據用戶(Data Users，DU)，如圖1所示。

(1) 數據擁有者：主要負責將明文數據加密，并提取加密索引和AMAC。將密文數據上傳到云服務器，加密索引和AMAC上傳到智能合約中，用戶請求搜索時，對數據用戶進行授權并發送授權信息。

(2) 云服務器：主要負責密文數據的存儲，并根據數據用戶上傳的加密索引集合下發密文數據集合。

(3) 區塊鏈系統：主要負責接收并存儲數據擁有者發送過來的加密索引以及AMAC，接收數據用戶上傳的陷門，并根據陷門進行查詢，將查詢結果下發到數據用戶。

(4) 數據用戶：向數據擁有者請求授權后得到授權信息，并將授權信息上傳到區塊鏈中。根據查詢結果，請求云服務器下發密文數據，最后進行本地驗證。

2.2 安全目標

(1) 機密性：由于本方案中索引存儲在智能合約中，對任何實體而言都是透明且公開的，所以需要預先對索引進行加密，避免外部攻擊者可以獲得有關索引的任何有效信息。

(2) 前向與后向安全：在動態搜索加密方案中，需要支持前向與后向安全，才可以保護數據發生更新時不泄露有關索引信息。其中，前向安全指的是當添加了包含先前搜索的關鍵字的文檔時，攻擊者無法通過之前的陷門獲取有關該文檔的相關信息。后向安全是指當一篇之前增加的文檔被刪除后，這篇文檔不會在后續的搜索過程中泄露相關信息。

(3) 可驗證性：由于惡意云服務器可能返回錯誤結果，所以需要保證返回結果的可驗證性。可驗證性意味著當返回的結果是錯誤時，該結果以及對應的證據無法通過驗證。

2.3 威脅模型

由于區塊鏈的公開性，其中存儲的數據和智能合約的計算是公開的，根本沒有隱私可言。因此，可能存在攻擊者通過分析區塊鏈中存儲的數據或交易信息來獲取敏感信息。此外，云服務器可能由于某些原因無法執行數據擁有者發出的更新操作，并將錯誤結果返回給數據用戶。其中包括以下情況：

(1) 數據擁有者添加了一個文檔，但是云服務器沒有執行添加操作。當數據用戶搜索該文檔中包含的關鍵字時，云服務器選擇偽造一篇文檔將其返回給數據用戶。

(2) 數據擁有者會更新某篇文檔的內容，但云服務器并沒有執行更新操作。當數據用戶搜索此文檔中包含的關鍵字時，云服務器將更新之前的文檔返回給數據用戶。

(3) 云服務器并未按照數據擁有者的要求刪除某篇文檔。當數據用戶搜索此文檔中包含的關鍵字時，云服務器將本應刪除的文檔返回給了數據用戶。

3 系統描述

3.1 初始化階段

Setup(λ)→Para，SK：輸入安全參數λ，生成公開參數和本地參數。安全哈希函數包含以下函數(h1，h2，h3，h4，h5，H1，H2，H3，G)，其中，h1：{0，1}λ→{0，1}2λ，h2：{0，1}λ→{0，1}λ+logNmax，h3：{0，1}λ×{0，1}logNmax→{0，1}2λ，h4：{0，1}λ×{0，1}logNmax→{0，1}2λ，h5：{0，1}λ×{0，1}2λ-logNmax→{0，1}2λ以及H1：{0，1}*×{0，1}*→{0，1}2λ-logNmx，H2：{0，1}λ-1→{0，1}2λ，H3：{0，1}λ-1→{0，1}λ，G：{0，1}*×{0，1}*→{0，1}λ-1；隨后生成偽隨機置換函數P：{0，1}λ×{0，1}λ→{0，1}λ(P-1為P的反函數)。最后，廣播公開參數Para={h1，h2，h3，h4，h5，H1，H2，H3，P，P-1}，數據擁有者初始化一個映射空集Map，將本地參數SK={G，Map}保存在本地。

3.2 更新數據階段

如圖2所示，為了節約存儲成本和保護索引中文檔標識符數量，筆者采用了打包技術，將DB(wi)addition和DB(wi)deletion中的文檔標識符打包進塊。

圖2 打包索引圖

(2)

算法1數據更新算法。

輸入：打包索引數據庫PDB：{OP，PID，W，AM}；安全哈希函數(h1，h2，h3，h4，h5，H1，H2，H3，G)；偽隨機置換函數{P，P-1}以及本地狀態映射Map。

輸出：存儲到智能合約中的映射集合EDB。

① For eachwi∈W

③ if Map[wi]=⊥ then

⑤ end if

⑨ 數據擁有者更新保存在本地的映射圖Map；

在本算法中，c為版本指針，用來指示關鍵字wi的更新狀態次數。從表面來看，更新的數據以鍵值的方式存儲在區塊鏈中，并且各自密文之間彼此無關。但是包含相同關鍵字的密文之間具有隱藏關系，如圖3所示。其中最近更新狀態依次指向之前的更新狀態，并且每個更新狀態還對應著本次全部的更新索引。

圖3 隱藏關系圖

3.3 授權階段

用戶檢查最近區塊中的交易，并檢查地址是否為數據擁有者，若是，則用自己私鑰SKuser解密獲得授權信息Q={Twi，c，Kf，Km}。

3.4 搜索階段

Search(Para，Twi，EDB)→RI，α：輸入公共參數Para，數據用戶調用智能合約并發送陷門Twi，隨后智能合約執行算法2。

算法2數據搜索算法。

輸入：安全哈希函數(h1，h2，h3，h4，h5，H1，H2，H3，G)；偽隨機置換函數{P，P-1}；查詢關鍵字生成的陷門Twi；存儲在智能合約的映射集合EDB。

輸出：打包索引集合RI；AMAC結果α。

① 智能合約初始化一個空集RI，將α置為0；

② keywi=H2(Twi)；

③ valwi=EDB[keywi]；

⑥ While EDB[keylen]≠⊥ do

⑦ vallen=EDB[keylen]；

⑨ Forj=1 to m do

經過搜索算法過程，智能合約將RI和α存儲在日志中并發布出去。

3.5 解密階段

3.6 驗證階段

Verify(I，Km，α)→ 0 or 1：用戶上傳I到云服務器，云服務器根據I，將對應的密文文檔集合發送給用戶。隨后用戶在本地計算密文文檔集合的AMAC，

α+=δ1⊕δ2…⊕δi。

(3)

如果α+=α，則輸出1，代表通過驗證環節，密文文檔集合正確并進行解密；否則輸出0，意味著沒有通過驗證環節。

4 安全分析

4.1 適應安全

采用文獻[22]的安全模型，在有狀態的模擬器和攻擊者之前采用模擬游戲。游戲中的泄露函數定義為，

L=(LSetup，LUpdate，LAuthorization，LSearch) ，

(4)

定義1將本文方案定義為Ⅱ= (Setup，Update，Authorization，Search)，S代表模擬器，A表示攻擊者。隨后定義了以下兩個游戲。

只要文中方案Ⅱ對所有攻擊者存在以下公式，即可滿足自適應安全定義。

(5)

其中，negl(λ)為可以忽略函數。

定理1如果P是一個安全的偽隨機置換函數，并且所有安全的哈希函數具有抗沖突性質，那么文中的方案Ⅱ是自適應安全的。

在游戲G2中，維護一個列表SL，其中，SL[w，c]=stc，而不是通過P(Kc，stc-1)生成stc。在更新環節，當需要stc時，游戲隨機選取一個字符串stc={0，1}λ。因為偽隨機置換函數是安全的，所以非常簡單得出G2和G1是不可區分的。

|Pr[G2=1]=Pr[G1=1]| 。

(6)

在游戲G3中，將所有安全哈希函數轉化為隨機預言機，并維護一個列表用來存儲每個預言機的輸入與輸出。舉例而言，給定一個輸入x，隨機預言機隨機選取一個字符串y=h1(x)作為輸出，然后將其插入到列表h1-L。因為哈希函數具有抗沖突性，所以得出G3和G2是無法區分的。

|Pr[G3=1]=Pr[G2=1]| 。

(7)

在游戲G4中，在更新環節并沒有使用G(wi，c)生成Tagwi，而是采用一個隨機字符串Tagwi={0，1}λ。同時游戲需要維護一個列表，用來響應攻擊者A的授權查詢，其中列表存儲的為(wi，Tagwi，c)。如果攻擊者可以區分，則可以得出

|Pr[G4=1]-Pr[G3=1]|≤Pr[Bad] ，

(8)

其中，Bad表示攻擊者A可以區分隨機字符串和Tagwi的概率，這個概率為2-λ+negl(λ)。攻擊者最多進行次q1=poly(λ)猜測，其中，poly( )不是特性多項式。隨后，通過以上公式可以得出Pr[Bad]≤q12-λ+q1negl(λ)。可以看出，概率為可忽略的函數，因此得出G4和G3在計算上是不可區分的。

在最后一個游戲中，模擬器使用泄露函數從攻擊者A的視角進行模擬，其中泄露函數包含搜索模式和更新歷史。從攻擊者的角度來看，G5和G4的行為是一樣的。通過以上分析可以得出，G5和G4是無法區分的。

(9)

通過以上分析，可以得出

(10)

因為Pr[Bad]是可以忽略的函數，所以筆者提出的方案滿足自適應安全。

4.2 前向安全

4.3 后向安全

4.4 可驗證性

文中方案的驗證方法與文獻[12]的類似，因此給出如下定義。

定義2定義一個可驗證搜索加密方案為Ⅱ=(Setup，Update，Authorization，Search)。其中，A表示攻擊者，實驗Forge可以表示為如下：

證明：假設攻擊者A可以找到(C*，w，α*)?R。如果攻擊者A可以得到Verify(C*，w，Km，α*)=1，需要滿足以下條件：

攻擊者A可以找到一個元組{C*，w，δ*}，并非通過消息認證碼生成公式δi=Auth(fi，Km)輸出的，但是可以通過驗證公式Verify(C*，w，Km，α*)=1。定義如果攻擊者A成功地完成本次實驗，則等價于可以偽造一個消息認證碼通過驗證，這種通過的概率定義可以表示為Pr[ForgeA Ⅱ]。因為，本方案中消息認證碼生成函數是安全的，所以攻擊者可以偽造消息認證碼通過驗證的概率為可以忽略的。根據以上等式可以得出

(11)

綜上所述，本方案滿足可驗證性定義，證明完畢。

5 性能分析

5.1 功能對比

將文中方案與上述文獻對比，如表2中所示。

表2 功能對比

文獻[12]方案支持動態更新，并對更新結果可以進行驗證，但此方案只能在單用戶模型下進行，并且每次更新時也需要對Merkle Hash Trees更新，增加了數據擁有者的計算開銷。文獻[11]方案可以支持數據擁有者-云服務器-用戶模式下搜索加密，但是需要在這三者之間同步時間戳鏈，即使數據沒有進行更新，也需要定時發送證據到云服務器上。對于少量更新時，為維護時間戳鏈產生了許多額外開銷，并且每次更新需要查找Merkle Patricia Tree，對葉子節點進行更新。對于文獻[11]和文獻[12]，每次搜索過程還需要對驗證所需要的證據進行搜索，更新過程需要先完成對證據的搜索，然后再對證據進行更新。

文獻[18-20，22]都是基于區塊鏈平臺下進行，將搜索過程放入到智能合約中。文獻[19]是在靜態環境下進行，并不支持動態更新操作。文獻[18]與文獻[20，22]均支持動態更新，但是對于用戶從云服務器中下載的數據正確性，和云服務器中數據是否及時更新沒有考慮。文獻[18]雖然在增強方案中提到支持一對多模型，但沒有對如何進行授權和用戶上傳搜索信息進行說明。文獻[20]中只有增加和刪除操作，并沒有考慮對原始數據的更新。

由于文獻[11-12]是一般化驗證方案，其中并沒有包含具體完整的可搜索加密方案，所以無法知道其是否支持前向與后向安全。文獻[18]方案沒有涉及到數據更新，所以也就無法定義其是否支持前向與后向安全。文獻[18，20]方案中，均不支持前向與后向安全。雖然文獻[22]考慮了前向與后向安全，但由于其陷門構造使用公鑰加密，沒有很好的解決授權問題。

從功能上分析，該方案不僅實現了一對多模型下授權訪問功能，而且對于云服務器不誠實更新數據情況，用戶可以進行本地驗證。在保證以上功能的同時，也支持前向與后向安全，大大提高了數據的安全性。

5.2 實驗分析對比

該方案實驗環境為64 bit windows 操作系統，Intel?Core(TM) i5-4570 CPU 3.20 GHz、內存16 GB。文中使用Enron Email數據集作為原始數據集，提取出6 560篇文檔作為測試數據集。實驗中，智能合約使用solidity語言，與智能合約交互語言為javascript語言。數據擁有者方面使用python對數據集提取關鍵字并生成索引，利用160-bit ECC對授權信息進行加密。智能合約部署到本地測試網絡Ganache對其進行性能測試。實驗中，安全哈希函數基于SHA256構造，偽隨機置換函數使用AES (CBC模式，128-bit密鑰)，并且MAC生成算法采用HMAC-SHA256，加密文檔集合則使用AES對稱加密算法。

由于文獻[11-12]并不是具體的可驗證搜索加密方案，且實驗平臺不是基于區塊鏈，所以選擇基于智能合約且與近兩年的文獻[18，20，22]進行了對比。實驗從3個方面進行對比：索引生成時間、搜索時間和驗證時間。在每一個數量級進行50次反復試驗，求出時間開銷的平均值，保證實驗結果的準確性。

圖4 索引加密時間

首先，在索引加密的時間成本方面，將筆者提出的方案與其他方案進行了比較。如圖4所示，索引加密時間隨著關鍵字數量的增加而增加。由于筆者提出的方案與其他方案相比增加了驗證功能，因此有必要在索引加密階段添加AMAC的計算和加密。其次，由于圖4僅顯示了文獻[18，20]中的方案初始數據集上傳部分，而本方案中將初始數據集也看作一次數據更新，并增加了前向和后向安全。綜合上述原因，本方案在索引加密階段會比文獻[18，20]中的方案計算代價略高。隨著關鍵字數量的增加，筆者提出方案的索引加密時間比文獻[22]中的方案更加高效。造成這種差異的主要原因是文獻[22]中的方案沒有使用打包操作，并且所有索引都需要加密，這將導致巨大的開銷。

如圖5所示，隨著匹配索引數量的增加，文中方案的搜索算法的時間成本比其他方案更低。此結果的主要原因是，文獻[18，20]方案在執行搜索操作時，需要對原始數據索引和更新數據索引分別進行搜索，搜索結果中的每個文檔標識符還需要依次進行額外的哈希運算，檢查其是否刪除從而返回最終結果。由于文獻[22]中每條索引只對應一個文檔標識符，所以在搜索過程中需要對所有索引進行搜索，而本方案只需要對打包索引進行搜索即可，顯著提高了搜索效率。

由于文獻[18，20，22]中并沒有對返回結果的驗證，所以將本方案與文獻[11-12]進行驗證時間方面的對比。如圖6所示，文中方案在驗證時間開銷明顯低于其他方案，主要原因在于，文中方案只需要本地進行一次哈希運算和異或運算即可。對于文獻[12]來說，除了對返回結果進行哈希運算外，還需要對返回路徑上的節點進行運算，進而對Merkle Hash Trees的根節點進行驗證。文獻[11]除了對Merkle Patricia Tree的根節點進行驗證外，還需要對認證標志進行新鮮度驗證。并且文獻[11]中的方案在實際應用中，會存在百毫秒級別的驗證延遲，這種延遲主要是由更新間隔造成的，對于用戶體驗并不是很好。

圖5 搜索時間

圖6 驗證時間

6 結束語

在可搜索加密的基礎上，筆者將區塊鏈與可搜索加密相結合，提出了一種基于區塊鏈的動態可驗證密文檢索方案。文中方案主要應用于需要確保數據絕對安全的私有云環境，例如機密機構的數據庫。通過以太坊賬戶的特性，可以實現一對多環境下的授權訪問控制。依靠以太坊的特性，解決了惡意服務器返回結果的正確性問題。并且針對云服務器不更新數據問題，文中方案通過引入聚合消息認證碼技術，創新性地解決了數據更新時對返回結果的驗證。文中方案還支持前向和后向安全，確保了數據更新時不會泄露任何隱私。同時針對方案中索引生成、檢索和驗證3個方面進行了實驗測試。測試結果顯示本方案具有較高的效率。

接下來的工作將會針對可搜索加密如何在區塊鏈環境下，實現多關鍵字和關鍵字排序等更加靈活的查詢方式，讓用戶得到更加準確的返回結果。