支持連接關鍵詞搜索的屬性加密方案研究

陳思琦，黃汝維

(廣西大學計算機與電子信息學院，廣西 南寧 530004)

1 引言

在云計算模式下，用戶將存儲或者計算任務外包給云服務器，就能夠享受高質量的存儲服務或計算服務。為了保證隱私安全，用戶通常將數據加密后進行存儲。可搜索加密技術使得用戶能夠在不解密的前提下對密文進行檢索操作，用戶將數據加密后存儲在云端，提出搜索請求的用戶利用搜索關鍵字生成陷門，云服務器執行關鍵字搜索任務，然后返回包含該關鍵字的密文。大部分的可搜索加密方案屬于“一對一”通信模式，在云計算環境下，用戶希望能給特定的一部分人分享數據，數據擁有者要么對密鑰進行共享，這顯然會帶來密鑰泄露的可能性；要么每增加1個用戶，均使用該用戶的公鑰對數據進行加密，這使得數據擁有者加密負擔較重；或者通過聚合密鑰等操作，當用戶逐漸增多時，可信授權機構管理密鑰的負擔也會增加。在大部分單關鍵詞可搜索加密方案中，如果第1次搜索返回的結果無法滿足用戶需要，用戶將會使用另外的關鍵詞進行下一輪搜索，這種多次搜索-解密的過程將會花費很大的代價。

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

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

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

2 基礎知識

2.1 雙線性群

設p、q是素數，G1、G2分別是階為p、q的乘法循環群，雙線性映射e:G1×G1→G2。則有：

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

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

(3)可計算性。存在有效的多項式時間算法對任意的x,y∈G1，計算e(x,y)的值。

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

2.3 Shamir秘密共享方案

Shamir秘密共享方案基于拉格朗日多項式插值，設p為素數，共享秘密值為s。通過tt個子密鑰重構得到共享秘密值s，當t′

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

(1)

2.4 線性秘密共享LSSS策略

3 系統模型與方案設計

3.1 系統模型

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

Figure 1 System model圖1 系統模型

3.2 方案定義

支持連接關鍵詞搜索的屬性加密方案AECKS包括下列5個多項式時間算法：

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

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

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

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

(5)Search(CT,Trap)： 由CS執行關鍵詞搜索算法，輸入密文CT和陷門值Trap，如果用戶滿足數據屬主定義的訪問策略且搜索的關鍵詞集合存在，則CS返回對應的搜索結果，否則CS返回0。

3.3 方案設計

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)

對于i∈{ 0,1,…,mp}，計算Hi=gbai，并計算W0=gasgk，W1=gs，構造密文:

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 正確性分析

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

(8)

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

Eroot=-e(g,g)bstu

(9)

當用戶的屬性集滿足數據屬主訪問策略后，云服務器再執行關鍵詞搜索算法判斷關鍵詞是否存在。

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)

如果陷門關鍵詞集合包含于密文中的關鍵詞集合，則能夠還原出該隨機多項式，即:

(13)

因此

e(W0,tok0)=

(14)

等式成立，說明關鍵詞集合存在，則云服務器返回相應的搜索結果。

4.2 安全性分析

4.2.1 抵抗合謀攻擊

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

4.2.2 用戶密鑰安全

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

4.2.3 抵抗選擇關鍵字攻擊

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

下面采用反證法證明。

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

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

隨后S將陷門發給A，A調用搜索算法查看Wβ是否包含W′d。

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

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

本文方案能夠達到CKA安全。

證畢

□

4.3 性能分析

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

Table 1 Performance comparison of previous schemes and AECKS scheme

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

5 結束語

本文構建了一個支持關鍵詞連接搜索的屬性加密方案AECKS。基于多項式方程實現了文檔的連接搜索，縮小了搜索范圍。同時用戶在本地生成搜索陷門，避免了密鑰直接暴露給云服務器從而造成密鑰泄露的風險。采用LSSS共享矩陣實現了文件的細粒度訪問控制，實現了云環境下的多用戶共享，并且提高了加解密效率，節省了用戶資源。最后通過嚴格的安全性分析證明該方案能夠抵抗選擇關鍵字攻擊。