基于區塊鏈實現可搜索加密公平性的研究

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

0 引言

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

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

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

1 基礎技術

1.1 可搜索加密技術

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

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

圖1 SSE系統模型圖Fig.1 SSE System model diagram

1.2 區塊鏈技術和智能合約技術

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

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

1.3 哈希算法

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

1.4 主要工作

圖2 改進后的系統模型Fig.2 Improved system model

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

2 系統模型

加入區塊鏈系統后，本系統模型包含4部分，即：數據擁有者、服務器、用戶和區塊鏈系統。各個部分之間的交互關系及流程如圖2所示。

改進后的具體步驟：

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

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

第三步：云服務器向區塊鏈系統發送交易請求，支付一定數量的押金，支付押金后，從區塊鏈系統中獲得搜索令牌Tw。

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

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

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

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

3 實現方案

3.1 符號含義

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

3.2 方案簡介

本系統主要功能由9個算法構成并實現，包括（Setup,E nc,Token,Prepare,Appoint,Search,Verification,Pay,Dec）。

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

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

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

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

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

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

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

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

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

3.3 具體實現

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

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

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

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

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

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

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

請求算法如下：

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結合數據擁有者發來的(t1wi,ewi,MACwi)計算：

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

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

搜索算法如下：

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：驗證交易的可靠性，判別服務器是否有惡意。若服務器返回正確結果，則用戶支付服務費，交易正常進行；若服務器有惡意，則扣留服務器支付的押金。

用戶支付服務費Tp，區塊鏈系統根據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，區塊鏈系統將用戶支付的押金Tu和服務器支付的押金Ts返還給用戶和服務器，同時將服務費Tp給服務器；若步驟7）輸出False，區塊鏈系統將用戶支付的押金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：若交易證明出現在區塊鏈中，則用戶可以從中獲得Ci，使用對稱密鑰K1進行解密，Di=ε.Dec(K1,Ci)(1≤i≤n)。

4 安全性及性能分析

4.1 安全性分析

4.1.1 數據擁有者的安全性

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

4.1.2 用戶的安全性和公平性

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

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

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

4.1.4 區塊鏈的安全性和公平性

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

4.1.5 加密算法安全性

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

4.1.6 令牌安全性

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

4.2 性能分析

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

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

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

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

綜合各項性能指標，本系統具有較好的性能。

5 結束語

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

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

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

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