一種支持動(dòng)態(tài)可驗(yàn)證的密文檢索方案

杜瑞忠，王 一，田俊峰

(1.河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北 保定 071002；2.河北大學(xué) 河北省高可信信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002)

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

可搜索加密[1-4]是一種支持用戶在密文中進(jìn)行關(guān)鍵字檢索的新技術(shù)，主要解決云存儲(chǔ)環(huán)境下如何利用不可信的服務(wù)器實(shí)現(xiàn)基于關(guān)鍵字的安全搜索，使用戶能夠?qū)⒓用艿臄?shù)據(jù)存儲(chǔ)到云中，并通過密文域執(zhí)行關(guān)鍵字搜索，有選擇地從云中檢索感興趣的文檔，為用戶節(jié)省了大量開銷。然而以上方案全是假定服務(wù)器是誠(chéng)實(shí)、好奇的實(shí)體，但在現(xiàn)實(shí)世界中，云服務(wù)器可能因?yàn)橥獠抗艋蛘邇?nèi)部配置錯(cuò)誤，返回錯(cuò)誤或者不完整結(jié)果，從而對(duì)用戶進(jìn)行欺騙?？紤]到以上問題，可驗(yàn)證搜索加密方案[5-9]進(jìn)入到學(xué)者視野，這些方案使得用戶可以對(duì)結(jié)果進(jìn)行驗(yàn)證，進(jìn)而判斷服務(wù)器是否為惡意服務(wù)器。

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

在動(dòng)態(tài)可搜索加密方案中，前向安全和后向安全是兩個(gè)重要的安全屬性，可以確保在更新數(shù)據(jù)時(shí)不會(huì)發(fā)生信息泄漏。文獻(xiàn)[13]首先提出了關(guān)于前向安全和后向安全的概念。隨后，學(xué)者們?cè)诰哂星跋虬踩乃阉骷用芊桨竅14]的基礎(chǔ)之上，設(shè)計(jì)了一種可驗(yàn)證的前向隱私搜索加密方案[15]。后向安全作為動(dòng)態(tài)搜索加密方案中一個(gè)重要的安全屬性，在文獻(xiàn)[16]中首次被提出，并在文中對(duì)后向安全給出了形式化的定義。但是，以上方案不能很好地解決一對(duì)多模型下的訪問控制問題。

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

基于以上問題，筆者提出了一種基于區(qū)塊鏈的動(dòng)態(tài)可驗(yàn)證密文檢索方案，旨在解決動(dòng)態(tài)環(huán)境下可搜索加密的數(shù)據(jù)隱私和結(jié)果正確性問題。主要貢獻(xiàn)如下：

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

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

(3) 將該方案部署到本地私有網(wǎng)絡(luò)(Ganache)中，對(duì)大量真實(shí)數(shù)據(jù)集進(jìn)行分梯度實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果分析表明，該方案在索引生成、搜索效率以及驗(yàn)證時(shí)間具有一定優(yōu)勢(shì)。

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

1.1 區(qū)塊鏈及相關(guān)知識(shí)

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

智能合約是部署在區(qū)塊鏈上的一些特殊腳本代碼，即使其創(chuàng)建者也無法進(jìn)行修改，并且可以根據(jù)內(nèi)容自動(dòng)執(zhí)行。發(fā)布智能合本質(zhì)上就是將一筆交易發(fā)布到區(qū)塊鏈中，區(qū)塊鏈中所有礦工會(huì)進(jìn)行工作，當(dāng)挖出包含此智能合約的區(qū)塊時(shí)，區(qū)塊鏈中的所有節(jié)點(diǎn)都會(huì)保存此智能合約。而礦工也會(huì)得到獎(jiǎng)勵(lì)，獎(jiǎng)勵(lì)由gaslimit×gasprice決定，其中，gaslimit為發(fā)送方可以支出的最多燃料，gasprice為發(fā)送方為每個(gè)燃料支付的費(fèi)用。由于每個(gè)節(jié)點(diǎn)都會(huì)存儲(chǔ)智能合約，所有存儲(chǔ)的數(shù)據(jù)和智能合約的已執(zhí)行計(jì)算對(duì)任何用戶都是透明且不可篡改的。對(duì)于所有需要在可信環(huán)境下進(jìn)行的操作，理論上都可以使用智能合約來執(zhí)行。

1.2 外部賬戶

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

1.3 聚合消息認(rèn)證碼

由于以太坊中g(shù)aslimit的限制，普通消息認(rèn)證碼的存儲(chǔ)開銷太大且效率低下，并不適用于智能合約。因此，可以通過減少M(fèi)AC數(shù)量的方式，降低智能合約中消息認(rèn)證碼相關(guān)計(jì)算量，從而實(shí)現(xiàn)提高搜索效率和避免超過gaslimit的目的?；谝陨纤枷?，聚合消息認(rèn)證碼(Aggregate MACs，AMAC)被引入到文中。舉例而言，給定兩個(gè)數(shù)據(jù)消息認(rèn)證碼對(duì)(m1，δ1)和(m2，δ2)，其中，δi=Auth(K，mi)。將兩個(gè)消息認(rèn)證碼進(jìn)行異或操作，得到聚合消息認(rèn)證碼，

φ=δ1⊕δ2。

(1)

當(dāng)對(duì)這兩條數(shù)據(jù)(m1，m2)進(jìn)行驗(yàn)證時(shí)，只需對(duì)φ進(jìn)行驗(yàn)證即可。

文中符號(hào)說明如表1所示

表1 符號(hào)定義

2 系統(tǒng)模型

2.1 系統(tǒng)簡(jiǎn)介

圖1 方案模型圖

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

(1) 數(shù)據(jù)擁有者：主要負(fù)責(zé)將明文數(shù)據(jù)加密，并提取加密索引和AMAC。將密文數(shù)據(jù)上傳到云服務(wù)器，加密索引和AMAC上傳到智能合約中，用戶請(qǐng)求搜索時(shí)，對(duì)數(shù)據(jù)用戶進(jìn)行授權(quán)并發(fā)送授權(quán)信息。

(2) 云服務(wù)器：主要負(fù)責(zé)密文數(shù)據(jù)的存儲(chǔ)，并根據(jù)數(shù)據(jù)用戶上傳的加密索引集合下發(fā)密文數(shù)據(jù)集合。

(3) 區(qū)塊鏈系統(tǒng)：主要負(fù)責(zé)接收并存儲(chǔ)數(shù)據(jù)擁有者發(fā)送過來的加密索引以及AMAC，接收數(shù)據(jù)用戶上傳的陷門，并根據(jù)陷門進(jìn)行查詢，將查詢結(jié)果下發(fā)到數(shù)據(jù)用戶。

(4) 數(shù)據(jù)用戶：向數(shù)據(jù)擁有者請(qǐng)求授權(quán)后得到授權(quán)信息，并將授權(quán)信息上傳到區(qū)塊鏈中。根據(jù)查詢結(jié)果，請(qǐng)求云服務(wù)器下發(fā)密文數(shù)據(jù)，最后進(jìn)行本地驗(yàn)證。

2.2 安全目標(biāo)

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

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

(3) 可驗(yàn)證性：由于惡意云服務(wù)器可能返回錯(cuò)誤結(jié)果，所以需要保證返回結(jié)果的可驗(yàn)證性?？沈?yàn)證性意味著當(dāng)返回的結(jié)果是錯(cuò)誤時(shí)，該結(jié)果以及對(duì)應(yīng)的證據(jù)無法通過驗(yàn)證。

2.3 威脅模型

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

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

(2) 數(shù)據(jù)擁有者會(huì)更新某篇文檔的內(nèi)容，但云服務(wù)器并沒有執(zhí)行更新操作。當(dāng)數(shù)據(jù)用戶搜索此文檔中包含的關(guān)鍵字時(shí)，云服務(wù)器將更新之前的文檔返回給數(shù)據(jù)用戶。

(3) 云服務(wù)器并未按照數(shù)據(jù)擁有者的要求刪除某篇文檔。當(dāng)數(shù)據(jù)用戶搜索此文檔中包含的關(guān)鍵字時(shí)，云服務(wù)器將本應(yīng)刪除的文檔返回給了數(shù)據(jù)用戶。

3 系統(tǒng)描述

3.1 初始化階段

Setup(λ)→Para，SK：輸入安全參數(shù)λ，生成公開參數(shù)和本地參數(shù)。安全哈希函數(shù)包含以下函數(shù)(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；隨后生成偽隨機(jī)置換函數(shù)P：{0，1}λ×{0，1}λ→{0，1}λ(P-1為P的反函數(shù))。最后，廣播公開參數(shù)Para={h1，h2，h3，h4，h5，H1，H2，H3，P，P-1}，數(shù)據(jù)擁有者初始化一個(gè)映射空集Map，將本地參數(shù)SK={G，Map}保存在本地。

3.2 更新數(shù)據(jù)階段

如圖2所示，為了節(jié)約存儲(chǔ)成本和保護(hù)索引中文檔標(biāo)識(shí)符數(shù)量，筆者采用了打包技術(shù)，將DB(wi)addition和DB(wi)deletion中的文檔標(biāo)識(shí)符打包進(jìn)塊。

圖2 打包索引圖

(2)

算法1數(shù)據(jù)更新算法。

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

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

① For eachwi∈W

③ if Map[wi]=⊥ then

⑤ end if

⑨ 數(shù)據(jù)擁有者更新保存在本地的映射圖Map；

在本算法中，c為版本指針，用來指示關(guān)鍵字wi的更新狀態(tài)次數(shù)。從表面來看，更新的數(shù)據(jù)以鍵值的方式存儲(chǔ)在區(qū)塊鏈中，并且各自密文之間彼此無關(guān)。但是包含相同關(guān)鍵字的密文之間具有隱藏關(guān)系，如圖3所示。其中最近更新狀態(tài)依次指向之前的更新狀態(tài)，并且每個(gè)更新狀態(tài)還對(duì)應(yīng)著本次全部的更新索引。

圖3 隱藏關(guān)系圖

3.3 授權(quán)階段

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

3.4 搜索階段

Search(Para，Twi，EDB)→RI，α：輸入公共參數(shù)Para，數(shù)據(jù)用戶調(diào)用智能合約并發(fā)送陷門Twi，隨后智能合約執(zhí)行算法2。

算法2數(shù)據(jù)搜索算法。

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

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

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

② keywi=H2(Twi)；

③ valwi=EDB[keywi]；

⑥ While EDB[keylen]≠⊥ do

⑦ vallen=EDB[keylen]；

⑨ Forj=1 to m do

經(jīng)過搜索算法過程，智能合約將RI和α存儲(chǔ)在日志中并發(fā)布出去。

3.5 解密階段

3.6 驗(yàn)證階段

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

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

(3)

如果α+=α，則輸出1，代表通過驗(yàn)證環(huán)節(jié)，密文文檔集合正確并進(jìn)行解密；否則輸出0，意味著沒有通過驗(yàn)證環(huán)節(jié)。

4 安全分析

4.1 適應(yīng)安全

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

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

(4)

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

只要文中方案Ⅱ?qū)λ泄粽叽嬖谝韵鹿剑纯蓾M足自適應(yīng)安全定義。

(5)

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

定理1如果P是一個(gè)安全的偽隨機(jī)置換函數(shù)，并且所有安全的哈希函數(shù)具有抗沖突性質(zhì)，那么文中的方案Ⅱ是自適應(yīng)安全的。

在游戲G2中，維護(hù)一個(gè)列表SL，其中，SL[w，c]=stc，而不是通過P(Kc，stc-1)生成stc。在更新環(huán)節(jié)，當(dāng)需要stc時(shí)，游戲隨機(jī)選取一個(gè)字符串stc={0，1}λ。因?yàn)閭坞S機(jī)置換函數(shù)是安全的，所以非常簡(jiǎn)單得出G2和G1是不可區(qū)分的。

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

(6)

在游戲G3中，將所有安全哈希函數(shù)轉(zhuǎn)化為隨機(jī)預(yù)言機(jī)，并維護(hù)一個(gè)列表用來存儲(chǔ)每個(gè)預(yù)言機(jī)的輸入與輸出。舉例而言，給定一個(gè)輸入x，隨機(jī)預(yù)言機(jī)隨機(jī)選取一個(gè)字符串y=h1(x)作為輸出，然后將其插入到列表h1-L。因?yàn)楣：瘮?shù)具有抗沖突性，所以得出G3和G2是無法區(qū)分的。

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

(7)

在游戲G4中，在更新環(huán)節(jié)并沒有使用G(wi，c)生成Tagwi，而是采用一個(gè)隨機(jī)字符串Tagwi={0，1}λ。同時(shí)游戲需要維護(hù)一個(gè)列表，用來響應(yīng)攻擊者A的授權(quán)查詢，其中列表存儲(chǔ)的為(wi，Tagwi，c)。如果攻擊者可以區(qū)分，則可以得出

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

(8)

其中，Bad表示攻擊者A可以區(qū)分隨機(jī)字符串和Tagwi的概率，這個(gè)概率為2-λ+negl(λ)。攻擊者最多進(jìn)行次q1=poly(λ)猜測(cè)，其中，poly( )不是特性多項(xiàng)式。隨后，通過以上公式可以得出Pr[Bad]≤q12-λ+q1negl(λ)?？梢钥闯?，概率為可忽略的函數(shù)，因此得出G4和G3在計(jì)算上是不可區(qū)分的。

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

(9)

通過以上分析，可以得出

(10)

因?yàn)镻r[Bad]是可以忽略的函數(shù)，所以筆者提出的方案滿足自適應(yīng)安全。

4.2 前向安全

4.3 后向安全

4.4 可驗(yàn)證性

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

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

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

攻擊者A可以找到一個(gè)元組{C*，w，δ*}，并非通過消息認(rèn)證碼生成公式δi=Auth(fi，Km)輸出的，但是可以通過驗(yàn)證公式Verify(C*，w，Km，α*)=1。定義如果攻擊者A成功地完成本次實(shí)驗(yàn)，則等價(jià)于可以偽造一個(gè)消息認(rèn)證碼通過驗(yàn)證，這種通過的概率定義可以表示為Pr[ForgeA Ⅱ]。因?yàn)椋痉桨钢邢⒄J(rèn)證碼生成函數(shù)是安全的，所以攻擊者可以偽造消息認(rèn)證碼通過驗(yàn)證的概率為可以忽略的。根據(jù)以上等式可以得出

(11)

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

5 性能分析

5.1 功能對(duì)比

將文中方案與上述文獻(xiàn)對(duì)比，如表2中所示。

表2 功能對(duì)比

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

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

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

從功能上分析，該方案不僅實(shí)現(xiàn)了一對(duì)多模型下授權(quán)訪問功能，而且對(duì)于云服務(wù)器不誠(chéng)實(shí)更新數(shù)據(jù)情況，用戶可以進(jìn)行本地驗(yàn)證。在保證以上功能的同時(shí)，也支持前向與后向安全，大大提高了數(shù)據(jù)的安全性。

5.2 實(shí)驗(yàn)分析對(duì)比

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

由于文獻(xiàn)[11-12]并不是具體的可驗(yàn)證搜索加密方案，且實(shí)驗(yàn)平臺(tái)不是基于區(qū)塊鏈，所以選擇基于智能合約且與近兩年的文獻(xiàn)[18，20，22]進(jìn)行了對(duì)比。實(shí)驗(yàn)從3個(gè)方面進(jìn)行對(duì)比：索引生成時(shí)間、搜索時(shí)間和驗(yàn)證時(shí)間。在每一個(gè)數(shù)量級(jí)進(jìn)行50次反復(fù)試驗(yàn)，求出時(shí)間開銷的平均值，保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。

圖4 索引加密時(shí)間

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

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

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

圖5 搜索時(shí)間

圖6 驗(yàn)證時(shí)間

6 結(jié)束語

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

接下來的工作將會(huì)針對(duì)可搜索加密如何在區(qū)塊鏈環(huán)境下，實(shí)現(xiàn)多關(guān)鍵字和關(guān)鍵字排序等更加靈活的查詢方式，讓用戶得到更加準(zhǔn)確的返回結(jié)果。