可驗(yàn)證混合存儲(chǔ)屬性基多關(guān)鍵字密文檢索方案

曹素珍,杜霞玲,楊小東,劉雪艷,汪 銳

(西北師范大學(xué) a.計(jì)算機(jī)科學(xué)與工程學(xué)院; b.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,蘭州 730070)

0 概述

2000年,SONG等人[1]給出可搜索加密的概念,即加密方建立關(guān)鍵字安全索引并與數(shù)據(jù)密文存儲(chǔ)到云服務(wù)器平臺(tái),用戶可通過(guò)陷門查詢包含關(guān)鍵字的密文數(shù)據(jù),實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的直接操作,但采用對(duì)稱密鑰加密數(shù)據(jù),需專門的安全信道傳輸對(duì)稱密鑰。文獻(xiàn)[2]改進(jìn)了SONG等人的工作,采用解密方的公鑰加密數(shù)據(jù),無(wú)需專門的安全信道傳輸密鑰。文獻(xiàn)[3]在云環(huán)境下提出了支持多服務(wù)器多關(guān)鍵字的可搜索加密方案,多個(gè)服務(wù)器共同配合用戶一次性提交的多個(gè)關(guān)鍵字搜索請(qǐng)求,提高了密文檢索的效率。文獻(xiàn)[4]提出了支持搜索結(jié)果驗(yàn)證的公鑰可搜索加密方案,雖然該方案指出滿足多用戶請(qǐng)求的云存儲(chǔ)環(huán)境,但公鑰密碼體制中每一對(duì)公私鑰是對(duì)應(yīng)的,公鑰加密的數(shù)據(jù)僅由其對(duì)應(yīng)的私鑰才可解密,無(wú)法真正實(shí)現(xiàn)多用戶間的數(shù)據(jù)共享。

2005年,SAHAI等人[5]給出了基于屬性的加密方案，加密者用屬性定義訪問(wèn)控制策略,并在密文中嵌入該策略，只有屬性滿足訪問(wèn)控制策略的用戶,方可獲得相應(yīng)的數(shù)據(jù),開(kāi)啟了研究多用戶數(shù)據(jù)共享的新研究領(lǐng)域。文獻(xiàn)[6]結(jié)合屬性加密技術(shù)與可搜索技術(shù),構(gòu)造了基于屬性的可搜索加密方案。文獻(xiàn)[7-8]提出了可驗(yàn)證的屬性基單關(guān)鍵字可搜索加密方案,但都無(wú)法抵抗關(guān)鍵字猜測(cè)攻擊。文獻(xiàn)[9-10]提出了能夠有效抵抗關(guān)鍵字猜測(cè)攻擊的屬性基可搜索方案,但該方案未對(duì)檢索結(jié)果進(jìn)行驗(yàn)證。近年來(lái),新的支持可驗(yàn)證的多關(guān)鍵字搜索的屬性基可搜索加密方案相繼被提出[11-12],但均未考慮屬性鑰失效的非法用戶越權(quán)訪問(wèn)的問(wèn)題。文獻(xiàn)[13]提出了支持屬性撤銷的可搜索加密方案,但該方案計(jì)算開(kāi)銷過(guò)大。文獻(xiàn)[14]提出了密文策略的屬性撤銷可搜索加密方案,但該方案的搜索時(shí)間與屬性個(gè)數(shù)線性正相關(guān)。文獻(xiàn)[15]在文獻(xiàn)[13]的基礎(chǔ)上改進(jìn)了文獻(xiàn)[14]的不足,但該方案需要完全可信的第三方驗(yàn)證搜索結(jié)果的正確性。

鑒于區(qū)塊鏈技術(shù)具有防篡改、公開(kāi)驗(yàn)證、去中心化等特點(diǎn)[16]。文獻(xiàn)[17]提出了基于區(qū)塊鏈的單關(guān)鍵字可搜索加密方案。文獻(xiàn)[18-19]基于區(qū)塊鏈構(gòu)造了可搜索加密方案,但均不支持細(xì)粒度的用戶訪問(wèn)。

本文提出一種混合存儲(chǔ)屬性基多關(guān)鍵字密文檢索方案。通過(guò)將關(guān)鍵字索引與數(shù)據(jù)密文分別存儲(chǔ)到區(qū)塊鏈和云服務(wù)器上,使數(shù)據(jù)檢索空間縮小,易于快速地在海量數(shù)據(jù)中查找所需數(shù)據(jù)，密鑰加密后,即可在公開(kāi)信道傳輸。在此基礎(chǔ)上，通過(guò)屬性版本號(hào)撤銷用戶,以防止屬性變化身份失效的非法用戶繼續(xù)訪問(wèn)數(shù)據(jù)。

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

1.1 符號(hào)說(shuō)明

符號(hào)含義說(shuō)明如表1所示。

表1 符號(hào)含義說(shuō)明Table 1 Description of symbol meaning

1.2 雙線性映射

設(shè)G1和GT分別是兩個(gè)階為素?cái)?shù)p的乘法循環(huán)群,其中,g為G1的一個(gè)生成元,則雙線性映射e:G1×G1→GT滿足以下3個(gè)性質(zhì):

2)非退化性:e(g,g)≠1。

3)可計(jì)算性:對(duì)于群G1中的任意兩個(gè)元素g1、g2,存在有效算法計(jì)算e(g1,g2)。

1.3 與門訪問(wèn)結(jié)構(gòu)

在屬性基密碼體制中,與門訪問(wèn)控制策略通常被定義為用戶屬性與訪問(wèn)控制結(jié)構(gòu)之間的關(guān)聯(lián)關(guān)系,具體描述為:全局屬性集合U={x1,x2,…,xn},訪問(wèn)控制結(jié)構(gòu)At={At1,At2,…,Atn},當(dāng)且僅當(dāng)xi=Ati,i∈[1,n]時(shí),稱屬性滿足訪問(wèn)控制結(jié)構(gòu)。

1.4 安全性理論假設(shè)

本文方案的安全性基于HDH問(wèn)題、MDDH問(wèn)題和CDH問(wèn)題,具體定義如下:

2 基本方案

本文方案包含的實(shí)體主要有以下5個(gè)部分:

1)數(shù)據(jù)屬主:用對(duì)稱密鑰加密文檔,并上傳到云服務(wù)器,提取關(guān)鍵字生成索引,并上傳到區(qū)塊鏈。

2)云服務(wù)器:只存儲(chǔ)文檔密文。

3)授權(quán)機(jī)構(gòu):生成系統(tǒng)公共參數(shù)和主密鑰。

4)區(qū)塊鏈:存儲(chǔ)關(guān)鍵字索引信息,生成下載數(shù)據(jù)令牌。

5)數(shù)據(jù)用戶:生成陷門值,解密相應(yīng)文件。其中,云服務(wù)器是誠(chéng)實(shí)但好奇的;區(qū)塊鏈?zhǔn)峭耆尚诺拇鎯?chǔ)設(shè)備,方案中僅用于存儲(chǔ)關(guān)鍵字索引。

具體的系統(tǒng)模型如圖1所示。

圖1 本文系統(tǒng)模型

3 具體方案

本文具體方案如下:

6)Search(InW,Tk)→I:區(qū)塊鏈上的搜索者執(zhí)行,輸入搜索陷門Tk和索引InW。首先,搜索者通過(guò)式(1)檢驗(yàn)陷門中用戶身份與索引中用戶身份是否相同;然后,通過(guò)式(2)檢驗(yàn)陷門中關(guān)鍵字與索引中關(guān)鍵字是否相同;若式(1)和式(2)同時(shí)成立,則將I=(I1,I2,…,IN)返回給用戶;否則輸出⊥。

(1)

(2)

7)Dow(GP,I)→CT:云服務(wù)執(zhí)行。輸入公共參數(shù)GP、索引I。云服務(wù)器計(jì)算式Enck(di)=Ci⊕H5(IDdi)，并將所得結(jié)果Enck(di)返回給用戶。

8)Verify(R,CT):用戶輸入CT和R,計(jì)算式(3)驗(yàn)證搜索結(jié)果的正確性,若等式成立轉(zhuǎn)入步驟(9);否則,輸出⊥。

(3)

9)Dec(CT)→(D):用戶執(zhí)行,輸入搜索密文Enck(di),用戶屬性鑰sk。首先,身份為IDui用戶通過(guò)計(jì)算H1(F′H1(IDui)),恢復(fù)出Li=F″⊕H1(F′H1(IDui))。若用戶的屬性滿足訪問(wèn)結(jié)構(gòu),則可通過(guò)式(4)計(jì)算得到E,進(jìn)而通過(guò)式(5)和式(6)計(jì)算得到對(duì)稱密鑰k,解密出原始密文;否則終止算法。

(4)

(5)

(6)

4 安全性分析

4.1 抗用戶合謀攻擊

在用戶的私鑰中同時(shí)嵌入用戶屬性和用戶版本號(hào)。因版本號(hào)的不同,即使擁有相同屬性集合的用戶,他們的私鑰也不會(huì)相同。用戶間私鑰合謀生成搜索陷門,該陷門也無(wú)法通過(guò)區(qū)塊鏈上搜索者的驗(yàn)證,用戶間合謀也得不到額外信息,本文方案滿足抗用戶間的合謀攻擊。

4.2 私鑰傳輸

定理1若HDH問(wèn)題是困難的,則本文方案私鑰的傳輸無(wú)需安全信道。

證明根據(jù)HDH問(wèn)題的定義:已知gv和gH1(IDui),在v和H1(IDui)未知的前提下,判斷H1(gvH1(IDui))是否為群G中的元素是困難的。進(jìn)而,求解私鑰組件Li=sk2⊕H1(gvH1(IDui))是困難的,因此私鑰的傳輸無(wú)需安全信道。

4.3 對(duì)稱密鑰安全性

文檔上傳云服務(wù)器前,先用傳統(tǒng)的對(duì)稱算法加密,再用屬性加密算法加密對(duì)稱密鑰。本文方案基于MDDH問(wèn)題確保對(duì)稱密鑰的安全性。

定理2若MDDH問(wèn)題是困難的,則本文方案在隨機(jī)預(yù)言模型下對(duì)稱密鑰是安全的。

證明挑戰(zhàn)者B輸入MDDH問(wèn)題的實(shí)例(g,gπ,e(g,g)φ,Z)和群參數(shù)(g,p,e,G,GT),目標(biāo)是計(jì)算Z=e(g,g)πφ挑戰(zhàn)者B和敵手A進(jìn)行如下游戲模擬:

初始化:A提交挑戰(zhàn)訪問(wèn)結(jié)構(gòu)A*=Λi∈IW*Ai給挑戰(zhàn)者B,運(yùn)行系統(tǒng)建立算法,將公共參數(shù)GP=返回給A。

4)H3詢問(wèn):B維護(hù)一個(gè)初始為空的列表L3=。A向B詢問(wèn)R3∈GT的H3值,B首先查找R3是否在表L3中。若是,則將相應(yīng)的h3值返回給A;否則隨機(jī)選取d3∈{0,1}λ,令h3=d3,并添加到表L3中,然后發(fā)送h3給A。

5)H4詢問(wèn):B維護(hù)一個(gè)初始為空的列表L4=。A向B詢問(wèn)R4∈{0,1}λ的H4值,B首先查找R4是否在表L4中。若是,則將對(duì)應(yīng)的h4值返回A;否則隨機(jī)選取d4∈{0,1}λ,令h4=d4,并添加到列表L4中,然后返回h4給A。

詢問(wèn)階段1:

2)解密詢問(wèn):敵手A做訪問(wèn)結(jié)構(gòu)At*下的解密詢問(wèn),B應(yīng)答如下:

(1)若A的屬性Atts滿足訪問(wèn)結(jié)構(gòu)At*,B以⊥應(yīng)答;否則,轉(zhuǎn)到步驟(2)。

詢問(wèn)階段2:敵手A可以重復(fù)進(jìn)行階段1的詢問(wèn)。

猜測(cè):A輸出關(guān)于b的猜測(cè)b′∈{0,1},若b=b′,則B能判斷出e(g,g)πφ=Z;否則e(g,g)πφ≠Z。

證畢。

4.4 陷門的不可區(qū)分性

定理3若CDH假設(shè)成立,則本文方案滿足陷門的不可區(qū)分性。

證明假設(shè)存在一個(gè)多項(xiàng)式時(shí)間敵手A能夠以不可忽略的優(yōu)勢(shì)εA攻破本文方案,則挑戰(zhàn)者B可以利用A以不可忽略的優(yōu)勢(shì)εB解決CDH問(wèn)題。

初始化:A向B提交要挑戰(zhàn)的訪問(wèn)策略A*=Λi∈IW*Ai,其中IW*表示屬性下標(biāo),即屬性索引值。

建立階段:挑戰(zhàn)者B運(yùn)行系統(tǒng)建立算法,輸出公共參數(shù)GP。挑戰(zhàn)者B通過(guò)拋擲硬幣游戲選擇ξ∈{0,1},如果ξ=1,則T=gabc;否則,T為群G中的一個(gè)隨機(jī)值。

詢問(wèn)階段1:

敵手A選擇任意屬性集Atts*和身份IDu*,進(jìn)行密鑰和陷門詢問(wèn):

詢問(wèn)階段2:敵手A可以重復(fù)進(jìn)行階段1的詢問(wèn)。

猜測(cè):敵手A輸出ξ對(duì)ξ′∈{0,1}的猜測(cè)。當(dāng)ξ=ξ′時(shí),挑戰(zhàn)者B輸出1,表示T=gabc;否則輸出0,表示T是G中的隨機(jī)值,挑戰(zhàn)者解決困難問(wèn)題的概率計(jì)算如下:

1)當(dāng)輸出為1時(shí),表明敵手A得到關(guān)鍵字<ω0,ω1>的有效密文。此時(shí),敵手A的優(yōu)勢(shì)為:εA=Pr[ξ′=ξ|T=gabc]=ε+1/2。

2)當(dāng)輸出為0時(shí),表明T是群G中的一個(gè)隨機(jī)值。此時(shí),敵手A的優(yōu)勢(shì)為:εA=Pr[ξ′=ξ|T∈GT]=1/2。

根據(jù)步驟1)和步驟2)得出挑戰(zhàn)者B的優(yōu)勢(shì)為:

因此,挑戰(zhàn)者B能夠以不可忽略的優(yōu)勢(shì)ε/2解決CDH問(wèn)題。

5 性能分析

為更全面地闡述本文方案的性能,從功能特性、計(jì)算開(kāi)銷以及實(shí)驗(yàn)仿真等方面對(duì)比分析本文方案與具有代表性的支持屬性撤銷可搜索加密[13-15]方案的優(yōu)劣勢(shì)。

5.1 功能特征對(duì)比

從表2可以看出,相比于文獻(xiàn)[13-15]方案,本文方案在支持用戶撤銷的基礎(chǔ)上,加密了用戶屬性私鑰,可使其在公開(kāi)信道傳輸;同時(shí),將索引和密文分開(kāi)存儲(chǔ),易于提高檢索效率。另外,相比于文獻(xiàn)[13]方案,本文方案支持多個(gè)關(guān)鍵字同時(shí)檢索,易于快速檢索所需數(shù)據(jù)。其中,√為支持,×為不支持。

表2 功能特征對(duì)比

5.2 計(jì)算開(kāi)銷對(duì)比

通過(guò)理論數(shù)值分析,對(duì)比本文方案與文獻(xiàn)[13-15]方案。假設(shè)關(guān)鍵字個(gè)數(shù)對(duì)計(jì)算開(kāi)銷的影響相同,僅考慮耗時(shí)長(zhǎng)的指數(shù)運(yùn)算和對(duì)數(shù)運(yùn)算,忽略哈希運(yùn)算和異或運(yùn)算,對(duì)比結(jié)果如表3所示。其中:|U|代表全局屬性個(gè)數(shù);|S|代表用戶屬性個(gè)數(shù);|R|代表滿足搜索要求的密文文件數(shù);E代表群G上的指數(shù)運(yùn)算;ET代表群GT上的指數(shù)運(yùn)算;P代表對(duì)數(shù)運(yùn)算。

表3 計(jì)算開(kāi)銷對(duì)比

從表3中系統(tǒng)建立、密鑰生成、加密、陷門生成、搜索等開(kāi)銷可以看出,本文方案和文獻(xiàn)[15]方案均優(yōu)于文獻(xiàn)[13-14]方案;另外,本文方案的解密計(jì)算開(kāi)銷遠(yuǎn)遠(yuǎn)低于文獻(xiàn)[14]方案,為恒定值。與文獻(xiàn)[15]方案相比,本文方案系統(tǒng)建立開(kāi)銷與用戶個(gè)數(shù)線性相關(guān),但本文方案的密鑰生成、加密及陷門生成開(kāi)銷低于文獻(xiàn)[15]方案,搜索開(kāi)銷高于文獻(xiàn)[15]方案,但也為恒定值。

5.3 實(shí)驗(yàn)仿真

實(shí)驗(yàn)環(huán)境為:Intel?CoreTMi5-2400 @ 3.10 GHz的處理器、4 GB的內(nèi)存、Windows10 x64的操作系統(tǒng),調(diào)用jpbc-2.0.0庫(kù)。設(shè)定關(guān)鍵字空間大小為1 000,用戶屬性個(gè)數(shù)取10、20、30、40、50、60。數(shù)值模擬對(duì)比本文方案與文獻(xiàn)[13-15]的加密和搜索階段的時(shí)間開(kāi)銷。實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

圖2 加密時(shí)間與屬性個(gè)數(shù)的關(guān)系

圖3 搜索時(shí)間與屬性個(gè)數(shù)的關(guān)系

從圖2可以看出,文獻(xiàn)[13-15]方案的加密時(shí)間開(kāi)銷,隨著屬性個(gè)數(shù)的增加線性增長(zhǎng)，而本文方案加密階段采用耗時(shí)少的哈希函數(shù)運(yùn)算、異或運(yùn)算,并對(duì)用戶屬性進(jìn)行聚合,使得加密時(shí)間恒定,與屬性個(gè)數(shù)無(wú)關(guān)。從圖3可以看出,文獻(xiàn)[13-14]方案的搜索時(shí)間與屬性個(gè)數(shù)正相關(guān),而本文方案和文獻(xiàn)[15]方案的搜索時(shí)間恒定,與理論分析結(jié)果保持一致。

6 結(jié)束語(yǔ)

云服務(wù)器在屬性基可搜索加密方案中執(zhí)行關(guān)鍵字搜索、用戶撤銷等操作時(shí),存在搜索效率低、用戶隱私泄露等問(wèn)題。本文通過(guò)引入?yún)^(qū)塊鏈技術(shù),將屬性可搜索加密中的索引與密文文檔分開(kāi)存儲(chǔ),同時(shí)對(duì)密鑰進(jìn)行加密,使其在公開(kāi)信道傳輸。此外,在密鑰中同時(shí)嵌入用戶版本號(hào)和用戶屬性,及時(shí)撤銷由屬性變化引起用戶身份失效的非法用戶,防止隱私泄露。效率分析結(jié)果表明,該方案搜索時(shí)間與屬性個(gè)數(shù)無(wú)關(guān)。下一步將在區(qū)塊鏈環(huán)境下,通過(guò)隱藏訪問(wèn)策略實(shí)現(xiàn)屬性基可驗(yàn)證的多關(guān)鍵字密文搜索。