區塊鏈上支持多關鍵字檢索的可搜索加密方案 *

牛淑芬，王金風，王伯彬，陳敬民，杜小妮

(1.西北師范大學計算機科學與工程學院，甘肅 蘭州730070；2.西北師范大學數學與統計學院，甘肅 蘭州730070)

1 引言

為了保護數據的隱私，在將數據上傳到云服務器之前，需要對數據進行加密。為了解決密文上的檢索問題，Song等人[1]提出了對稱可搜索加密SSE(Symmetric Search Encryption)方案，該方案實現了基于密文的搜索功能，但需要對所有的文檔進行掃描，所以效率比較低。 為了提高對密文的搜索效率，Goh[2]根據關鍵字建立安全索引，云服務器通過匹配陷門和索引返回用戶所需要的密文文檔。Boneh等人[3]提出了帶關鍵字的公鑰可搜索加密PEKS(Public key Encryption with Keyword Search)方案，公鑰可搜索加密方案利用公鑰加密，僅有相應私鑰的用戶才能搜索加密數據，公鑰可搜索加密方案更適合多用戶的數據共享領域。

在某些應用場景中，用戶需要通過更多的關鍵詞來縮小搜索范圍，獲得更加精確的搜索結果。Golle等人[4]在GSW-1中最早提出了多關鍵詞檢索MKSE(Multi-Keyword Searchable Encryption)方案，在該方案中關鍵字陷門的大小與加密文檔的數量成線性關系。Kerschbaum[5]提出了非結構化文本的多關鍵詞可搜索加密方案，但每次搜索針對的是文件中的所有關鍵詞，而不是有選擇地進行。為了提高檢索結果的準確性，Cao等人[6]提出了可以捜索多個關鍵字的密文排序搜索方案，采用匹配的方式衡量了關鍵字與密文文件的相關度，返回滿足用戶搜索條件的密文范圍。Zhang等人[7]提出的方案實現了分離關鍵字搜索，Ballard等人[8]提出的連接關鍵字的可搜索加密方案實現了多關鍵字搜索的擴展功能。宋衍等人[9]提出了多關鍵字任意連接的可搜索加密方案，提高了多關鍵字搜索的靈活性。Xia等人[10]提出了支持動態更新的多關鍵詞排序搜索方案，通過采用貪婪深度優先搜索算法提高檢索結果的準確性。楊旸等人[11]提出了能實現數據隱私保護的多關鍵詞語義排序搜索方案，該方案不僅提高了數據搜索效率，而且返回了更能滿足用戶需求的搜索結果。Li等人[12]提出了在電子郵件系統中支持指定服務器身份驗證的可搜索加密方案，通過對電子郵件發件人在加密時對郵件進行身份驗證，加強了方案的安全性。

2008年，Nakamoto[13]提出了一個不涉及第三方交易記錄的比特幣平臺。區塊鏈[14]是一個基于比特幣協議維護不可篡改的數據記錄列表。區塊鏈本質上是一個P2P網絡系統中的分布式數據庫[15]，區塊鏈上的每一個區塊是使用密碼學的相關技術而產生的數據塊，交易創建后將被廣播到區塊鏈系統中；交易被礦工[16]驗證有效后將被記錄到臨時區塊；礦工使用工作量證明機制[17]計算出區塊后將此區塊向全網廣播，再將區塊鏈接在區塊鏈上。區塊鏈上的交易是公開透明且不可更改的。

在基于云存儲的可搜索加密方案中[18,19]，云服務器是半誠實的，即服務器可以任意改變搜索結果或不執行搜索任務。在理想情況下，如果服務器未返回搜索結果或返回錯誤結果給用戶時，用戶希望服務器能受到經濟處罰，以降低其可信度，用戶也能贖回自己承諾的手續費。通過引入區塊鏈技術[20,21]可以實現這一要求，而現有的方案[22,23]無法精確返回搜索結果，因此本文提出了區塊鏈上的多關鍵字可搜索加密方案。根據存儲數據的大小將其分為輕量級數據和重量級數據，本方案主要是針對輕量級數據的存儲及檢索作了描述，即嵌入一筆交易的數據可以存儲在一個區塊上，如果是重量級數據，需要對數據做分割處理后再將其以交易的形式存儲在區塊鏈上。

2 系統模型和安全模型

2.1 系統模型

區塊鏈上的可搜索加密主要有數據擁有者V、數據使用者U、搜索者Q和礦工M共4個參與者。假設數據擁有者有n個文檔D1,D2,…,Dn，為了保護文檔的隱私，數據擁有者將文檔加密成密文C1,C2,…,Cn，并將其以交易TX=(TX1,TX2,…,TXn)的形式上傳到區塊鏈上。為了提高文檔的搜索效率，數據擁有者V生成文檔對應的索引I并將索引嵌入交易Inx中，再將索引交易上傳到區塊鏈上。當數據使用者要檢索包含目標關鍵字W′的文檔時，數據使用者需要構造一筆包含關鍵字陷門TW′和索引交易Inx的查詢交易ask，再將查詢交易廣播到區塊鏈網絡中，由礦工將合法有效的交易上傳到區塊鏈上。通過搜索者Q返回包含陷門信息的交易get，數據使用者U在交易get中獲得密文Ci(1≤i≤n)，U將密文在本地用私鑰k解密，系統模型如圖1所示。

Figure 1 System model圖1 系統模型

2.2 方案形式化定義

(1)param←SetUp(1λ)：輸入安全系數λ，輸出系統參數param。

(2)k←KeyGen(param)：輸入系統參數param，輸出用戶密鑰k。

(3)(TX,Inx)←Enc(k,D,W)：數據擁有者運行該算法，對文檔集D={D1,…,Dn}和關鍵字W加密，并生成關鍵字索引I，將密文Ci(1≤i≤n)以交易TX的形式，索引I以交易Inx的形式上傳到區塊鏈上，將交易Inx廣播到P2P的區塊鏈網絡。

(4)TW′←Trapdoor(k,W′)：由數據使用者生成關鍵字搜索令牌，輸入密鑰k和目標關鍵字集W′ =(w′1,w′2,…,w′m}，輸出陷門TW′。

(5)(withdraw/get)←Search(TW′,Inxi)：由數據使用者U和搜索者Q運行的確定性算法，數據使用者U構建一筆包含TW′和Inx的交易ask，當數據使用者U執行該算法時，輸出交易withdraw，若搜索者Q執行該算法，則輸出交易get。

(6)D←Dec(k,get)：數據使用者U運行該算法，輸入密鑰k和交易get，輸出解密文檔D，數據使用者U從區塊鏈上獲得交易get并從該交易里獲得密文，然后對其用k解密。

2.3 安全模型

3 區塊鏈上多關鍵字的可搜索加密方案

區塊鏈上的多關鍵字可搜索加密主要有數據擁有者V、數據使用者U、搜索者Q和礦工M共4個參與者，方案的詳細過程描述如下：

(2)KeyGen(k)：假設每一個用戶X有一個秘密指數aX，其中0≤aX≤q-1，對應的公開值為bX=gaX，bX被包含在X的證書里并被可信的權威機構TA簽名。

③U計算出會話密鑰k=SVaUbVrU，其中U從Cert(V)中獲得了bV值。

④V計算會話密鑰k=SUaVbUrV，其中Di從Cert(U)中獲得了bU值。在會話結束時，V和U計算出相同的會話密鑰k=grVaU+rUaV。

(3)Enc(k,D,W)：數據擁有者V執行該算法，輸入密鑰k、文檔集D={D1,D2,…,Dn}和關鍵字集W={w1,w2,…,wn}，其中，wi={wi1,wi2,…,wim}，數據擁有者V按如下步驟構造密文交易TXi(1≤i≤n)和索引交易Inxi(1≤i≤n)：

①將文檔Di加密為密文Ci=Enck(Di)(1≤i≤n)。

③為了存儲密文Ci(1≤i≤n)和索引結構Is，V需要找到n+1個值di$且交易接受者是V的未花費交易輸出UTXi(1≤i≤n+1)來構造交易TXi(1≤i≤n)和交易Inxi,1≤i≤n，將密文Ci和索引結構Is分別嵌入交易TXi和交易Inxi中，將其存儲在區塊上,再由礦工將其鏈接到區塊鏈上。關鍵字索引結構如圖2所示。

Figure 2 Keyword index structure圖2 關鍵字索引結構

(4)Trapdoor(k,W′)：授權數據使用者U執行該算法生成關鍵字陷門，輸入密鑰k和要檢索的關鍵字集W′，數據使用者U按如下步驟構建交易ask：

②U可以指定任意用戶進行搜索，假設該搜索者是Q。

③U需要找到值d$且交易接受者為U的一筆未花費交易Tq，U用Tq計算交易ask的主體。

④U將(TW,Inx)嵌入交易ask的外部腳本中，對該交易進行簽名后向全網廣播。

(5)Search(TW,Inx)：由Q來執行該搜索算法，如果Q想獲取交易ask中的服務費，Q需要構造交易get。交易構造如下所示：

②Q以ask作為輸入計算交易get的主體，Q將密文(C1,C2,…,Cn)嵌入交易get中，Q對交易get簽名并向全區塊鏈網絡廣播，再由M將收集的交易寫入區塊鏈，若get未出現在區塊鏈上，U構造交易withdraw來追回交易ask中的費用d$。區塊鏈上的搜索過程如圖3所示。

Figure 3 Search process on blockchain圖3 區塊鏈上搜索過程

(6)Dec(k,get)：U執行該算法，如果交易get出現在區塊鏈上，U從區塊鏈上獲得交易get，U再讀取嵌入交易get中的密文Ci，并使用密鑰k解密密文Ci，獲得明文文檔Deck(Ci)=Di。

4 安全性和效率分析

4.1 安全性證明

定理1如果f是多項式時間安全的偽隨機函數，H1是抗碰撞的哈希函數，Enc和Dec是PPT安全的對稱加解密算法，那么基于區塊鏈的多關鍵字對稱可搜索加密方案Π=(SetUp,KeyGen,Enc,Trapdoor,Search,Dec)是IND-CKA安全的。

(3)模擬陷門TXTW。

(4)模擬交易ask。

使用模擬器S模擬交易ask，如果敵手Α想獲得模擬交易ask*中的手續費，當qt=0時，S需要將關鍵字密文返回給Α。當qt≥1時，S將詢問的關鍵字密文返回給Α，Ciwq是關于關鍵字wq的訪問密文，如果想得到這筆服務費，他必須建立一個新的不同的區塊鏈，這違反了區塊鏈上的不可逆性，又因為f是偽隨機函數，因此敵手Α創建的交易S無法獲得交易ask中的服務費。

□

4.2 效率分析

4.2.1 理論分析

本節將區塊鏈上的可搜索加密方案與其他方案在性能和計算效率方面做了詳細的比較，如表1和表2所示，其中“√”表示是，“×”表示否，E和P分別為循環群中的雙線性對運算時間和指數運算時間，n′為每個文檔的關鍵字個數，m為用戶搜索的關鍵字的數量,H表示哈希運算時間，|D|表示文檔的大小，|TX|表示交易的大小，r表示包含某關鍵字的文檔檢索數量。

Table 1 Performance comparison among different schmems

如表1所示，在支持關鍵字搜索方面，文獻[9]方案和本文方案實現了多關鍵字搜索的功能，文獻[12,22,23]支持密文上的單關鍵字搜索功能。在采用加密算法方面，文獻[22]方案和本文方案采用對稱加密算法，實現了數據的快速加密，文獻[9,12,23]方案使用公鑰加密算法解決了數據加密過程中的密鑰傳輸問題，但公鑰加密算法加密速度慢。在數據存儲平臺方面，文獻[9,12]方案采用云存儲服務器,但云存儲服務器是半誠實且好奇的，搜索過程中不具有公平性，文獻[22,23]方案和本文方案采用區塊鏈技術，為存儲平臺解決了搜索者的公平性問題。

如表2所示，在關鍵字加密計算量上，本文方案計算開銷大于文獻[12,23]方案，但本文方案實現了多關鍵字的數據加密功能，本文方案比文獻[9]方案多1次指數運算；在陷門計算量上，本文方案在滿足多關鍵字搜索的同時只進行了1次指數運算，因此具有較高的計算優勢，文獻[23]方案只用了4個哈希函數但其支持單關鍵字的檢索，文獻[9,12]方案的計算開銷均大于本文方案的；在搜索運算量上，在支持多關鍵字檢索的同時本文方案的計算開銷小于文獻[9]方案的，大于文獻[12,23]方案的，文獻[12,23]方案使用公鑰加密算法實現了密文上的單關鍵字檢索功能，因此文獻[12,23]方案的計算開銷要小于本文方案的；在通信量計算上，文獻[9,12]方案的通信量大小與文檔的大小及包含關鍵字的文檔檢索數量的乘積呈線性關系，文獻[23]方案和文本方案是基于區塊鏈技術存儲的，因此通信量與區塊上交易的大小有關，文獻[23]方案基于聯盟鏈存儲，因此通信量大小是8|TX|，本文方案是基于公開鏈存儲的，區塊上每一筆交易需要6次確認才能記錄到區塊鏈上，通信量是6|TX|，選擇存儲區塊鏈的類型不同所需要的通信計算量也不同。

Table 2 Efficiency comparison among different schemes

本文提出的方案既實現了區塊鏈上的多關鍵字檢索功能，又實現了較高的陷門生成率，同時也滿足搜索效率與關鍵字數量成線性關系。此外，在本文方案中，存儲在區塊鏈上的數據是分布式存儲且不可篡改的，具有安全性更高的加密和陷門生成方式，并且用戶能夠使用區塊鏈技術實現真正的數據共享。

4.2.2 數值實驗分析

本節通過對文獻[9]方案和本文方案進行數值模擬來分析方案的實際性能。在Linux 系統上使用PBC(Pairing-Based Cryptography)庫，基于C語言實現文獻[9]方案和本文方案，數值模擬環境參數配置如表3所示。

Table 3 Simulation environment configuration parameters

本文方案和文獻[9]方案都實現了密文上多關鍵字的檢索功能。在數值模擬實驗中，索引生成、陷門生成和搜索過程均使用相同的關鍵字，增加關鍵字數量，統計在不同數量關鍵字下各個過程的計算開銷。關鍵字的個數設置為100，200，300，400，500，600，700，800，900，1 000。本次實驗結果采用運行程序100次的平均值，本文方案與文獻[9]方案的實驗結果如圖4～圖6所示。

Figure 4 Time of index generation圖4 索引生成時間

Figure 5 Time of trapdoor generation圖5 陷門生成時間

Figure 6 Retrieval time圖6 檢索時間

如圖4所示，在索引生成階段，本文方案與文獻[9]方案的索引生成時間均與關鍵字的個數呈線性增長關系，本文方案的索引生成時間略高于文獻[9]方案的,本文方案的關鍵字加密過程比文獻[9]的多進行1次指數運算，但本文方案實現了區塊鏈上的數據存儲及檢索功能，具有更高的安全性。

如圖5所示，在陷門生成階段，文獻[9]方案陷門生成時間與關鍵字的個數呈線性增長關系，而本文方案關鍵字的增加不會影響陷門生成的時間，且本文方案中的陷門生成時間略低于文獻[9]方案的，本文方案具有較高的陷門生成效率。

如圖6所示，在數據檢索階段，本文方案與文獻[9]方案的檢索時間與關鍵字的個數呈線性增長關系，文獻[9]方案的檢索時間隨關鍵字數量的增加速度比本文方案的要快，在不考慮密文存儲平臺的情況下，在支持多關鍵字搜索的同時，本文方案的檢索效率要明顯優于文獻[9]方案的。

5 結束語

本文針對目前可搜索加密方案中云服務器誠實且好奇的特點和單關鍵字搜索效率低的問題，提出了區塊鏈上多關鍵字的可搜索加密方案。在該方案中，每個參與的節點都是平等的，且無需指定關鍵字的位置，搜索者Q在交易中給數據使用者U返回正確的文檔時需遍歷文件中的所有關鍵字，Q將搜索到符合條件的所有文檔以交易的形式返回給用戶，提供更精確的檢索服務。用戶將所有的數據以交易的形式存儲在區塊鏈上，但區塊的大小是有限的，因此虛擬鏈的使用將會是一個重點。