區(qū)塊鏈上支持多關(guān)鍵字檢索的可搜索加密方案 *

牛淑芬，王金風(fēng)，王伯彬，陳敬民，杜小妮

(1.西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州730070；2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州730070)

1 引言

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

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

2008年，Nakamoto[13]提出了一個(gè)不涉及第三方交易記錄的比特幣平臺(tái)。區(qū)塊鏈[14]是一個(gè)基于比特幣協(xié)議維護(hù)不可篡改的數(shù)據(jù)記錄列表。區(qū)塊鏈本質(zhì)上是一個(gè)P2P網(wǎng)絡(luò)系統(tǒng)中的分布式數(shù)據(jù)庫(kù)[15]，區(qū)塊鏈上的每一個(gè)區(qū)塊是使用密碼學(xué)的相關(guān)技術(shù)而產(chǎn)生的數(shù)據(jù)塊，交易創(chuàng)建后將被廣播到區(qū)塊鏈系統(tǒng)中；交易被礦工[16]驗(yàn)證有效后將被記錄到臨時(shí)區(qū)塊；礦工使用工作量證明機(jī)制[17]計(jì)算出區(qū)塊后將此區(qū)塊向全網(wǎng)廣播，再將區(qū)塊鏈接在區(qū)塊鏈上。區(qū)塊鏈上的交易是公開透明且不可更改的。

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

2 系統(tǒng)模型和安全模型

2.1 系統(tǒng)模型

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

Figure 1 System model圖1 系統(tǒng)模型

2.2 方案形式化定義

(1)param←SetUp(1λ)：輸入安全系數(shù)λ，輸出系統(tǒng)參數(shù)param。

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

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

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

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

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

2.3 安全模型

3 區(qū)塊鏈上多關(guān)鍵字的可搜索加密方案

區(qū)塊鏈上的多關(guān)鍵字可搜索加密主要有數(shù)據(jù)擁有者V、數(shù)據(jù)使用者U、搜索者Q和礦工M共4個(gè)參與者，方案的詳細(xì)過程描述如下：

(2)KeyGen(k)：假設(shè)每一個(gè)用戶X有一個(gè)秘密指數(shù)aX，其中0≤aX≤q-1，對(duì)應(yīng)的公開值為bX=gaX，bX被包含在X的證書里并被可信的權(quán)威機(jī)構(gòu)TA簽名。

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

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

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

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

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

Figure 2 Keyword index structure圖2 關(guān)鍵字索引結(jié)構(gòu)

(4)Trapdoor(k,W′)：授權(quán)數(shù)據(jù)使用者U執(zhí)行該算法生成關(guān)鍵字陷門，輸入密鑰k和要檢索的關(guān)鍵字集W′，數(shù)據(jù)使用者U按如下步驟構(gòu)建交易ask：

②U可以指定任意用戶進(jìn)行搜索，假設(shè)該搜索者是Q。

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

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

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

②Q以ask作為輸入計(jì)算交易get的主體，Q將密文(C1,C2,…,Cn)嵌入交易get中，Q對(duì)交易get簽名并向全區(qū)塊鏈網(wǎng)絡(luò)廣播，再由M將收集的交易寫入?yún)^(qū)塊鏈，若get未出現(xiàn)在區(qū)塊鏈上，U構(gòu)造交易withdraw來追回交易ask中的費(fèi)用d$。區(qū)塊鏈上的搜索過程如圖3所示。

Figure 3 Search process on blockchain圖3 區(qū)塊鏈上搜索過程

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

4 安全性和效率分析

4.1 安全性證明

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

(3)模擬陷門TXTW。

(4)模擬交易ask。

使用模擬器S模擬交易ask，如果敵手Α想獲得模擬交易ask*中的手續(xù)費(fèi)，當(dāng)qt=0時(shí)，S需要將關(guān)鍵字密文返回給Α。當(dāng)qt≥1時(shí)，S將詢問的關(guān)鍵字密文返回給Α，Ciwq是關(guān)于關(guān)鍵字wq的訪問密文，如果想得到這筆服務(wù)費(fèi)，他必須建立一個(gè)新的不同的區(qū)塊鏈，這違反了區(qū)塊鏈上的不可逆性，又因?yàn)閒是偽隨機(jī)函數(shù)，因此敵手Α創(chuàng)建的交易S無法獲得交易ask中的服務(wù)費(fèi)。

□

4.2 效率分析

4.2.1 理論分析

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

Table 1 Performance comparison among different schmems

如表1所示，在支持關(guān)鍵字搜索方面，文獻(xiàn)[9]方案和本文方案實(shí)現(xiàn)了多關(guān)鍵字搜索的功能，文獻(xiàn)[12,22,23]支持密文上的單關(guān)鍵字搜索功能。在采用加密算法方面，文獻(xiàn)[22]方案和本文方案采用對(duì)稱加密算法，實(shí)現(xiàn)了數(shù)據(jù)的快速加密，文獻(xiàn)[9,12,23]方案使用公鑰加密算法解決了數(shù)據(jù)加密過程中的密鑰傳輸問題，但公鑰加密算法加密速度慢。在數(shù)據(jù)存儲(chǔ)平臺(tái)方面，文獻(xiàn)[9,12]方案采用云存儲(chǔ)服務(wù)器,但云存儲(chǔ)服務(wù)器是半誠(chéng)實(shí)且好奇的，搜索過程中不具有公平性，文獻(xiàn)[22,23]方案和本文方案采用區(qū)塊鏈技術(shù)，為存儲(chǔ)平臺(tái)解決了搜索者的公平性問題。

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

Table 2 Efficiency comparison among different schemes

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

4.2.2 數(shù)值實(shí)驗(yàn)分析

本節(jié)通過對(duì)文獻(xiàn)[9]方案和本文方案進(jìn)行數(shù)值模擬來分析方案的實(shí)際性能。在Linux 系統(tǒng)上使用PBC(Pairing-Based Cryptography)庫(kù)，基于C語言實(shí)現(xiàn)文獻(xiàn)[9]方案和本文方案，數(shù)值模擬環(huán)境參數(shù)配置如表3所示。

Table 3 Simulation environment configuration parameters

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

Figure 4 Time of index generation圖4 索引生成時(shí)間

Figure 5 Time of trapdoor generation圖5 陷門生成時(shí)間

Figure 6 Retrieval time圖6 檢索時(shí)間

如圖4所示，在索引生成階段，本文方案與文獻(xiàn)[9]方案的索引生成時(shí)間均與關(guān)鍵字的個(gè)數(shù)呈線性增長(zhǎng)關(guān)系，本文方案的索引生成時(shí)間略高于文獻(xiàn)[9]方案的,本文方案的關(guān)鍵字加密過程比文獻(xiàn)[9]的多進(jìn)行1次指數(shù)運(yùn)算，但本文方案實(shí)現(xiàn)了區(qū)塊鏈上的數(shù)據(jù)存儲(chǔ)及檢索功能，具有更高的安全性。

如圖5所示，在陷門生成階段，文獻(xiàn)[9]方案陷門生成時(shí)間與關(guān)鍵字的個(gè)數(shù)呈線性增長(zhǎng)關(guān)系，而本文方案關(guān)鍵字的增加不會(huì)影響陷門生成的時(shí)間，且本文方案中的陷門生成時(shí)間略低于文獻(xiàn)[9]方案的，本文方案具有較高的陷門生成效率。

如圖6所示，在數(shù)據(jù)檢索階段，本文方案與文獻(xiàn)[9]方案的檢索時(shí)間與關(guān)鍵字的個(gè)數(shù)呈線性增長(zhǎng)關(guān)系，文獻(xiàn)[9]方案的檢索時(shí)間隨關(guān)鍵字?jǐn)?shù)量的增加速度比本文方案的要快，在不考慮密文存儲(chǔ)平臺(tái)的情況下，在支持多關(guān)鍵字搜索的同時(shí)，本文方案的檢索效率要明顯優(yōu)于文獻(xiàn)[9]方案的。

5 結(jié)束語

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