基于區(qū)塊鏈實現(xiàn)可搜索加密公平性的研究

王 楠（北方工業(yè)大學 信息學院，北京 100144）

0 引言

在這個信息飛速傳遞的時代，數(shù)據(jù)無時無刻不在交互傳輸，數(shù)據(jù)信息傳遞到各個平臺的服務器上，其中也包含一些敏感的數(shù)據(jù)。為了降低資源受限用戶的存儲和管理負擔，這些數(shù)據(jù)大多被存儲在云服務器中，一旦存在惡意的云服務器會對數(shù)據(jù)進行篡改、刪除或出售給其他服務器，造成用戶數(shù)據(jù)泄露從而帶來損失。用戶擔心數(shù)據(jù)泄露，會在上傳數(shù)據(jù)前進行加密，但加密后的數(shù)據(jù)需要解密才能獲取，需要將全部密文轉(zhuǎn)化為明文，然后用戶在全部明文中查找需求的明文。實際場景中，絕大多數(shù)的用戶執(zhí)行解密操作時只想獲取其中的部分內(nèi)容，但是在大量的加密數(shù)據(jù)中想要檢索到自己想要的那一部分明文實現(xiàn)起來非常困難，大大降低了檢索的效率。所以，雖然有很多成熟的加密算法，但一般加密算法加密后再上傳會給后續(xù)檢索帶來很大困擾。

此時需要一種加密算法，加密復雜度高，不易被破解，以保障數(shù)據(jù)安全。對于加密者來說，能對密文直接進行檢索。在此需求下，可搜索加密技術應運而生。最原始的可搜索加密的模型，包括數(shù)據(jù)擁有者、云服務器和用戶三部分，它允許數(shù)據(jù)擁有者以一種私密的方式把自己的數(shù)據(jù)外包給云端，同時保持數(shù)據(jù)的可搜索的能力，即數(shù)據(jù)擁有者加密明文后，將密文上傳到云服務器，云服務器保管這些數(shù)據(jù)，并且提供搜索服務。其他用戶訪問時，根據(jù)密文不能得到任何關于明文的相關信息，保障了信息的安全。

但隨著技術的普及和需求的不斷提升，可搜索加密也暴露出一些問題：用戶需要在服務器提供搜索服務前支付費用，一旦惡意的服務器返回錯誤的數(shù)據(jù)，用戶無法索賠。在某些情況下，用戶也可能存在惡意，否認服務器發(fā)來的正確結(jié)果，或故意發(fā)現(xiàn)錯誤令牌造成服務器無法檢索到正確結(jié)果，此情況概率很小，對于用戶來說沒有實質(zhì)收益。因此，在本方案中默認用戶是誠實的，只考慮服務器的惡意問題。將區(qū)塊鏈技術引入系統(tǒng)，利用區(qū)塊鏈系統(tǒng)的不可篡改、可追蹤等優(yōu)點，解決了用戶公平性的問題，避免上述安全事件的發(fā)生。

1 基礎技術

1.1 可搜索加密技術

2000年，song等人首次提出了可搜索加密（Searchable Encryption，SE）的思想[1]，并在此基礎上加以實現(xiàn)。用戶可以通過關鍵詞在密文中進行檢索，該技術通過加密明文的關鍵詞生成搜索憑證即訪問令牌，服務器通過令牌獲得與關鍵詞相對應的密文，返還給用戶。

根據(jù)加密類型的不同，可搜索加密可分為對稱可搜索加密和非對稱可搜索加密，非對稱可搜索加密2004年由Boneh等首次提出[2]，利用橢圓曲線算法實現(xiàn)，此加密方式的加密密鑰和解密密鑰不同，導致了算法更加復雜，解密效率低。相比之下，對稱可搜索加密的優(yōu)勢得以體現(xiàn)[3]，相同的密鑰提升了加密解密的效率。最原始的對稱可搜索加密技術的系統(tǒng)模型大體如圖1所示，包括數(shù)據(jù)擁有者、云服務器和用戶3部分[4-6]。功能的實現(xiàn)通過以下3個步驟，步驟一：數(shù)據(jù)擁有者擁有文件集D，通過密鑰K將其加密為密文C，同時生成索引I，將密文C和索引I發(fā)送給云服務器保存，將密鑰K發(fā)送給用戶。步驟二：用戶生成訪問令牌，把想要搜索的關鍵字W通過密鑰K加密，轉(zhuǎn)換為搜索令牌Tw，并發(fā)送令牌給服務器，同時支付費用。步驟三：服務器結(jié)合C、Tw、I生成對應關鍵字W的密文C’，返還給用戶，最后用戶在本地用密鑰K解密C’，獲取想要的明文D'。如果該系統(tǒng)中，除了被授權的用戶，其他任何人不能通過密文得到明文信息，就可以說該SSE算法是安全的[7]。

圖1 SSE系統(tǒng)模型圖Fig.1 SSE System model diagram

1.2 區(qū)塊鏈技術和智能合約技術

區(qū)塊鏈技術源于2008年“中本聰”在密碼學郵件組發(fā)表的名為《比特幣：一種點對點電子現(xiàn)金系統(tǒng)》的論文中[8]，之后成為數(shù)字加密貨幣體系的核心技術。應用區(qū)塊鏈技術結(jié)合可搜索加密是因為以下兩點：一，區(qū)塊鏈系統(tǒng)是由大量的分布式共識節(jié)點組成的系統(tǒng)，沒有中心節(jié)點，是由各個節(jié)點共同維護的系統(tǒng)，避免了強大惡意節(jié)點壟斷的情況；二，智能合約的應用，依靠合約的執(zhí)行來實現(xiàn)交易認證[9]。區(qū)塊鏈上所有交易均完全公開，并且在加入到區(qū)塊鏈前經(jīng)過全部節(jié)點的驗證。并且，時間戳機制使每一筆交易都有極強的可追溯性[10]。

智能合約在本系統(tǒng)中起到認證作用，智能合約的概念最早于1994年由美國的NickSzabo提出[11]，本質(zhì)是一系列計算機交易協(xié)議，在無需第三方的環(huán)境中執(zhí)行合約條款。智能合約的可編程性給區(qū)塊鏈技術提供了更多操作空間，在區(qū)塊鏈系統(tǒng)中智能合約能更好地發(fā)揮功能[12]。目前，智能合約技術被廣泛應用在區(qū)塊鏈中[13]。

1.3 哈希算法

哈希加密算法有著非常好的性質(zhì)，首先，哈希加密后密文等長，避免了攻擊者由密文長度獲取關于明文長度的相關信息；其次，哈希函數(shù)是典型的單向不可逆函數(shù)，例如y=f(x)，已知y的值，想要獲取x的值非常困難；最后，哈希函數(shù)的抗碰撞性非常適合對交易結(jié)果進行驗證。例如x1≠x2，則很難找到f(x1)=f(x2)，即難找到兩個不同的關鍵字對應相同的散列值[14,15]。

1.4 主要工作

圖2 改進后的系統(tǒng)模型Fig.2 Improved system model

解決了可搜索加密時交易雙方不公平的問題，方法是雙方支付一定數(shù)量的押金，由區(qū)塊鏈系統(tǒng)進行檢測，一旦服務器存在惡意，包括返回錯誤搜索結(jié)果或不完整的搜索結(jié)果，在區(qū)塊鏈系統(tǒng)檢測后將會被扣留押金。區(qū)塊鏈的引入完善了可搜索加密的安全體系，提升了系統(tǒng)安全性，同時可以提供對結(jié)果的認證，大大減少了用戶的計算量，本系統(tǒng)是用Python語言實現(xiàn)的。

2 系統(tǒng)模型

加入?yún)^(qū)塊鏈系統(tǒng)后，本系統(tǒng)模型包含4部分，即：數(shù)據(jù)擁有者、服務器、用戶和區(qū)塊鏈系統(tǒng)。各個部分之間的交互關系及流程如圖2所示。

改進后的具體步驟：

第一步：數(shù)據(jù)擁有者將明文數(shù)據(jù)D加密為密文C，同時生成索引I，將對應的私鑰K發(fā)送給用戶，將密文C和索引I發(fā)送給云服務器。

第二步：用戶給出想要搜索的關鍵詞w，并加密該關鍵詞為令牌Tw，并將令牌Tw發(fā)送給區(qū)塊鏈系統(tǒng)，同時向區(qū)塊鏈系統(tǒng)支付一定數(shù)量的押金，這是保障后續(xù)交易公平的必要準備。

第三步：云服務器向區(qū)塊鏈系統(tǒng)發(fā)送交易請求，支付一定數(shù)量的押金，支付押金后，從區(qū)塊鏈系統(tǒng)中獲得搜索令牌Tw。

第四步：云服務器得到Tw后，可以結(jié)合數(shù)據(jù)擁有者發(fā)送的C、I在本地計算出關鍵詞對應的密文結(jié)果C'。

第五步：云服務器將搜索結(jié)果C'返回給區(qū)塊鏈系統(tǒng)，經(jīng)區(qū)塊鏈檢驗后，判定該服務器是否為惡意，則該服務器支付的預定金不予退回。用戶支付的押金將被退回（本次交易終止）。

第六步：如果服務器誠實且提供正確數(shù)據(jù)信息，區(qū)塊鏈系統(tǒng)檢驗后，將正確結(jié)果返還給用戶，用戶支付服務費Tp，區(qū)塊鏈系統(tǒng)將服務費Tp轉(zhuǎn)給服務器，同時退還雙方押金。第七步：用戶在本地解密出明文D'。

表1 符號及其含義Table 1 Symbols and their meanings

3 實現(xiàn)方案

3.1 符號含義

本方案所涉及到的符號及其含義在表1中列出。

3.2 方案簡介

本系統(tǒng)主要功能由9個算法構(gòu)成并實現(xiàn)，包括（Setup,E nc,Token,Prepare,Appoint,Search,Verification,Pay,Dec）。

Setup(1k)→K以k為安全因子，生成密鑰列K。

Enc(K,D)→(I,C)將密鑰列K和文件數(shù)據(jù)集D作為輸入，輸出密文集C和索引I。

Token(K,w)→(Tw)將密鑰列K、關鍵詞集合W作為輸入，生成搜索令牌Tw。

Prepare(Tu,Tw)→null:用戶向區(qū)塊鏈系統(tǒng)支付押金Tu，防止用戶中途退出，用戶支付押金時將Tw也發(fā)送給服務器，用于解密及驗證。

Appoint(Ts)→(Tw1)由服務器執(zhí)行，發(fā)送請求到區(qū)塊鏈，請求獲取Tw1（Tw1是令牌Tw的一部分），由于服務器可以根據(jù)Tw1獲取用戶的信息，因而發(fā)送請求時需要向區(qū)塊鏈系統(tǒng)支付押金Ts，支付后獲得部分令牌Tw1。

Search(Tw1,I)→(Cw,MACw)服務器得到Tw1后，結(jié)合索引I進行搜索，輸出對應的密文Cw，將數(shù)據(jù)擁有者發(fā)送密文C時附帶的帶密鑰哈希MACw和Cw一并發(fā)給區(qū)塊鏈系統(tǒng)。

Verification(t3w,Cw,MACw)→Ture/False判別算法，區(qū)塊鏈系統(tǒng)驗證服務器是否為惡意，輸入Tw-Tw1和Cw，計算MACw'，驗證MACw'是否等于MACw。若相等，輸出Ture，否則輸出False，交易中止。

Pay(Tp)→Ci驗證服務器非惡意后，區(qū)塊鏈系統(tǒng)將密文Ci返還給用戶，用戶支付費用Tp給區(qū)塊鏈系統(tǒng)，同時退還用戶押金Tu和服務器押金Ts。

Dec(Ci ,K)→Di用戶在本地輸入密鑰列K和得到的密文Cw，輸出對應關鍵詞W的明文Di。

3.3 具體實現(xiàn)

數(shù)據(jù)擁有者主要應用到偽隨機函數(shù)，包括F1,F2,F3，表示為{0,1}k×{0,1}*→{0,1}k。一個哈希函數(shù)H：{0,1}k→{0,1}m。

1）Setup：生成隨機密鑰列K1,K2,K3,{0,1}k→K1,K2,K3。

2）Enc：通過使用密鑰K1,數(shù)據(jù)擁有者加密明文D={D1,D2,…,Dn}為密文文件，即C={C1,C2,…,Cn}Ci=ε.Enc(K1,Ci)，之后生成密文集合C。令W={w1,w2,…,wn}為明文集D的關鍵詞集合，其中，m表示關鍵詞的數(shù)量，對于每一個關鍵詞Wi(1≤i≤m)，選擇初始化為空、大小為n的數(shù)組DB(wi)接收。如果文件集中第j個文件包含關鍵詞wi，那么DB(wi)[j]=1，否則DB(wi)[j]=0。

數(shù)據(jù)擁有者把(t1wi,ewi,MACwi)放到索引I中，將C,I上傳到云服務器。

3）Token：數(shù)據(jù)擁有者在步驟2）發(fā)送C,I的同時，會將K1,K2,K3發(fā)送給用戶，用戶根據(jù)想要搜索的關鍵詞w，生成令牌，進行如下計算：

4）Prepare：用戶將步驟3）中生成的t1w,t2w,t3w,發(fā)送給區(qū)塊鏈系統(tǒng)，同時為了避免用戶中途退出，需要用戶支付押金Tu。為了避免服務器的惡意行為，后續(xù)需要服務器支付押金。

5）Appoint：服務器向區(qū)塊鏈發(fā)送請求，想要獲得t1w和t2w，由于服務器可以通過t1w和t2w獲取數(shù)據(jù)信息，因而需要服務器支付押金。服務器支付押金Ts，區(qū)塊鏈系統(tǒng)發(fā)送t1w和t2w給服務器，t3w由區(qū)塊鏈系統(tǒng)保留。

請求算法如下：

Algorithm:Appoint Input: Ts Output:null if blockchain system get Ts then return(t1 w, t2 w)else return Tu to server

6）Search：服務器通過t1w，t2w結(jié)合數(shù)據(jù)擁有者發(fā)來的(t1wi,ewi,MACwi)計算：

I=(t1wi,ewi,MACwi)，將t1w作為密鑰，解密出ewi,MACwi中對應關鍵詞w的ew和MACw。

服務器繼續(xù)解密，將t2w作為密鑰解密ew得到DB(w)，DB(w)=θ.Dec(t2w,ew)。若DB(wi)[j]=1將對應的文件Cj放入Cw集中，將Cw和MACw發(fā)送給區(qū)塊鏈系統(tǒng)。

搜索算法如下：

Algorithm:Search find ew from ewi DB(w)=θ.Dec(t2 w, ew)for j in DB(w) do if DB(w)[j]=1 Cw=Cw∪Cj Send Cw MACw to Blockchain end

7）Verification：驗證交易的可靠性，判別服務器是否有惡意。若服務器返回正確結(jié)果，則用戶支付服務費，交易正常進行；若服務器有惡意，則扣留服務器支付的押金。

用戶支付服務費Tp，區(qū)塊鏈系統(tǒng)根據(jù)t3w和Cw計算出MACw'：

驗證算法如下：

Algorithm:Verification Input:t3 w , Cw , MACw Output:true/false if MACw' ==MACw return true else return false

8）Pay：若步驟7）輸出True，區(qū)塊鏈系統(tǒng)將用戶支付的押金Tu和服務器支付的押金Ts返還給用戶和服務器，同時將服務費Tp給服務器；若步驟7）輸出False，區(qū)塊鏈系統(tǒng)將用戶支付的押金Tu和服務費Tp返還給用戶，不退還服務器支付的押金Ts，一并返還給用戶。

支付算法如下：

Algorithm:Pay if get.Verification()==true User send Tp to blockchain system Blockchain system send Ts +Tp to server Blockchain system send Tu to user else Blockchain system send Tu + Ts to user

9）Dec：若交易證明出現(xiàn)在區(qū)塊鏈中，則用戶可以從中獲得Ci，使用對稱密鑰K1進行解密，Di=ε.Dec(K1,Ci)(1≤i≤n)。

4 安全性及性能分析

4.1 安全性分析

4.1.1 數(shù)據(jù)擁有者的安全性

數(shù)據(jù)擁有者在本地加密數(shù)據(jù)，加密后上傳到服務器，加密過程獨立完成，以加密文檔的形式上傳給服務器，因此該系統(tǒng)的數(shù)據(jù)擁有者是安全的。

4.1.2 用戶的安全性和公平性

用戶將令牌上傳到區(qū)塊鏈，由區(qū)塊鏈保管，服務器支付押金后才能獲取相應的令牌，沒有泄露風險，保障了用戶數(shù)據(jù)的安全性；服務器得到令牌后，解密出相應密文，發(fā)送到區(qū)塊鏈系統(tǒng)，經(jīng)區(qū)塊鏈系統(tǒng)認證后，結(jié)果正確，用戶支付服務費，結(jié)果不正確，用戶不需要支付服務費，同時服務器支付的押金還會作為賠款支付給用戶，避免了用戶支付費用后得不到正確的搜索結(jié)果的情況，保障了用戶的交易公平性。

4.1.3 服務器的安全性和公平性

服務器得到數(shù)據(jù)擁有者發(fā)送的索引和密文以及區(qū)塊鏈系統(tǒng)發(fā)送的令牌，均是以加密形式呈現(xiàn)，服務器利用令牌進行搜索操作后，發(fā)送給區(qū)塊鏈的依然是密文形式的文件，保障了服務器的安全性；服務器執(zhí)行搜索操作后，只要返回正確的搜索結(jié)果，即可通過區(qū)塊鏈的驗證，得到相應的服務費，保障了服務器的交易公平性。

4.1.4 區(qū)塊鏈的安全性和公平性

區(qū)塊鏈中的每個區(qū)塊都有其對應的哈希值，會被下一個區(qū)塊引用和驗證，作為下一個區(qū)塊的預哈希。如果修改某個區(qū)塊的內(nèi)容，那么該區(qū)塊的哈希值一定會變，該區(qū)塊的下一個區(qū)塊已經(jīng)引用了該區(qū)塊的哈希值，這一原理使區(qū)塊鏈具有不可篡改性。交易過程中，區(qū)塊鏈主要起到保留押金、支付費用和交易驗證等功能，由于區(qū)塊鏈的高透明度，保障了交易的公平性。

4.1.5 加密算法安全性

數(shù)據(jù)擁有者在本地加密，采用偽隨機函數(shù)加密索引，采用AES高級加密標準加密文件，該加密算法密鑰長度達到128位，將明文分塊加密，保障了加密數(shù)據(jù)的安全性。

4.1.6 令牌安全性

用戶執(zhí)行關鍵詞加密時，采用和數(shù)據(jù)擁有者同樣的偽隨機函數(shù)進行加密，算法復雜度高，同樣的關鍵詞每次生成相同的令牌。除令牌外，服務器得不到與關鍵詞有關的任何信息，保障了搜索令牌的安全性。

4.2 性能分析

圖3 文件數(shù)量與密鑰生成時間的關系Fig.3 The relationship between the number of document and the key generation time

圖4 文件數(shù)量與建立索引時間的關系Fig.4 The relationship between the number of documents and the building index time

通過仿真實驗對系統(tǒng)性能進行評估，具體實驗環(huán)境為Intel Core i5-8500 CPU，64位操作系統(tǒng)，8.00G內(nèi)存，使用python語言進行編程，版本為Python3.8.0。

分別執(zhí)行了從100～1000個文件的加密，文件數(shù)量與密鑰生成時間的關系如圖3所示，文件數(shù)量與建立索引時間的關系如圖4所示，文件數(shù)量與執(zhí)行搜索時間的關系如圖5所示，文件數(shù)量與區(qū)塊鏈執(zhí)行驗證的時間如圖6所示。

綜合各項性能指標，本系統(tǒng)具有較好的性能。

5 結(jié)束語

本文提出了將區(qū)塊鏈系統(tǒng)引入可搜索加密模型的方案，主要針對惡意服務器，保障了交易雙方的公平性，通過認證算法判斷服務器是否存在惡意（包括返回錯誤搜索結(jié)果和不完整搜索結(jié)果等惡意行為）。引入押金機制確保了交易公平進行。區(qū)塊鏈系統(tǒng)保障了交易的可追溯和數(shù)據(jù)的不可篡改，提高系統(tǒng)的可靠性和透明度。對本方案的安全性和

圖5 文件數(shù)量與執(zhí)行搜索時間的關系Fig.5 The relationship between the number of documents and the search time

圖6 文件數(shù)量與區(qū)塊鏈驗證時間的關系Fig.6 The relationship between the number of documents and the blockchain verification time

性能進行了評估，證明方案是切實可行的，并具有很好的系統(tǒng)性能。