陳思琦，黃汝維

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

1 引言

在云計(jì)算模式下，用戶將存儲(chǔ)或者計(jì)算任務(wù)外包給云服務(wù)器，就能夠享受高質(zhì)量的存儲(chǔ)服務(wù)或計(jì)算服務(wù)。為了保證隱私安全，用戶通常將數(shù)據(jù)加密后進(jìn)行存儲(chǔ)?？伤阉骷用芗夹g(shù)使得用戶能夠在不解密的前提下對(duì)密文進(jìn)行檢索操作，用戶將數(shù)據(jù)加密后存儲(chǔ)在云端，提出搜索請(qǐng)求的用戶利用搜索關(guān)鍵字生成陷門，云服務(wù)器執(zhí)行關(guān)鍵字搜索任務(wù)，然后返回包含該關(guān)鍵字的密文。大部分的可搜索加密方案屬于“一對(duì)一”通信模式，在云計(jì)算環(huán)境下，用戶希望能給特定的一部分人分享數(shù)據(jù)，數(shù)據(jù)擁有者要么對(duì)密鑰進(jìn)行共享，這顯然會(huì)帶來密鑰泄露的可能性；要么每增加1個(gè)用戶，均使用該用戶的公鑰對(duì)數(shù)據(jù)進(jìn)行加密，這使得數(shù)據(jù)擁有者加密負(fù)擔(dān)較重；或者通過聚合密鑰等操作，當(dāng)用戶逐漸增多時(shí)，可信授權(quán)機(jī)構(gòu)管理密鑰的負(fù)擔(dān)也會(huì)增加。在大部分單關(guān)鍵詞可搜索加密方案中，如果第1次搜索返回的結(jié)果無法滿足用戶需要，用戶將會(huì)使用另外的關(guān)鍵詞進(jìn)行下一輪搜索，這種多次搜索-解密的過程將會(huì)花費(fèi)很大的代價(jià)。

在多用戶數(shù)據(jù)共享方面，2005年，Sahai等人[1]提出了基于屬性的加密方案ABE(Attribute-Based Encryption)。基于屬性的加密方案主要分為密鑰策略的屬性加密方案KP-ABE(Key-Policy Attribute-Based Encryption)和密文策略的屬性加密方案CP-ABE(Ciphertext-Policy Attribute-Based Encryption)。在CP-ABE中，密文與訪問策略相關(guān)聯(lián)，適合云環(huán)境下數(shù)據(jù)分享場(chǎng)景，數(shù)據(jù)屬主制定訪問策略，用戶的屬性用來生成私鑰，滿足訪問策略的用戶能夠解密相應(yīng)的數(shù)據(jù)。Goyal等人[2]提出了一個(gè)基于訪問樹結(jié)構(gòu)的KP-ABE方案。Kaushik等人[3]于2013年構(gòu)造了基于CP-ABE的可搜索加密方案，采用了訪問樹結(jié)構(gòu)。大部分基于訪問樹的可搜索加密方案雖然能夠直觀方便地表達(dá)訪問策略，但是存在計(jì)算開銷、通信開銷較大等問題。2011年，Waters[4]提出了3種基于不同困難假設(shè)的CP-ABE方案，基于線性秘密共享策略LSSS(Linear Secret Sharing Scheme)，實(shí)現(xiàn)了與訪問樹相等的策略表達(dá)能力，且具有更高效率和安全性。陳燕俐等人[5]提出了一個(gè)基于LSSS共享矩陣的可搜索加密方案，能夠支持文件級(jí)細(xì)粒度的訪問控制。部分其他基于CP-ABE的加密方案主要針對(duì)屬性撤銷、提高加解密效率方面[6 - 9]。

為了縮小搜索范圍，避免多次搜索-解密的過程，Golle等人[10]提出了2種支持連接關(guān)鍵詞的搜索方案。Chuah 等人[11]于2011年提出了基于 Bed Tree的多關(guān)鍵詞搜索方案，提高了搜索效率。王尚平等人[12]提出了支持關(guān)鍵詞連接搜索的加密方案，并且通過授權(quán)用戶以及云服務(wù)器先后對(duì)關(guān)鍵詞加密來實(shí)現(xiàn)多用戶共享。但是，文獻(xiàn)[10-12]的方案基于對(duì)稱密碼學(xué)，實(shí)用性有限。Boneh等人[13]基于謂詞加密概念，構(gòu)建了支持加密數(shù)據(jù)上的比較查詢(x≥a)公鑰系統(tǒng)，實(shí)現(xiàn)加密數(shù)據(jù)上的連接關(guān)鍵詞搜索，但是該方案使用合數(shù)階雙線性群，需要較大的群空間。2012年，Chen 等人[14]提出了2種支持關(guān)鍵詞連接搜索的加密方案，但是該方案無法支持關(guān)鍵詞子集的搜索。Zhang等人[15]提出了支持關(guān)鍵詞子集搜索的加密方案，但是用戶端的計(jì)算量較大。宋衍等人[16]提出了一個(gè)支持關(guān)鍵詞任意連接搜索的屬性加密方案，在方案中使用了訪問樹作為訪問結(jié)構(gòu)，當(dāng)文檔數(shù)據(jù)較多時(shí)，加解密效率仍然有待提高。

針對(duì)大部分基于屬性的可搜索加密方案存在效率低下、密鑰易泄露以及僅支持單關(guān)鍵詞搜索的問題，本文基于LSSS提出了一個(gè)支持連接關(guān)鍵詞搜索的屬性加密方案AECKS(Attribute-based Encryption supporting Conjunctive Keyword Search)，能夠支持文件級(jí)細(xì)粒度訪問控制，提高用戶的加解密效率。基于多項(xiàng)式方程實(shí)現(xiàn)了連接關(guān)鍵詞的搜索，使得搜索范圍更加精確，提升了用戶的搜索體驗(yàn)。

2 基礎(chǔ)知識(shí)

2.1 雙線性群

設(shè)p、q是素?cái)?shù)，G1、G2分別是階為p、q的乘法循環(huán)群，雙線性映射e:G1×G1→G2。則有：

(1)雙線性。對(duì)于任意的a,b∈Zp和x,y∈G1都有e(xa,yb)=e(x,y)ab；對(duì)于任意的x1,x2,y∈G1，有e(x1x2,y)=e(x1,y)e(x2,y)。

(2)非退化性。存在x,y∈G1，使得e(x,y)≠1，其中1是G2的單位。

(3)可計(jì)算性。存在有效的多項(xiàng)式時(shí)間算法對(duì)任意的x,y∈G1，計(jì)算e(x,y)的值。

2.2 q維判定性Diffie-Hellman問題(q-DDH)

2.3 Shamir秘密共享方案

Shamir秘密共享方案基于拉格朗日多項(xiàng)式插值，設(shè)p為素?cái)?shù)，共享秘密值為s。通過tt個(gè)子密鑰重構(gòu)得到共享秘密值s，當(dāng)t′

給出tt個(gè)子密鑰yi，i≤i≤tt,通過拉格朗日插值公式重構(gòu)出多項(xiàng)式f(x)為:

(1)

2.4 線性秘密共享LSSS策略

3 系統(tǒng)模型與方案設(shè)計(jì)

3.1 系統(tǒng)模型

AECKS方案的系統(tǒng)模型如圖1所示，包括授權(quán)管理機(jī)構(gòu)(UM)、數(shù)據(jù)擁有者(DO)、數(shù)據(jù)用戶(DU)和云服務(wù)器(CS)共4個(gè)參與方。UM負(fù)責(zé)管理系統(tǒng)中的全部屬性，并且負(fù)責(zé)系統(tǒng)初始化和用戶密鑰生成工作，UM是完全可信的；DO首先對(duì)文檔的每個(gè)文件生成關(guān)鍵詞集合，使用訪問結(jié)構(gòu)將關(guān)鍵詞集合進(jìn)行加密，文檔數(shù)據(jù)利用對(duì)稱加密算法加密(如AES加密算法)，然后將所有密文上傳到CS；DU根據(jù)搜索需要，利用私鑰以及想要搜索的關(guān)鍵詞集合生成陷門后發(fā)送給CS；CS負(fù)責(zé)用戶數(shù)據(jù)存儲(chǔ)以及數(shù)據(jù)搜索工作，CS是“誠(chéng)實(shí)但好奇”的，能夠忠實(shí)執(zhí)行用戶的操作，但可能會(huì)試圖從中獲取信息。

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

3.2 方案定義

支持連接關(guān)鍵詞搜索的屬性加密方案AECKS包括下列5個(gè)多項(xiàng)式時(shí)間算法：

(1)Setup(1λ)→ (PK,MSK)：由UM執(zhí)行初始化算法，生成系統(tǒng)公私鑰。UM輸入1個(gè)安全參數(shù)1λ，輸出1個(gè)公鑰PK和1個(gè)主密鑰MSK。

(2)Encrypt(PK,(M,ρ),W)→ (CT)：由DO執(zhí)行加密算法。算法輸入公共參數(shù)PK、用戶定義的訪問結(jié)構(gòu)(M,ρ)和待加密的關(guān)鍵詞集合W，輸出密文CT,其中ρ為2.4節(jié)中的映射函數(shù)。

(3)KeyGen(PK,MSK,S)→ (SK)：由UM執(zhí)行用戶私鑰生成算法，算法以公共參數(shù)PK、系統(tǒng)主密鑰MSK以及用戶屬性集S作為輸入，輸出用戶私鑰SK。

(4)TokenGen(SK,W′)→ (Trap)：由DU執(zhí)行陷門生成算法，輸入用戶私鑰SK和待搜索的關(guān)鍵詞集合W′，輸出W′對(duì)應(yīng)的陷門值Trap。

(5)Search(CT,Trap)： 由CS執(zhí)行關(guān)鍵詞搜索算法，輸入密文CT和陷門值Trap，如果用戶滿足數(shù)據(jù)屬主定義的訪問策略且搜索的關(guān)鍵詞集合存在，則CS返回對(duì)應(yīng)的搜索結(jié)果，否則CS返回0。

3.3 方案設(shè)計(jì)

PK=(e,p,ga,gb,{hi}i∈[1,|U|]G,GT,H)

(2)

保存主密鑰為:

MSK= (a,b)

(3)

z(x)=a·(x-H(w1))(x-H(w2))…

(x-H(wmp))+k=

ampxmp+…+a1x+a0

(4)

對(duì)于i∈{ 0,1,…,mp}，計(jì)算Hi=gbai，并計(jì)算W0=gasgk，W1=gs，構(gòu)造密文:

CT=(W0,W1,{Hi,i∈{0,1,…,mp}},

{(Ci,Di),i∈[1,l]})

(5)

SK=(S,K,L,{Kx,?x∈S})

(6)

Trap=(S,tok0,tok1,L′,

{Fi,i∈{0,1,…,mp}},{K′x,x∈S})

(7)

4 方案分析

4.1 正確性分析

在關(guān)鍵詞搜索階段，由用戶而非云服務(wù)器執(zhí)行陷門生成工作，在進(jìn)行搜索操作時(shí)，云服務(wù)器通過雙線性映射計(jì)算得到秘密值Eroot，計(jì)算過程如下所示：

(8)

如果用戶的屬性集能夠滿足訪問結(jié)構(gòu)(M,ρ),那么存在一組值{ωi∈Zp}i∈I使得∑i∈Iωiλi=s，所以

Eroot=-e(g,g)bstu

(9)

當(dāng)用戶的屬性集滿足數(shù)據(jù)屬主訪問策略后，云服務(wù)器再執(zhí)行關(guān)鍵詞搜索算法判斷關(guān)鍵詞是否存在。

e(W0,tok0)=e(gasgk,gbu)=

e(g,g)asbu+kbu

(10)

e(W1,tok1)=e(gs,g(α-t)bu)e(g,g)asbu-stbu

(11)

(12)

如果陷門關(guān)鍵詞集合包含于密文中的關(guān)鍵詞集合，則能夠還原出該隨機(jī)多項(xiàng)式，即:

(13)

因此

e(W0,tok0)=

(14)

等式成立，說明關(guān)鍵詞集合存在，則云服務(wù)器返回相應(yīng)的搜索結(jié)果。

4.2 安全性分析

4.2.1 抵抗合謀攻擊

在本文方案AECKS中，DO將秘密共享值嵌入了密文中，如果要進(jìn)行關(guān)鍵詞的比較操作，那么用戶或者攻擊者需要將e(g,g)buts恢復(fù)出來，假設(shè)User1是一個(gè)能成功進(jìn)行搜索請(qǐng)求的用戶，即使攻擊者A的屬性集合包含了User1的屬性集合，但是由于在進(jìn)行用戶私鑰構(gòu)造時(shí)，不同用戶所選取的隨機(jī)數(shù)不同，所以無法以共謀方式通過組件的組合獲得User1的私鑰。攻擊者A無法偽造正確陷門，因?yàn)橄蓍T值的每個(gè)組件都是以隨機(jī)大數(shù)u為指數(shù)的冪，攻擊者A不能根據(jù)tok0=gbu求解得到u的值，因此AECKS在離散對(duì)數(shù)問題假設(shè)下是安全的。

4.2.2 用戶密鑰安全

大部分基于屬性的可搜索加密方案是由云服務(wù)器進(jìn)行關(guān)鍵詞陷門生成，在這個(gè)階段，用戶密鑰通常不加密就直接提交給云服務(wù)器，由云服務(wù)器進(jìn)行用戶權(quán)限的判斷，這可能導(dǎo)致用戶密鑰泄露。本文方案陷門由搜索用戶調(diào)用算法生成，避免了密鑰泄露的可能性。同時(shí)在密鑰生成階段，用戶私鑰中的組件K、L與隨機(jī)大數(shù)t相關(guān)聯(lián)，在離散對(duì)數(shù)困難問題假設(shè)下，用戶密鑰的安全性得到了保障。

4.2.3 抵抗選擇關(guān)鍵字攻擊

定理1在q-DDH假設(shè)下，AECKS能夠抵抗選擇關(guān)鍵字攻擊(CKA)。

下面采用反證法證明。

(2)詢問階段1。A詢問關(guān)鍵詞集合W′c=(w′c,1,w′c,2,…,w′c,t)的陷門，同樣在生成陷門階段，對(duì)于w′c,j∈W′c，如果攻擊者A已經(jīng)詢問過w′c,j，則挑戰(zhàn)者S返回相應(yīng)的xc,j，如果未被詢問，則S隨機(jī)選取xc,j∈ZP作為H(wc,j)，并將其加入B中。隨后攻擊者A將對(duì)關(guān)鍵詞W′c進(jìn)行密文搜索，確定關(guān)鍵詞W′c是否存在。

(3)挑戰(zhàn)階段。在多次詢問后，A開始挑戰(zhàn)。A選擇了2個(gè)關(guān)鍵詞集合W0=(w0,1,w0,2,…,w0,t),W1=(w1,1,w1,2,…,w1,t)發(fā)送給S。要求A不能詢問(W0W1)∪(W1W0)中任何關(guān)鍵詞子集的陷門，然后S隨機(jī)選取β∈{0,1}，生成Wβ的密文后發(fā)送給A。

隨后S將陷門發(fā)給A，A調(diào)用搜索算法查看Wβ是否包含W′d。

(5)猜測(cè)階段。A輸出對(duì)β的猜測(cè)β′。如果β′=β則y=gam,否則y=x。攻擊者A不知道主密鑰，構(gòu)造的m次多項(xiàng)式f(x)中的系數(shù)是均勻分布的，A無法從密文以及陷門中得到關(guān)于f(x)系數(shù)或主密鑰的信息。如果y=gam，則對(duì)于i∈{1,2,…,m}，

因此說明生成了正確的陷門。由于A不能詢問集合(W0W1)∪(W1W0)中任何子集的陷門，在這個(gè)前提下算法要分辨β的取值，只能是A從正確陷門中得到了信息。所以，如果A分辨出了β的取值，說明S具有一定優(yōu)勢(shì)能夠判斷y=gam是否成立，這與問題假設(shè)相悖，因此A不具分辨密文的優(yōu)勢(shì)。

本文方案能夠達(dá)到CKA安全。

證畢

□

4.3 性能分析

本節(jié)將構(gòu)造的AECKS方案與現(xiàn)有的加密方案在不同階段的計(jì)算量進(jìn)行詳細(xì)比較，在數(shù)據(jù)外包模式下，考慮到DO和DU的資源有限，存儲(chǔ)能力與計(jì)算能力可能受限，因此要求在加解密階段和陷門生成階段的計(jì)算量盡量小。記P表示雙線性配對(duì)運(yùn)算，H表示橢圓曲線群中的純量乘法，E表示橢圓曲線群中的指數(shù)運(yùn)算，v1表示訪問結(jié)構(gòu)中的屬性個(gè)數(shù)，v2表示搜索用戶具有的屬性個(gè)數(shù)，user表示具有訪問權(quán)限的用戶個(gè)數(shù)，ky1表示文檔關(guān)鍵詞個(gè)數(shù)，ky2表示搜索關(guān)鍵詞個(gè)數(shù)，表1給出了本文AECKS方案與文獻(xiàn)中其他方案的性能分析對(duì)比，包括加密階段、陷門生成、搜索階段的計(jì)算量以及是否實(shí)現(xiàn)連接搜索功能。當(dāng)被搜索關(guān)鍵詞集合包含于文檔的關(guān)鍵詞集合時(shí)能夠進(jìn)行連接搜索，如果搜索的關(guān)鍵詞集合大于文檔關(guān)鍵詞集合，則不存在滿足條件的搜索結(jié)果，因此ky2≤ky1。

Table 1 Performance comparison of previous schemes and AECKS scheme

通過表1可以看出，與同樣基于LSSS共享矩陣的可搜索加密方案[5]相比，本文AECKS方案在加密階段由于與v1以及ky1線性相關(guān)，效率會(huì)有一定損失，但是文檔的關(guān)鍵詞個(gè)數(shù)是有限的，ky1不會(huì)無限增大，而且本文方案實(shí)現(xiàn)了關(guān)鍵詞連接搜索；在陷門生成階段，文獻(xiàn)[5]的方案與v2線性相關(guān)，本文方案與ky1線性相關(guān)，因此計(jì)算量的開銷增加有限。與文獻(xiàn)[13]的方案對(duì)比，AECKS同樣具有連接搜索功能，文獻(xiàn)[13]加密階段的計(jì)算量與ky1和user線性相關(guān)，這說明隨著訪問用戶的增加，計(jì)算量也會(huì)大大增加；本文方案在加密階段的計(jì)算量與ky1和v1相關(guān)，由于用戶的屬性是確定、有限的，因此在用戶增加的情況下，用戶在加密階段的計(jì)算量并不會(huì)線性增加，同樣由于文檔關(guān)鍵詞的個(gè)數(shù)也是有限的，因此在陷門生成階段，本文方案具有較高效率。在搜索階段，文獻(xiàn)[5]的方案僅與v2線性相關(guān)，文獻(xiàn)[13]的方案僅與ky2線性相關(guān)，本文方案與ky1和v2線性相關(guān)，但是由于搜索操作是由云服務(wù)器執(zhí)行，考慮到云服務(wù)器的計(jì)算資源充足，因此不會(huì)對(duì)用戶造成資源負(fù)擔(dān)。同時(shí)本文加密方案支持關(guān)鍵詞連接搜索，當(dāng)數(shù)據(jù)不斷增加時(shí)，不必因?yàn)殛P(guān)鍵詞域重新加密數(shù)據(jù)，因此本文方案是靈活高效的，并且在通信和計(jì)算開銷方面都具有較大的優(yōu)勢(shì)。

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

本文構(gòu)建了一個(gè)支持關(guān)鍵詞連接搜索的屬性加密方案AECKS?；诙囗?xiàng)式方程實(shí)現(xiàn)了文檔的連接搜索，縮小了搜索范圍。同時(shí)用戶在本地生成搜索陷門，避免了密鑰直接暴露給云服務(wù)器從而造成密鑰泄露的風(fēng)險(xiǎn)。采用LSSS共享矩陣實(shí)現(xiàn)了文件的細(xì)粒度訪問控制，實(shí)現(xiàn)了云環(huán)境下的多用戶共享，并且提高了加解密效率，節(jié)省了用戶資源。最后通過嚴(yán)格的安全性分析證明該方案能夠抵抗選擇關(guān)鍵字攻擊。