支持關鍵字更新的基于屬性可搜索加密方案

許盛偉　王榮榮　陳　誠

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

0　引　言

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

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

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

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

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

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

1　基礎知識

1.1　符號說明

表1　符號說明

1.2　定　義

定義1雙線性群

設p、q是素數，G1、G2分別是階為p、q的乘法循環群，雙線性對映射e:G1×G1→G2。如果映射e滿足下述性質：

(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]訪問結構

P={P1,P2,…,Pn}為一個實體集合，A?2p是2p的一個非空子集，對于任意的B,C如果當B∈A且B?C時，有C∈A，那么稱A?2p是單調的。一個訪問結構A是P={P1,P2,…,Pn}的一個非空子集，即A?2p{Φ}。那么A的子集合稱為授權集合，非A的子集合被稱為非授權集合。

定義3[10]訪問樹

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

定義4[10]滿足訪問樹

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

1.3　帶計數器的布隆過濾器

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

圖1　布隆過濾器結構

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

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

圖2　帶計數器的布隆過濾器結構

1.4　應用模型

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

圖3　方案應用流程圖

2　方案設計

2.1　數據擁有者使用ABE公鑰加密算法加密文件

(1) 初始化：選取階為素數p，生成元為g雙線性群G1，隨機選擇α,β∈Zp。可得屬性集加密算法的公鑰為：PK←(G1,g,h=gβ,e(g,g)?)主密鑰為：MSK←(β,gα)。

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

其中:r∈Zp,rj∈Zp。

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

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

2.2　數據擁有者對關鍵字進行加密生成文件索引和陷門

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

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

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

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

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

r′(IQ+εi)+t

(5) 服務器返回結果。

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

2.3　對文件密文的解密運算

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

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

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

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

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

3　方案分析

3.1　正確性分析

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

則：

當S[j]=0時，Q′[j]、Q″[j]、Q[j]三者相等，則：

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

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

同理可證：當在關鍵字集中刪除一些關鍵字時，結果也成立。

上述計算結果標明，利用帶計數器的布隆過濾器產生的索引確實可以實現關鍵字的更新。

3.2　安全性分析

3.2.1關鍵字安全

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

3.2.2密文的保密性

3.2.3明文的保密性

3.3　效率分析

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

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

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

4　結　語

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

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

[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] 馬明軍, 楊亞濤, 王培東,等. 基于屬性的可認證搜索加密方案[J].計算機工程與設計,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] 李新, 彭長根, 牛翠翠. 隱藏樹型訪問結構的屬性加密方案[J]. 密碼學報, 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]. 計算機學報, 2014(5):1017-1024.

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

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

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