支持關(guān)鍵字更新的基于屬性可搜索加密方案

許盛偉　王榮榮　陳　誠

(西安電子科技大學(xué)通信工程學(xué)院　陜西 西安 710071) (北京電子科技學(xué)院　北京 100070)

0　引　言

在數(shù)據(jù)爆炸的當(dāng)今社會，數(shù)據(jù)存儲和共享的問題在云技術(shù)的來臨后而得到了很好的解決。但弊端就是用戶消息是明文存儲，并沒有進行加密保護，云存儲管理員可以訪問甚至獲得用戶的數(shù)據(jù)，這樣給用戶帶來了很大的安全隱患。因此，目前部分云存儲中心采用密文存儲方式, 密文存儲可以預(yù)防用戶隱私泄露的風(fēng)險，但是也存在問題。例如：如何實現(xiàn)在云服務(wù)器搜索后能找到想要的數(shù)據(jù)，且不在搜索過程中泄露數(shù)據(jù)信息內(nèi)容。并且加密操作破環(huán)了原先明文數(shù)據(jù)的值以及大小關(guān)系等，其不再具有可供檢索的語義和統(tǒng)計特性，為了解決這些問題，可搜索的加密技術(shù)逐漸產(chǎn)生，并引起了人們的廣泛關(guān)注和大量研究。

Perrig等[1]率先提出可搜索加密技術(shù)的概念，正如字面所體現(xiàn)的那樣，此技術(shù)不僅能實現(xiàn)加密，防止用戶數(shù)據(jù)隱私的泄露，還能通過搜索獲得加密數(shù)據(jù)，具有很好的應(yīng)用行和適應(yīng)性。但是存在的不足就是數(shù)據(jù)搜索者只能檢索自己事先存在云上的密文數(shù)據(jù)。

Boneh等[2]在2004年使用匿名的基于身份的加密方式下設(shè)計出了公鑰可搜索加密方案(PEKS)，可以實現(xiàn)對其他用戶數(shù)據(jù)進行檢索，并在郵件系統(tǒng)中具有很大的應(yīng)用前景。Goh[3]通過把布隆過濾器運用到文件索引中，提出了Z-IDX方案。2011年Cao等[4]提出了支持多關(guān)鍵字排序的密文檢索算法(MRSE)，使用向量內(nèi)積實現(xiàn)對關(guān)鍵字的相似度進行排序，使得可搜索加密的發(fā)展又邁進了一步。

傳統(tǒng)的可搜索加密方案幾乎都是針對“一對一”[5]的通信方式，即關(guān)于關(guān)鍵詞的密文與數(shù)據(jù)查詢者是一對一的關(guān)系。這種方式很顯然不適合關(guān)鍵詞密文可被多個用戶進行查詢的情形。當(dāng)存儲在云上的數(shù)據(jù)資源想要分享給多個用戶時，傳統(tǒng)的做法只能是用每一個用戶的私鑰對數(shù)據(jù)進行加密。然后通過安全信道將不同的密文結(jié)果分別傳送給不同的用戶，用戶通過關(guān)鍵字進行查詢獲得相應(yīng)的檢索結(jié)果。從中可以看出，在這種情況下使用傳統(tǒng)的可搜索加密方案，不僅效率不高還會造成資源的浪費，不適合于實際中應(yīng)用。

2005年Sahai等[6]提出了模糊的基于身份的加密，首次出現(xiàn)了“基于屬性的加密(ABE)”這個概念。用戶的身份不再使用傳統(tǒng)的身份標(biāo)識，而是將用戶所具有的若干屬性來表示其身份，這些屬性可以使用“且、或、非”的關(guān)系聯(lián)系在一起?；趯傩约用?ABE)的實現(xiàn)往往有兩種策略方式：一種是密文策略的基于屬性加密(CP-ABE)，另一種是密鑰策略的基于屬性加密(KP-ABE)。2008年Goyal等[7]通過使用“訪問樹”[8]的概念將KP-ABE轉(zhuǎn)化成CP-ABE，在CP-ABE中通過使用用戶的部分屬性指定一個訪問結(jié)構(gòu)，也就是訪問樹，然后以此訪問結(jié)構(gòu)對數(shù)據(jù)消息進行加密。在解密過程中，只要解密者具有的屬性滿足此訪問結(jié)構(gòu)就可以完成解密。2011年Waters[9]在標(biāo)準(zhǔn)模型下提出了一個CP-ABE系統(tǒng)，并證明了它在D-H假設(shè)下的安全性，在文獻[10]中被證明是具有語義安全的。2014年李雙等[11]構(gòu)造了基于屬性的可搜索加密方案(ATT-PEKS)，并給出了一致性分析和安全性證明。2016年譚彭超等[13]提出利用帶計數(shù)器的布隆過濾器可以增加或刪除關(guān)鍵字。

然而在上述的基于屬性的可搜索加密方案中，文件明文的加密和關(guān)鍵字生成索引過程中都是使用了雙線性對運算，增加了運算時間，而且文件的索引一旦生成將不能更改，限制了生成索引的靈活性。針對以上兩個問題，本文提出了一種改進的基于屬性的可搜索加密算法，文件明文仍使用ABE進行加密，索引和陷門采用對稱加密的思想，并通過引入帶計數(shù)器的布隆過濾器，實現(xiàn)關(guān)鍵字的更新。

1　基礎(chǔ)知識

1.1　符號說明

表1　符號說明

1.2　定　義

定義1雙線性群

設(shè)p、q是素數(shù)，G1、G2分別是階為p、q的乘法循環(huán)群，雙線性對映射e:G1×G1→G2。如果映射e滿足下述性質(zhì)：

(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[10]訪問結(jié)構(gòu)

P={P1,P2,…,Pn}為一個實體集合，A?2p是2p的一個非空子集，對于任意的B,C如果當(dāng)B∈A且B?C時，有C∈A，那么稱A?2p是單調(diào)的。一個訪問結(jié)構(gòu)A是P={P1,P2,…,Pn}的一個非空子集，即A?2p{Φ}。那么A的子集合稱為授權(quán)集合，非A的子集合被稱為非授權(quán)集合。

定義3[10]訪問樹

用T表示一顆訪問樹，樹中的每個非葉子結(jié)點具有子節(jié)點和閾值的，用numx表示結(jié)點x的子結(jié)點的數(shù)目，用kx表示結(jié)點x的閾值，并且:0≤kx≤numx；當(dāng)kx=1時，表示“或”門；當(dāng)kx=numx時，表示“與”門。樹中的每一個葉子節(jié)點表示一個屬性，即kx=1。除此之外，parent(x)代表結(jié)點x的父結(jié)點。att(x)表示葉子結(jié)點x所代表的屬性值。對樹中每個結(jié)點的子結(jié)點進行編號1～num，其中編號的函數(shù)用index(x)來表示。

定義4[10]滿足訪問樹

用T表示一顆訪問樹，其根節(jié)點用R來表示，那么訪問樹T可以表示成TR，則Tx表示以x為根結(jié)點的子樹。當(dāng)屬性集合S滿足訪問樹Tx時，就有Tx(S)=1?？梢酝ㄟ^遞歸遍歷的方式來計算Tx(S)的值。若x是葉子結(jié)點，當(dāng)且僅當(dāng)att(x)∈S時，有Tx(S)的值為1。若x是非葉子結(jié)點時，則計算它的所有子結(jié)點x′的Tx′(S)，那么至少有Kx的子結(jié)點值為1時，Tx(S)的值為1。

1.3　帶計數(shù)器的布隆過濾器

布隆過濾器(Bloom Filter)是現(xiàn)在計算機中應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)，它由一個很長的二進制向量(或者說是包含多位的位數(shù)組)和若干個獨立的哈希函數(shù)組成，它通過使用哈希函數(shù)將一個元素映射到一個二進制向量中，可以用來檢查元素是否屬于此集合。其原理是位數(shù)組+K個獨立的哈希函數(shù)，初始狀態(tài)時，Bloom Filter是一個包含m位的全部為0的位數(shù)組，例如像S={x1,x2,…,xn}這樣一個n個元素的集合，Bloom Filter使用K個相互獨立的哈希函數(shù)，他們分別將集合中的元素映射到{1,2,…,m}的范圍內(nèi)，對任意一個元素x第i個哈希函數(shù)映射的位置hi(x)就會被置為1(1≤i≤k)。若一個位置經(jīng)過映射被置為1，那么該位置的值就為1，后續(xù)操作將不再影響該位置的值，如圖1所示。

圖1　布隆過濾器結(jié)構(gòu)

如果一個集合中的元素經(jīng)過這些哈希函數(shù)的映射后的所有位都是1，那么就可以認(rèn)為該元素是屬于這個集合的，若存在映射后的位置不為1，也就是0，那么就判定此元素是不屬于這個集合的。因為可能好幾個關(guān)鍵字通過哈希函數(shù)會映射到同一個位置上變?yōu)?，刪掉此關(guān)鍵字可能會影響其他的關(guān)鍵字，但是通過使用counting Bloom filiter就可以實現(xiàn)這個操作。

帶計數(shù)器的布隆過濾器可以支持關(guān)鍵字的增加和刪除操作，當(dāng)多個關(guān)鍵字wi(i=1,2,…)通過k個相互獨立的哈希函數(shù)映射到同一個位置時，對應(yīng)位置的數(shù)將不再是1而是多個映射結(jié)果的和，其原理如圖2所示。其中，x1,x2為原先已經(jīng)存在的關(guān)鍵字，x3為向過濾器中新插入的關(guān)鍵字。

圖2　帶計數(shù)器的布隆過濾器結(jié)構(gòu)

1.4　應(yīng)用模型

本方案的應(yīng)用模型為面向云存儲的可搜索加密系統(tǒng)，主要適用的場景是存放公共通知、消息共享、電子郵件、電子公文等的云存儲系統(tǒng)。云存儲數(shù)據(jù)為容量小且安全性要求較高的應(yīng)用云存儲數(shù)據(jù)。系統(tǒng)包括第三方云存儲服務(wù)器、數(shù)據(jù)擁有者以及數(shù)據(jù)檢索者。數(shù)據(jù)擁有者先將文件進行加密然后選擇關(guān)鍵字進行特定的處理后作為文件的加密索引，最后將加密索引和密文一同上傳到云存儲服務(wù)器。數(shù)據(jù)檢索者如果想獲得所需要的文件，那么在獲得認(rèn)證權(quán)限后，將要搜索的關(guān)鍵字通過特定方式生成查詢向量，加密后生成查詢陷門，并把陷門發(fā)送給云存儲服務(wù)器，服務(wù)器在收到查詢陷門后，通過查詢機制返回給用戶相應(yīng)的密文文件。應(yīng)用模型如圖3所示。

圖3　方案應(yīng)用流程圖

2　方案設(shè)計

2.1　數(shù)據(jù)擁有者使用ABE公鑰加密算法加密文件

(1) 初始化：選取階為素數(shù)p，生成元為g雙線性群G1，隨機選擇α,β∈Zp?？傻脤傩约用芩惴ǖ墓€為：PK←(G1,g,h=gβ,e(g,g)?)主密鑰為：MSK←(β,gα)。

(2) 產(chǎn)生私鑰：把用戶的屬性集S和主密鑰MSK作為輸入，產(chǎn)生用戶私鑰為：

其中:r∈Zp,rj∈Zp。

(3) 密文的加密：使用公鑰PK和訪問樹T加密文件明文消息M，得到密文E。

通過自上而下遍歷的方式為訪問樹中的每個結(jié)點選擇它的多項式qx，qx的階數(shù)dx與這個結(jié)點的閾值kx需滿足dx=kx-1。毋容置疑從根節(jié)點R進行qx的選擇，任取s∈Zp，并令qR(0)=s，其他dR個點的值進行可以任取，那么通過kx個值就可以求得多項式qR。同理，使用相同的方法可以獲得子結(jié)點的qx，qx(0)=qparent(x)(index)，樹T中結(jié)點的集合用Y表示，所以，遞歸結(jié)束后文件密文為：

2.2　數(shù)據(jù)擁有者對關(guān)鍵字進行加密生成文件索引和陷門

下面使用帶計數(shù)器的布隆過濾器采用對稱加密的思想對關(guān)鍵字行加密，作為文件的索引，可以高效跟蹤文件的關(guān)鍵字[14]。

(1) 生成對稱密鑰Sk={S,M1,M2}，m：布隆過濾器的數(shù)組長度。首先隨機選擇m+2維的矩陣M1、M2和長度為m+2的0、1字符串。

(4) 陷門匹配。將要搜索查詢的陷門提交給服務(wù)器后，服務(wù)器將自動和數(shù)據(jù)庫中的索引進行匹配，匹配過程如下：

Q′(I′)T+Q″(I″)T=

(r′Q,r′,t)·(I,εi,1)T=

r′(IQ+εi)+t

(5) 服務(wù)器返回結(jié)果。

(4)中r′(IQ+εi)+t越大，則服務(wù)器使用最大匹配的原則，根據(jù)相似度的匹配結(jié)果進行排序，返回排好序的文件。

2.3　對文件密文的解密運算

當(dāng)用戶接收到文件后，所要做的就是解密操作，對于基于屬性加密的解密算法如下：

通過遞歸遍歷的方式當(dāng)輸入密文E和一個結(jié)點x，當(dāng)輸出為群G2上的一個值時，結(jié)果正確，否則結(jié)果終止。

當(dāng)x為葉子結(jié)點時，令i=att(x)，若i不屬于用戶私鑰對應(yīng)的屬性集時，解密終止。若i是屬于用戶私鑰對應(yīng)的屬性集時，解密如下：

e(gr,gqx(0))=e(g,g)rqx(0)

通過上述分析，我們得到了結(jié)點的解密方法DecryptNode。所以，當(dāng)解密密文時，當(dāng)解密密文時，只需要求出根結(jié)點R的DecryptNode值即可。所以，當(dāng)TR(S)=1時，S為用戶屬性集合。得到DecryptNode(E,R)=e(g,g)rs，接下來就可以恢復(fù)明文了。

3　方案分析

3.1　正確性分析

若將{w1,w2,…,w6}的加密索引與{w7,w8,w9}的加密索引相加，其結(jié)果等同于{w1,w2，…,w9}的加密索引，現(xiàn)證明如下：

則：

當(dāng)S[j]=0時，Q′[j]、Q″[j]、Q[j]三者相等，則：

Q[j]·(I[j]+Ii[j])T=QI

遍歷每個j(j=0,1,…,m+1)，結(jié)果同樣也為QI。

同理可證：當(dāng)在關(guān)鍵字集中刪除一些關(guān)鍵字時，結(jié)果也成立。

上述計算結(jié)果標(biāo)明，利用帶計數(shù)器的布隆過濾器產(chǎn)生的索引確實可以實現(xiàn)關(guān)鍵字的更新。

3.2　安全性分析

3.2.1關(guān)鍵字安全

當(dāng)云存儲服務(wù)器為“honest-but-curious”時，用戶能夠在服務(wù)器上進行檢索。方案中，當(dāng)用戶在檢索時關(guān)鍵字的門限值以及關(guān)鍵詞索引都是通過布隆過濾器經(jīng)過偽隨機函數(shù)加密并填充后形成的向量，一個索引可以產(chǎn)生2(m+2)個未知量，M1、M2有2(m+2)2個未知量，所以服務(wù)器只能判斷出該文件是否包含該關(guān)鍵字，但是卻不能獲得該關(guān)鍵字的具體信息。而且通過在末尾添加隨機數(shù)可以達到一種混淆，預(yù)防了關(guān)鍵字?jǐn)?shù)目的攻擊。

3.2.2密文的保密性

3.2.3明文的保密性

3.3　效率分析

表2為幾種方案與本文方案在計算過程中的運算代價比較。其中n代表屬性中元素的個數(shù)，y代表hash函數(shù)個數(shù)，文獻[10]是基于屬性的加密方案，文獻[12]是基于屬性的可搜索加密方案。

表2　本文方案與原方案效率對比表

本文構(gòu)造的方案與傳統(tǒng)的PEKS(帶關(guān)鍵詞的公鑰加密方案)一樣，即需要存儲文件密文還需要存儲關(guān)鍵字索引。從運算時間上來看，現(xiàn)有的PEKS方案在加密文件和關(guān)鍵詞以及服務(wù)器檢索過程中大量使用雙線性對運算。而本文提出的改進算法是在文件加密時使用了基于屬性的雙線性對運算，在關(guān)鍵字加密和生成查詢向量過程中，使用了帶計數(shù)器的布隆過濾器進行Hash運算以及向量的簡單相乘運算，運算時間較少，索引向量和查詢向量中的關(guān)鍵字?jǐn)?shù)量對搜索時間幾乎沒影響。通過表2就可以看出，與文獻[12]相比，本方案在雙線性對運算和指數(shù)運算上，計算量減少。文獻[10]只能實現(xiàn)對數(shù)據(jù)進行加解密，故計算量最少。本文方案與文獻[10]相比，實現(xiàn)了密文的可搜索，對關(guān)鍵字和陷門進行了加密，但是計算量卻是只有少許的增加，對運算時間幾乎沒影響。所以總體來說，本文方案節(jié)約了運算時間，提高了效率。

4　結(jié)　語

本文提出的改進算法借鑒了對稱加密的思想，對文件進行了基于屬性的公鑰加密。通過發(fā)現(xiàn)文獻[13]中的方案的算法錯誤，并進行了修改，將其應(yīng)用到本方案中，在關(guān)鍵字加密以及生成陷門階段，利用布隆過濾器并分裂生成索引向量和搜索查詢向量。然后利用對稱密鑰進行加密生成加密索引和查詢陷門，舍棄了先前使用的對關(guān)鍵字也使用公鑰加密算法的思想，歸避了使用雙線性對運算。服務(wù)器在進行查詢時，只需進行查詢向量和加密索引的相乘運算即可，降低了服務(wù)器檢索的時間消耗，提高了算法的執(zhí)行效率。并且采用帶計數(shù)器的布隆過濾器，允許用戶對已構(gòu)建的文件索引進行增加和刪除，可以實現(xiàn)動態(tài)更新文件索引中的關(guān)鍵字，并保證了數(shù)據(jù)的隱私性。

在文件中對于明文的加密繼續(xù)使用CP-ABE算法，將文件明文用訪問樹進行加密，即使服務(wù)器是不可信的，其數(shù)據(jù)也是安全的。所以，根據(jù)ABE加密算法可以實現(xiàn)一對多的通信優(yōu)勢，數(shù)據(jù)擁有者不用關(guān)心誰可以解密密文，只要解密者的私鑰屬性滿足訪問樹即可。

[1] Song D X, Wagner D, Perrig A. Practical Techniques for Searches on Encrypted Data[C]// IEEE Symposium on Security and Privacy. IEEE Computer Society, 2000:44.

[2] Dan B, Crescenzo G D, Ostrovsky R, et al. Public Key Encryption with Keyword Search[M]// Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:506-522.

[3] Goh E J. Secure Indexes[J]. Submission, 2004.

[4] Cao N, Wang C, Li M, et al. Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data[J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 25(1):222-233.

[5] 馬明軍, 楊亞濤, 王培東,等. 基于屬性的可認(rèn)證搜索加密方案[J].計算機工程與設(shè)計,2016,37(2):358-362.

[6] Sahai A, Waters B. Fuzzy Identity-Based Encryption[M]// Advances in Cryptology—EUROCRYPT 2005. Springer Berlin Heidelberg, 2005:457-473.

[7] Goyal V, Jain A, Pandey O, et al. Bounded Ciphertext Policy Attribute Based Encryption[M]// Automata, Languages and Programming. DBLP, 2008:579-591.

[8] 李新, 彭長根, 牛翠翠. 隱藏樹型訪問結(jié)構(gòu)的屬性加密方案[J]. 密碼學(xué)報, 2016, 3(5): 471-479.

[9] Waters B. Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization[M]// Public Key Cryptography—PKC 2011. Springer Berlin Heidelberg, 2011:53-70.

[10] Bethencourt J, Sahai A, Waters B. Ciphertext-Policy Attribute-Based Encryption[C]// IEEE Symposium on Security and Privacy. IEEE Computer Society, 2007:321-334.

[11] 李雙, 徐茂智. 基于屬性的可搜索加密方案[J]. 計算機學(xué)報, 2014(5):1017-1024.

[12] 李雙. 訪問控制與加密[M]. 機械工業(yè)出版社, 2012.

[13] 譚彭超,張應(yīng)輝,鄭東.支持關(guān)鍵字更新的可搜索加密方案[J].桂林電子科技大學(xué)學(xué)報,2016,36(1):44-47.

[14] 李經(jīng)緯, 賈春福, 劉哲理,等. 可搜索加密技術(shù)研究綜述[J]. 軟件學(xué)報, 2015, 26(1):109-128.