基于KP-ABE算法的云存儲可驗證安全刪除方案

朱怡曉 趙 奎

(四川大學網絡空間安全學院 四川 成都 610065)

0 引 言

云計算連接了大規模的存儲和計算資源,吸引大量數據外包到云服務器進行存儲和共享[1]。在不同文獻提出的各種模型中,云服務器被定義為好奇但會誠實執行程序的不完全受信任的實體[2]。由于數據外包存儲會造成數據所有者和數據管理權分離,當用戶想刪除云端數據時,云服務器可能為了潛在利益不按用戶要求徹底銷毀數據[3],如僅使數據對用戶不可見而數據本身仍保留在存儲介質中,從而能夠回收這些數據進行進一步的挖掘和分析或轉賣給第三方,這大大增加了隱私泄露的風險[4]。如何實現數據確定性刪除是云存儲不可忽視但受關注相對較少的一個問題。

確定性刪除旨在使被刪除數據不可恢復[5]。從數據管理角度看,云服務器在執行刪除時可能僅是移除一些索引或鏈接,并沒有真正清除存儲介質上的數據,這就使得數據可能被恢復而導致信息泄露。因此實際應用中,基于密碼學的刪除方式被廣泛采納,通過使數據密文不可解密達到刪除數據的目的[6]。雖然密碼學刪除能夠一次快速刪除大量數據,但文件的加密形式讓內容共享變得不便[7],基于屬性的加密算法能夠實現細粒度訪問控制和一對多文件共享,近年來在云計算中被廣泛應用[8]。Tiplea等[9]提出一種基于雙線性映射的單調布爾電路密鑰策略屬性基加密方案,該方案基于秘密共享和雙線性映射,構造了包含與門、或門和扇出門訪問結構,實現了細粒度的安全訪問控制,并證明了其在標準模型中的選擇性安全性。

針對云環境下數據的確定性刪除問題,國內外研究者先后提出了多種方案，而大部分方案僅通過返回“成功”或“失敗”等結果告知用戶刪除操作的執行情況, 因此用戶無法追蹤驗證,只能無條件相信該結果[10]。Xue等[11]提出基于屬性基加密的可驗證安全刪除方案,半可信云服務器利用Merkle Hash Tree(MHT)在執行刪除后產生一個數據刪除證據,數據擁有者也通過構建新的MHT驗證該證據的有效性,從而驗證數據是否被確定性刪除。但該刪除方案僅支持較簡單的訪問策略,其對應于用戶私鑰的訪問結構由簡單的與門表示,缺乏對靈活的訪問控制策略的支持。

為實現支持靈活訪問策略的細粒度訪問控制、確定性刪除、刪除結果可驗證,本文在文獻[9]和文獻[11]的基礎上,基于KP-ABE算法提出一種云存儲可驗證安全刪除方案。使用屬性集合描述關聯加密數據,引入支持與門、或門和(k,n)閾值門的布爾電路構造用戶私鑰中的訪問結構,通過撤銷訪問數據所必需的屬性使數據無法訪問從而確定性地刪除數據,并利用多分支路徑樹實現刪除的可驗證性。

1 背景知識

1.1 基于屬性的加密

基于屬性的加密(Attribute-based Encryption, ABE)是在非對稱密碼學和基于身份的加密算法的基礎上發展起來的一種非對稱加密方案[12],將一系列屬性和訪問控制策略嵌入密文和用戶私鑰,只有當屬性集合滿足相應訪問規則時才能成功解密。

根據訪問策略部署方式,屬性基加密可分為密鑰策略屬性基加密(KP-ABE)[13]和密文策略屬性基加密(CP-ABE)[14]。在KP-ABE算法中,使用屬性集合關聯標記密文,訪問策略被部署于用戶私鑰,算法由以下四個概率多項式時間算法元組構成。

初始化Setup(s)：輸入安全參數s,輸出公共參數PP和主密鑰MSK。

加密Encryption(R,A,PP)：輸入待加密數據R、密文描述屬性集A和公共參數PP,輸出R對應密文E。

密鑰生成KeyGenerate(AS,MSK)：輸入訪問結構AS和主密鑰MSK,輸出用戶私鑰SK。

解密Decryption(E,SK)：輸入密文E和用戶私鑰SK,若E對應的屬性集合A滿足SK對應的訪問結構AS,則解密密文,輸出明文信息R。

1.2 雙線性映射

G1和G2為兩個階為素數p的乘法循環群,Zp為相應的數域，g為G1的生成元。若映射e：G1×G1→G2是雙線性映射,則其具備下列三個特性[15]。

雙線性(Bilinear)：對任意x,y∈G1;a,b∈Zp,存在e(xa,yb)=e(x,y)ab；

可計算性(Computable)：對任意x,y∈G1,始終存在有效算法e以計算e(x,y)；

非退化性(Non-Degenerate)：e(g,g)是群G2的生成元,且e(g,g)≠1。

1.3 DBDH假設

決策性雙線性Diffie-Hellman假設[16]定義為：給定階為素數p的乘法循環群G1,隨機選擇生成元g(G1,對于任意的元素a,b,c,z∈Zp,給定一個五元組(g,ga,gb,gc,e(g,g)abc),不存在算法能夠在概率多項式時間內以不可忽略的優勢區分e(g,g)abc和e(g,g)z。

1.4 布爾電路

布爾電路由線路和節點組成,其中每個葉節點對應一個屬性取值真值(True或False),內部節點由與門、或門和非門3種邏輯門組成,任意節點的輸出只能作為一個上層節點的輸入[17]。本文將討論支持與門、或門和閾值門的單調布爾電路。其中(k,n)閾值門表示僅當n個輸入中至少有k個輸入被計算為真時,其輸出才為真。與門和或門可分別表示為(2,2)和(1,2)閾值門。

1.5 Shamir秘密共享算法

Shamir秘密共享算法[18]將秘密S分為n個子秘密,任意k個子秘密都可以恢復出S,而任意少于k個的子秘密無法恢復S。

加密過程中,取隨機數a1,a2,…,ak-1,令a0=S,構造多項式f(x)=a0+a1x+…+ak-1xk-1,取n個數x1,x2,…,xn代入多項式得到f(x1),f(x2)…,f(xn)。解密時,任取k個數據(x1,f(x1)),(x2,f(x2)),…,(xk,f(xk)),使用拉格朗日插值多項式計算出唯一的原k-1階多項式,從而恢復出秘密S。

1.6 多分支路徑樹

多分支路徑樹(Large Branching Tree, LBT)是基于哈希值的多叉樹,每個節點有多個兄弟節點但僅有一個父節點,其中葉節點值為數據塊哈希值,而內部節點值則是其所有子節點值的哈希值[19]。在葉節點數量相等情況下,多分支路徑樹的深度遠小于MHT。

圖1展示了9個數據塊集合的多分支路徑樹。每個數據塊元素Ei都具有完整性輔助認證集合,由該元素在到達根節點的路徑上的所有兄弟節點值組成,如E2的完整性輔助認證集合為{h1,h3,h11,h12}。根據元素Ei及其完整性輔助認證集合能夠計算出LBT根值。假設驗證方知道原數據的LBT根值R,當需要驗證某元素完整性時,從證明方獲得對應的輔助認證集合并計算得到樹根值R’,檢查R’是否等于R即可檢查該元素是否被證明方未改變地存儲。因此,多分支路徑樹被廣泛應用于完整性驗證。

圖1 多分支路徑樹示例

2 基于KP-ABE的可驗證刪除方案

2.1 方案模型

為實現云存儲中數據的細粒度訪問控制、確定性刪除和可驗證,提出基于KP-ABE的可驗證安全刪除方案。方案涉及以下四種角色。

1) 數據擁有者：文件的創建者。將數據上傳至云服務器前,數據擁有者先對數據進行加密,并希望在發出刪除指令后數據得到確定性刪除,即此前所有授權訪問的用戶均不能再獲取數據相應信息。

2) 用戶：云服務器存儲數據的訪問者。不同用戶擁有不同私鑰,決定該用戶是否被數據擁有者授權訪問指定文件。

3) 半可信云服務器：具備強大的存儲資源和計算能力的實體。同時,云服務器不完全受信任,可能由于潛在利益對存儲的數據進行窺探或不按數據擁有者要求確定性地刪除數據。

4) 可信授權方：可信任的用戶私鑰和重加密密鑰的派發中心。

數據擁有者在將數據上傳至云服務器前,首先使用對稱加密算法AES加密該數據,然后使用一系列屬性標記加密AES密鑰,再將數據密文和密鑰密文一起上傳到云服務器。可信授權方根據訪問結構為數據擁有者和其他用戶派發私鑰,滿足訪問條件的用戶可正確解密密鑰密文,再通過解密所得AES密鑰解密數據密文。當想要刪除云服務器上的數據時,數據擁有者向可信授權方發送刪除請求,并獲得重加密密鑰。隨后數據擁有者將該重加密密鑰轉發至云服務器,通知云服務器執行刪除操作。完成刪除后,云服務器向數據擁有者返回能夠用于驗證刪除被正確執行的證據。

方案模型如圖2所示。

圖2 方案模型

2.2 具體構造

在方案構建中,為屬性集合引入一個關鍵屬性akey,默認情況下密文屬性集合和授權用戶訪問結構中都含有該屬性并且取值為真。用戶訪問結構最終輸出門為與門,akey作為該門的一個輸入。通過更改關鍵屬性的取值,密文將不再被包括數據擁有者在內所有用戶的私鑰正確解密,從而達到數據刪除的目的。為實現刪除可驗證,數據擁有者和云服務器可基于密文組件創建多分支路徑樹并獲取根值,重加密密文后云服務器將新的根值作為刪除證據發送給數據擁有者進行驗證。方案整體流程為初始化、加密、生成密鑰、解密、請求刪除、生成重加密密鑰、執行刪除、驗證刪除結果。

2.2.1初始化

可信授權方選擇兩個素數階p的乘法循環群G1和G2,雙線性映射e：G1×G1→G2,g為G1的生成元。n為屬性個數,隨機選擇y∈Zp,ti∈Zp,計算Y=e(g,g)y,Ti=gti，其中i∈[1,n]。輸出公共參數PP=(e,g,Y, {Ti}),保留主密鑰MSK=(y, {ti})。數據擁有者選擇隨機數r∈Zp,計算v=gr,生成簽名公私鑰對(sk,pk)。

2.2.2加 密

輸入明文R,數據擁有者使用AES算法加密數據,輸出加密后的數據密文Rk,其中k為AES密鑰。基于公共參數PP,關鍵屬性akey取值為真的密文屬性集A以及AES密鑰k,數據擁有者選擇隨機數s∈Zp,計算C1=k·Ys,C2=gs,C3={?ai∈A,Xi=Tis},輸出密文C=(A,C1,C2,C3),將數據密文Rk和密鑰密文C上傳至云服務器。

加密后,使用哈希函數對C3中元素進行壓縮,將獲得的有序集{H(Xi)}作為葉子節點構建多分支路徑樹,數據擁有者保存樹根值Root并使用私鑰sk對Root進行簽名得到sk(Root)。同時,為數據選擇唯一名稱Dname,記錄C3中關鍵屬性對應的密文元素Xk、Xk對應哈希值在葉節點中的索引index，以及Xk在多分支路徑樹中的完整性輔助認證集合IAAS。為該外包數據生成標簽L=(H(Dname‖Xk‖index))r,上傳(Dname,index,IAAS,L,sk(Root))至云服務器。

2.2.3生成密鑰

輸入主密鑰MSK和用戶訪問結構電路Circuit,可信授權方自頂向下進行遍歷。由于與門和或門均可表示為閾值門,因此基于Shamir秘密共享算法,以y為根秘密沿布爾電路向下構造其子秘密,生成電路連線wirei和元素集合的映射S,輸出相應密鑰D給用戶：

S=Share(y,Circuit)={〈wirei,elements〉}

式中：elements表示數域Zp中的元素；inputwirei表示第i個屬性值節點對應的輸入線路；n為電路總輸入數。Share(y,Circuit)描述如下。

1) 標記訪問結構中所有邏輯門為未訪問狀態,即令F={unvisited,?gate∈Circuit}。

2) 將y賦值給映射S中訪問結構最終輸出線o對應的元素數組,即S(o)={y}。

3) 自頂向下遍歷電路。若當前(k,n)閾值門的狀態F(gate)==unvisited,那么將其更新為visited。該閾值門連接輸出線w和n個輸入線w1,w2,…,wn,對i∈{1,2，…,|S(w)|},選擇隨機數a1,a2,…,ak-1∈Zp,構造秘密共享多項式p(x)=S(w)[i]+a1·x+a2·x2+…+ak-1·xk-1。然后對j∈{1,2,…,n},S(wj).add(p(j))。

2.2.4解 密

用戶從云服務器獲取數據密文Rk和密鑰密文C,基于公共參數PP及用戶密鑰D,創建葉節點編號與元素數組的映射VA及電路連線wirei與元素數組的映射R。對i∈{1,2,…,n}和j∈{1,2,…,|S(wirei)|},若屬性i∈A,執行：

遍歷所有葉節點后,執行秘密重建：

R=Reconstruct(Circuit,VA,gs)

Reconstruct(Circuit,VA,gs)過程描述如下：

1) 令F={unvisited, ?gate∈Circuit}。

2) 對于i∈{1,2,…,n},R(inputwirei)=VA(i)。

3) 自底向上遍歷電路。若當前(k,n)閾值門的狀態F(gate)==unvisited,那么將其更新為visited。該閾值門連接輸出線w和n個輸入線w1,w2,…,wn,判定|R(w1)|=|R(w2)|=…=|R(wn)|并定義length=|R(w1)|,對i∈{1,2,…,length},執行下列操作。

(1) 從R(w1)[i],R(w2)[i],…,R(wn)[i]中隨機選擇k個值Bi1,Bi2,…,Bik,使得?j∈{1,2,…,k}都有Bij!=null成立,其中i1,i2,…,ik代表值非空的gate編號。如果本次取值為i的循環中沒有足夠非空值,則用下一個i繼續。

(2) 對所有j∈{1,2,…,k},計算：

(3)w為輸出線路,計算：

(4)R(w).add(Rw)。

若密文屬性集合滿足該訪問結構,通過重建過程能夠得到R(o)[1]=e(g,g)y·s。根據密文和重建結果,可解密AES密鑰k=C1/R(o)[1],最終通過k解密數據密文Rk。

2.2.5請求刪除

當想要刪除云服務器上的數據時,數據擁有者分別向可信授權方和云服務器發送刪除請求{Dname,akey},請求可信授權方修改密文屬性集中關鍵屬性取值為假。云服務器接收請求后,將文件Dname中對應關鍵屬性akey的相關信息{Xk,IAAS,L,index,sk(Root)}返回給數據擁有者。

通過驗證e(g,L)=e(v,H(Dname‖Xk‖index))是否成立,數據擁有者可判定云服務器發送的Xk是否為akey對應的正確密文元素。若成立,則數據擁有者使用Xk和云服務器發送的IAAS計算LBT樹根值R1,若sk(Root)=sk(R1),則證明該IAAS是正確有效的。

2.2.6生成重加密密鑰

基于刪除請求和主密鑰MSK,可信授權方找到{ti}中對應于關鍵屬性的值tkey,選擇隨機數tkey’,計算rk=tkey’/tkey,返回{Dname,akey,rk}給數據擁有者。接收重加密密鑰后,數據擁有者將該信息轉發給云服務器。

2.2.7執行刪除

基于密鑰密文C和重加密密鑰,云服務器計算Xk’=Xkrk,并替換原始密文中的Xk為Xk’,輸出更新后的密文C’=(A’,C1,C2,C3’)。同時,云服務器計算H(Xk’),更新原LBT獲取新的樹根值Rnew,將其作為刪除證據返回給數據擁有者。

2.2.8驗證刪除結果

為驗證云服務器是否誠實執行刪除操作,數據擁有者使用rk對Xk進行重加密得到Xnew。接收到云服務器發送的刪除證據Rnew后,數據擁有者使用Xnew和此前云服務器發送的IAAS生成樹根Rverify。若Rnew=Rverify,則證明云服務器確實刪除了該數據。

3 安全性分析

定理1若DBDH假設成立,那么不存在敵手能夠在多項式時間內在基于屬性的選擇性模型下成功對方案進行選擇明文攻擊。

本文安全模型中考慮兩種攻擊者：攻擊者A1旨在破壞密文的機密性；攻擊者A2旨在破壞刪除過程中生成的重加密密鑰的機密性。通過反證法假設攻擊者能以優勢ε在CPA游戲中勝出,那么存在模擬者B能以不可忽略的優勢ε/2解決DBDH問題實例。

給定模擬者DBDH問題實例如下：選擇兩個素數p階乘法循環群G1和G2以及雙線性映射e,g為群G1的生成元,隨機選擇a,b,c,z∈Zp；通過擲硬幣結果v決定Zv的值,若v=0則Zv=e(g,g)abc,否則Zv=e(g,g)z。

初始化：攻擊者A(A1,A2)選擇要挑戰的非空屬性集合ω并發送給模擬者B。

設置：對于集合U中的屬性ai,模擬者B分別選擇一個與之對應的隨機數ri∈Zp,然后設置ti如下：若ai∈ω,ti=ri, 否則ti=bri。B將公共參數(e,g,Y,{Ti})發送給A,其中Ti=gti,Y=e(ga,gb)=e(g,g)ab。

階段1：攻擊者進行如下詢問。

密鑰詢問：攻擊者提交訪問結構C給模擬者B以獲得相應密鑰,B針對兩種攻擊者分別進行應答：

1) 對A1,默認其選擇的屬性集合ω不滿足訪問結構C,B執行FakeShare過程將ga作為根秘密進行共享生成私鑰,同時B提供基于秘密gb的密鑰。從A1角度看,密鑰生成流程與原方案相同,若同時通過一組授權屬性和該解密密鑰, Reconstruct過程應返回e(g,g)abc。

采用符號Cw(A1)表示A1對訪問結構C中電路連線w進行評估時的取值,對A1提交的訪問結構C,總是滿足Cw(A1)=0。FakeShare(ga,C)過程描述如下。

(1) 令F={unvisited, ?gate∈C}。

(2) 創建映射S,令S(o)={ga},o為電路C輸出線路。

(3) 自頂向下遍歷電路。若當前(k,n)閾值門狀態F(gate)==unvisited,那么更新為visited。該閾值門連接輸出線w和n和輸入線w1,w2,…,wn,對i∈{1,2,…,|S(w)|},判斷執行：

若Cw(A1)=1,選擇隨機數a1,a2,…,ak-1∈Zp,構造多項式p(x)=S(w)[i]+a1·x+…+ak-1·xk-1。對j∈{1,2,…,n},執行：

若Cw(A1)=0,選擇隨機數a1,a2,…,ak-1∈Zp,構造多項式p(x)=gS(w)[i]+a1·x+…+ak-1·xk-1。對j∈{1,2,…,n},執行：

S=FakeShare(ga,C),私鑰D={Di},Di取值如下：

2) 對A2,默認它能對任何訪問結構C進行私鑰詢問,包括其選擇的屬性集合滿足的訪問結構。通過Share過程對秘密y=ab進行共享,得到S=Share(y,C)及有效密鑰D={Di}={gbS(i, j)/ri|j∈[1, |S(i)|]}。

重加密密鑰詢問：A2發送一個刪除請求{Dname,akey},B隨機選擇rkey’,生成重加密密鑰rk=rkey’/rkey,然后將{Dname,akey,rk}返回給A2。

刪除執行詢問：A2將信息{Dname,akey,rk}提交給模擬者B,B替換原始密文中關鍵屬性對應的密文組件,輸出重加密后的密文CT’。

挑戰：攻擊者A(A1,A2)選擇兩條長度相等的明文m0和m1并發送給模擬者B,B隨機選擇u({0, 1}和Zv({Z0,Z1}以使用Zv來加密mu。

對A1,返回密文CT=(ω,mu·Zv,gs, {Xi=Tic=gcri}i∈ω)。

對A2,B先執行重加密操作撤銷關鍵屬性akey,為其隨機選擇ti’,令tkey=ti’,返回密文CT=(ω’,mu·Zv,gs,{Xi=Tic=gcri}i∈ω’)。

階段2：攻擊者A(A1,A2)進行同階段1的額外詢問,B返回相應結果。

猜測：A輸出猜測結果u’,若u’=u,B輸出v’=0；否則B輸出v’=1。已知A在CPA游戲中勝出的優勢為ε,B的優勢計算如下：

式中：P(v=0)=P(v=1)=1/2。當v=0時Zv=e(g,g)abc,CT是與屬性集合ω相關的有效密文,因此有：

當v=1時Zv=e(g,g)z,C1是來自G2的一個隨機元素,即密文CT與攻擊者選擇的屬性集合ω無關,故有：

綜上可得B在DBDH游戲中的優勢為ε/2,故方案是選擇明文安全的。

4 性能分析

為驗證方案有效性并評估其性能,在Windows 7系統64位計算機上進行相關實驗,具體配置為Intel(R) Core(TM) i7-7700 @3.60 GHz處理器,8 GB RAM。方案基于Java語言并通過調用Java Pairing Based Cryptography(jPBC)庫進行實現,下面從加密解密、生成用戶私鑰及刪除驗證階段評估方案效率,實驗結果均取10次實驗的平均值。

選擇1 MB大小的文件,首先增加密文屬性集合中屬性個數以觀察在各個階段的時間開銷。固定用戶訪問結構布爾電路中邏輯門個數,使密文描述屬性集合元素個數從3開始遞增至15。

圖3給出了用戶加解密時間開銷。可以發現加密時間隨屬性個數增加大致呈線性增加趨勢,同時由于解密階段也與密文屬性集合大小相關,因此解密時間也隨屬性個數增加增大。本文方案在文獻[13]的基礎上提高了訪問結構的靈活性,當屬性個數為15時,加密和解密時間開銷分別為138 ms和88 ms,低于方案文獻[13],且對于用戶是可接受的。

圖3 加密及解密時間開銷

圖4給出了生成用戶私鑰和刪除驗證的時間開銷。由于用戶私鑰所關聯的訪問結構與屬性個數相關,因此隨著屬性個數增多,生成用戶私鑰的時間開銷增大,當屬性個數增至15時,該階段時間開銷為137 ms。在刪除驗證階段,數據擁有者需要執行雙線性對運算,進行重加密和LBT的重構,并對比云服務器作為刪除證據發送的LBT樹根值和驗證階段產生的樹根值。如圖4所示,刪除驗證過程中數據擁有者的時間開銷約為44 ms,且與密文屬性集合元素個數無關。

圖4 生成用戶私鑰及刪除驗證時間開銷

圖5顯示了固定密文屬性集合中屬性個數為15,遞增用戶訪問結構中邏輯門個數從1至14時生成用戶私鑰的時間開銷變化。由于用戶訪問結構中的與門和或門均可用(k,n)閾值門進行表示,且一個閾值門與其等價的若干閾值門在生成插值多項式時的計算量相當,因此在生成用戶私鑰階段,與訪問結構中邏輯門個數無關,可信授權方的時間開銷約為139 ms。

圖5 訪問結構邏輯門數-生成用戶私鑰時間開銷

為分析構建LBT的時間開銷,固定密文屬性個數為15,給出樹的構建時間與其出度的關系如圖6所示。出度為2時,表示結構為二叉樹,對應于文獻[13]中使用的MHT。本文方案中樹的出度大于2,可以看到LBT的構建時間比MHT的構建時間大大減少,同時隨著出度的增加逐漸減小,能夠減輕數據擁有者和云服務器的計算負擔。

圖6 多分支路徑樹構建時間開銷

5 結 語

本文針對云存儲中數據確定性刪除問題,提出一種新的可驗證安全刪除方案。基于KP-ABE算法,通過撤銷訪問密文必需的關鍵屬性和構建多分支路徑樹實現外包數據的安全刪除和刪除結果可驗證,同時引入含(k,n)閾值門的單調布爾電路支持靈活的訪問控制策略。安全性分析證明在基于屬性的選擇性模型下,該方案能夠抵御選擇明文攻擊。進一步實驗結果表明該方案能以可接受的時間開銷實現加解密及刪除驗證,證明了其有效性和實用性。未來可針對數據多副本關聯刪除、批量數據可驗證性刪除方面展開進一步研究。