林 娟,薛慶水,曹珍富

(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海200240)

基于代理的即時屬性撤銷KP-ABE方案

林 娟,薛慶水,曹珍富

(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海200240)

屬性撤銷是屬性基加密方案在實(shí)際應(yīng)用中亟須解決的問題,已有支持間接撤銷模式的可撤銷屬性基加密方案存在撤銷延時或需要更新密鑰及密文等問題。為此,提出一種間接模式下基于代理的支持屬性即時撤銷的密鑰策略屬性基加密方案,該方案不需要用戶更新密鑰及重加密密文,通過在解密過程中引入代理實(shí)現(xiàn)撤銷管理,減輕了授權(quán)機(jī)構(gòu)的工作量,其要求代理為半可信,不支持為撤銷用戶提供訪問權(quán)限及解密密文。分析結(jié)果表明,該方案支持細(xì)粒度訪問控制策略,并且可以實(shí)現(xiàn)系統(tǒng)屬性的撤銷、用戶的撤銷及用戶的部分屬性撤銷。

屬性基加密;密鑰策略;訪問控制;半可信代理;屬性撤銷;即時撤銷

1 概述

近年來,屬性基加密(Attribute-based Encryption, ABE)[1]機(jī)制成為公鑰密碼學(xué)的研究熱點(diǎn)之一,具體可分為2類:密鑰策略屬性基加密(Key Policy-ABE, KP-ABE)[2]和密文策略屬性基加密(Ciphertext Policy-ABE,CP-ABE)[3]。ABE內(nèi)在的“多對多”特性使其具備良好應(yīng)用前景,而在實(shí)際應(yīng)用中因存在屬性到期、密鑰泄露、屬性變更等問題需要引入屬性撤銷機(jī)制,因此屬性撤銷成為屬性基加密方案設(shè)計(jì)中必須解決的重要問題。

屬性撤銷機(jī)制按撤銷執(zhí)行者的不同分為直接撤銷[4-5]、間接撤銷[6-9]2類。直接撤銷是指發(fā)送者在加密密文時直接指定撤銷列表。大部分直接撤銷的ABE方案是以廣播加密機(jī)制為基礎(chǔ)構(gòu)造的,但只能實(shí)現(xiàn)用戶的撤銷或者一次加密僅支持一個屬性的撤銷,無法真正實(shí)現(xiàn)細(xì)粒度撤銷。直接撤銷存在發(fā)送者需持有撤銷用戶列表的問題,因此人們更傾向于研究間接撤銷機(jī)制。間接撤銷模式下撤銷由授權(quán)機(jī)構(gòu)或者半可信第三方執(zhí)行。文獻(xiàn)[6]提出了完全二叉樹的撤銷機(jī)制,使得密鑰更新數(shù)量與用戶數(shù)成對數(shù)比,該方案不支持即時撤銷;文獻(xiàn)[7]引進(jìn)半可信第三方持有撤銷列表及部分密鑰的方法,實(shí)現(xiàn)了即時撤銷,該方案需要第三方誠實(shí)且實(shí)時在線;文獻(xiàn)[8]方案是引入半可信代理采用代理重加密技術(shù)更新密鑰密文,降低了授權(quán)機(jī)構(gòu)的撤銷負(fù)荷。間接撤銷模式下大部分方案存在撤銷延時、密文空間大或需要更新密鑰與密文等問題。

本文針對以上撤銷方案的不足,引入半可信第三方實(shí)現(xiàn)了細(xì)粒度的屬性即時撤銷KP-ABE方案。該方案引入半可信代理持有系統(tǒng)所有屬性的撤銷列表,并在密文中附加任意多個屬性的用戶撤銷列表信息,解密者需結(jié)合該代理加密的密文方解密,從而實(shí)現(xiàn)基于代理的即時屬性撤銷。這種方法不需要任何用戶更新密鑰,也不需要對已有的密文進(jìn)行重加密,但要求半可信第三方實(shí)時在線。

2 預(yù)備知識

2.1 雙線性配對

令G0,G1為加法循環(huán)群,GT為乘法循環(huán)群,以上3個群的階均為素?cái)?shù)p,雙線性映射e:G0×G1→GT必須滿足以下條件:

(1)雙線性:對于任意的P∈G0,Q∈G1和任意的a,b∈Zp,e(aP,bQ)=e(P,Q)ab成立。

(2)非退化性:?P∈G0,Q∈G1,使得e(P,Q)≠1。

(3)可計(jì)算性:任取P∈G0,Q∈G1,均存在有效算法可以求得e(P,Q)。

2.2 訪問結(jié)構(gòu)

令P={P1,P2,…,Pn}是n個參與方的集合。如果對于任意集合B,C都有:若B∈且B?C即有C∈,則訪問結(jié)構(gòu)?2P是單調(diào)的。訪問結(jié)構(gòu)是2P的一個非空子集,即?2P?。中的集合稱為授權(quán)集合,不在中的集合稱為非授權(quán)集合。

3 模型定義

3.1 方案模型

該基于代理的即時屬性撤銷KP-ABE方案由可信授權(quán)機(jī)構(gòu)、半可信撤銷代理服務(wù)器(簡稱代理)、發(fā)送者和用戶4個部分組成,其中涉及以下6種概率多項(xiàng)式時間算法:

(1)Setup(1λ,n)→(MSK,PK):授權(quán)機(jī)構(gòu)調(diào)用該初始化算法。輸入安全參數(shù)1λ、密文屬性集中屬性數(shù)量的最大可能值n,輸出系統(tǒng)公鑰PK和系統(tǒng)私鑰MSK。

(2)Encrypt(M,γ,PK)→CT:發(fā)送者調(diào)用該加密算法。輸入明文M、屬性集合γ?(為所有屬性的集合)以及系統(tǒng)的公鑰PK,輸出密文CT(其中包括γ,E′,E″,{Ei}i∈γ)。

(3)KeyGen(ID,T,MSK,PK)→SKID:授權(quán)機(jī)構(gòu)調(diào)用該密鑰生成算法。輸入用戶的唯一身份標(biāo)識ID∈U(U為所有用戶標(biāo)識的集合)、訪問結(jié)構(gòu)T、系統(tǒng)私鑰MSK和系統(tǒng)公鑰PK,輸出為用戶ID的私鑰SKID。

(4)ProxyRekey(MSK,{RLi}i∈A)→{PRKi}i∈A:當(dāng)授權(quán)機(jī)構(gòu)對撤銷參數(shù)初始化或撤銷用戶屬性時調(diào)用該代理撤銷密鑰生成算法,并將輸出結(jié)果傳送給代理。輸入系統(tǒng)私鑰MSK及所有屬性的撤銷列表{RLi}i∈A(其中,每個撤銷列表包含的用戶數(shù)上限為vi),輸出所有屬性的代理撤銷密鑰{PRKi}i∈A。方案限定每次撤銷時代理接收到新的PRKi值就必須刪除舊的PRKi值,即更新PRKi值。

(5)ProxyReEnc({PRKi}i∈γ,{Ei}i∈γ,ID)→{E′i}i∈γ:撤銷代理服務(wù)器調(diào)用該代理密文轉(zhuǎn)換算法,并將輸出結(jié)果傳送給用戶。算法輸入用戶標(biāo)識ID、用戶發(fā)送的部分密文{Ei}i∈γ及該密文屬性集的代理撤銷密鑰{PRKi}i∈γ,輸出用于撤銷運(yùn)算的密文{E′i}i∈γ。該算法在用戶提出解密申請時調(diào)用,因此要求代理服務(wù)器必須實(shí)時在線。

(6)Decrypt(CT,SKID)→M:用戶運(yùn)行該解密算法,輸入密文CT(含γ,E′,E″,{Ei}i∈γ,{E′i}i∈γ)及用戶私鑰SKID。令γ′=γ-{i}ID∈RLi,i∈γ為去除撤銷屬性之后的密文屬性集合,如果γ′滿足用戶私鑰的訪問結(jié)構(gòu)即T(γ′)=1,則解密成功輸出明文M。

3.2 安全模型

一個基于代理的屬性撤銷KP-ABE方案在“選擇集合-選擇明文攻擊模型”下是安全的,如果對于下述的游戲,攻擊者在概率多項(xiàng)式時間內(nèi)的攻擊優(yōu)勢是可忽略的。

4 KP-ABE方案

給攻擊者。

第2階段:與第1階段相同。

猜測階段:攻擊者輸出υ′∈{0,1}。如υ′=υ,則攻擊者獲勝;定義A的攻擊優(yōu)勢為

4.1 基本思想

本文借鑒了文獻(xiàn)[10-11]方案中的設(shè)計(jì)思想,將文獻(xiàn)[12]的廣播撤銷機(jī)制應(yīng)用到文獻(xiàn)[2]的KPABE方案中,運(yùn)用多項(xiàng)式秘密共享技術(shù)實(shí)現(xiàn)了一種支持屬性即時撤銷的KP-ABE方案。本文方案在系統(tǒng)主密鑰中定義了用于撤銷運(yùn)算的vi階多項(xiàng)式Pi,在用戶ID的私鑰中綁定Pi(0)并添加與Pi(ID)相關(guān)的私鑰成分,而代理持有vi個撤銷用戶組成的共享{Pi(Ui,u)}u={1,2,…,vi}所計(jì)算出的部分密文;解密時如果用戶ID的屬性i未撤銷,則可以結(jié)合密鑰及代理轉(zhuǎn)換的密文中的Pi(ID)和{Pi(Ui,u)}u={1,2,…,vi}共vi+1個多項(xiàng)式值求得Pi(0),從而成功解密密文;反之,則{Pi(Ui,u)}u={1,2,…,vi}中包含了Pi(ID),因此只有v個多項(xiàng)式值無法重構(gòu)指數(shù)上的秘密Pi(0),從而該用戶的屬性i撤銷成功。

4.2 方案具體實(shí)現(xiàn)

方案具體實(shí)現(xiàn)過程如下:

(1)Setup(1λ,n):令G0,G1為2個階為素?cái)?shù)p的加法群,g,h分別為G0,G1的生成元,GT是階為素?cái)?shù)p的乘法群,非對稱雙線性配對e:G0×G1→GT(群G1到群G0不存在有效的同態(tài)映射)。系統(tǒng)初始屬性集A中的屬性用Z*p的元素表示,n為密文屬性集γ屬性數(shù)目的最大可能值。首先,授權(quán)機(jī)構(gòu)為每個屬性i∈A隨機(jī)生成一個Zp上的vi階撤銷多項(xiàng)式Pi,之后新增的系統(tǒng)屬性也需要為其添加對應(yīng)的隨機(jī)多項(xiàng)式Pi;其次,隨機(jī)選取元素y∈Zp,g2∈G0計(jì)算e(g2,h)y,另從G0中隨機(jī)選取n+1個元素t1, t2,…,tn+1,令N={1,2,…,n+1},定義函數(shù)T如下:

最后輸出系統(tǒng)公鑰PK為PK=(g2,h,t1,…, tn+1,e(g2,h)y),系統(tǒng)主密鑰 MSK為 MSK=(y, {Pi}i∈A)。

(2)Encrypt(M,γ,PK):該加密算法與原KPABE[2]方案基本相同,本文方案改用非對稱雙線性配對。選擇隨機(jī)值s∈Zp,明M∈GT文在屬性集γ的作用下,輸出密文CT為:

(4)ProxyRekey(MSK,{RLi}i∈A):當(dāng)授權(quán)機(jī)構(gòu)對撤銷參數(shù)初始化或者撤銷用戶屬性時,將對每個系統(tǒng)屬性i∈A創(chuàng)建或更新相應(yīng)的用戶撤銷列表RLi=(Ui,1,Ui,2,…,Ui,vi)。需要注意的是本文方案限定每個屬性對應(yīng)的撤銷用戶數(shù)上限為vi(因多項(xiàng)式的階是固定的,從而限制了每個屬性的撤銷用戶上限),如果屬性i的實(shí)際撤銷用戶數(shù)小于vi,授權(quán)機(jī)構(gòu)隨機(jī)選取Ui,u?U將該撤銷用戶列表填充至vi個用戶,并依次計(jì)算出每個用戶Ui,u∈RLi對應(yīng)的Pi(Ui,u)值。授權(quán)機(jī)構(gòu)將下述代理撤銷密鑰{PRKi}i∈A通過安全信道傳送給撤銷代理服務(wù)器:

{PRKi}i∈A={?Ui,u∈RLi:[Ui,u,Pi(Ui,u)]}i∈A

(5)ProxyReEnc({PRKi}i∈γ,{Ei}i∈γ,ID):代理將根據(jù)解密者發(fā)送的部分密文{Ei}i∈γ和用戶標(biāo)識ID,結(jié)合密文屬性集γ包含的屬性對應(yīng)的代理撤銷密鑰{PRKi}i∈γ,生成用于撤銷運(yùn)算的密文{E′i}i∈γ如下:

(6)Decrypt(CT,SKID):該解密算法將按下述方式遞歸進(jìn)行。對于用戶密鑰訪問樹T中每個葉子節(jié)點(diǎn)x,如果其屬性i∈γ且用戶ID的屬性i未撤銷,即i∈γ′,其中γ′=γ-{i}ID∈RLi,i∈γ,則運(yùn)行:

否則DecryptNode返回⊥。上述計(jì)算等式中使用拉格朗日插值公式至少需要vi+1個不同點(diǎn)的多項(xiàng)式Pi的取值才可計(jì)算出Pi(0)。如果用戶ID的i屬性撤銷即 ID∈RLi,則 λi,IDPi(ID)+∑viu=1λi,uPi(Ui,u)無法求出Pi(0),因此無法解密即完成對用戶的i屬性的撤銷。

對于訪問樹T中的非葉子節(jié)點(diǎn)x,算法如下:對于節(jié)點(diǎn)x的孩子節(jié)點(diǎn)z,調(diào)用DecryptNode(CT,SKID, z)計(jì)算結(jié)果記作Fz,令Sx為任意kx(節(jié)點(diǎn)x的門限值)個Fz≠⊥的子節(jié)點(diǎn)z的集合,如果不存在這樣的集合,則Fx返回⊥,否則Fx計(jì)算過程如下:

5 安全性與性能分析

5.1 安全性分析

本文的基礎(chǔ)KP-ABE[2]方案在“選擇集合-選擇明文攻擊模型”下是可證安全的,下面將對在原KP-ABE基礎(chǔ)上添加了屬性撤銷機(jī)制的方案進(jìn)行簡要的安全性分析。假設(shè)攻擊者在上文所述安全模型定義的攻擊游戲的第二階段之后,能以不可忽略的概率在攻擊游戲中獲勝,則必須可以計(jì)算出e(g2, h)ys。而要得到這樣的配對,攻擊者必須利用包含y的用戶私鑰Dx=g2qx(0)·T(i)rxPi(0)以及包含s的密文E″=hs,通過配對得出:

若要得出e(g2,h)ys,則相當(dāng)于要計(jì)算出e(T(i), h)srxPi(0),但是攻擊者在不滿足挑戰(zhàn)屬性集時無法得到正確的密鑰也無法求出該值。因此,攻擊者不能以不可忽略的概率解密密文。

本文方案的抗共謀安全性主要包含抗屬性共謀攻擊及抗撤銷共謀攻擊。首先方案的密鑰生成算法采用了門限秘密共享機(jī)制,在密鑰Dx中嵌入了秘密y,即密鑰與隨機(jī)多項(xiàng)式q綁定,使得不同的用戶不能結(jié)合私鑰,從而在完成門限策略的同時實(shí)現(xiàn)了抗屬性共謀的目的。其次用戶密鑰中與撤銷多項(xiàng)式相關(guān)的私鑰R′x=hrxPi(ID)也包含了與屬性值相關(guān)的隨機(jī)值rx,因此不同的撤銷用戶無法結(jié)合其私鑰還原撤銷多項(xiàng)式,從而實(shí)現(xiàn)了抗撤銷共謀攻擊。

5.2 性能分析

本文方案對每個系統(tǒng)屬性定義了用戶撤銷列表,因此系統(tǒng)支持一個或任意多個屬性的撤銷。雖然單個屬性的撤銷用戶數(shù)有上限要求,但系統(tǒng)對總體的撤銷用戶數(shù)沒有上限要求。同時方案也支持系統(tǒng)用戶及系統(tǒng)屬性的撤銷,實(shí)現(xiàn)用戶撤銷的方法是將所有屬性的撤銷多項(xiàng)式統(tǒng)一為一個即可,實(shí)現(xiàn)系統(tǒng)屬性撤銷只需要授權(quán)機(jī)構(gòu)將發(fā)送給代理的撤銷屬性對應(yīng)的撤銷列表用戶數(shù)刪除掉一個即可。另外在性能優(yōu)化方面,用戶可以在解密過程中將滿足密鑰訪問結(jié)構(gòu)的最小屬性集的密文發(fā)送給撤銷代理服務(wù)器,從而提高解密效率。

本文方案與文獻(xiàn)[7-8]的方案相同,都是引入半可信第三方作為即時撤銷執(zhí)行機(jī)構(gòu),且支持系統(tǒng)屬性、用戶及用戶部分屬性3種類型的撤銷。以上3個方案都要求半可信第三方必須實(shí)時在線,在本文方案中撤銷權(quán)限由授權(quán)機(jī)構(gòu)控制,撤銷算法由半可信第三方具體執(zhí)行,因此授權(quán)機(jī)構(gòu)只需要生成用戶私鑰及更新撤銷列表時在線,避免了文獻(xiàn)[8]方案中要求第三方與授權(quán)機(jī)構(gòu)都必須實(shí)時在線的局限,減輕了授權(quán)機(jī)構(gòu)的工作量,同時實(shí)現(xiàn)了文獻(xiàn)[7]方案中沒有完成的細(xì)粒度訪問控制。

6 結(jié)束語

本文提出了一種基于代理的支持細(xì)粒度屬性即時撤銷的密鑰策略屬性基加密方案。該方案具有不需要用戶更新密鑰和更新已經(jīng)加密的舊密文等特點(diǎn)。其撤銷效率與系統(tǒng)用戶數(shù)、密文數(shù)量及撤銷頻率無關(guān),適合于系統(tǒng)用戶屬性變更頻繁或者大型的數(shù)據(jù)系統(tǒng)。本文方案的撤銷原理相當(dāng)于在密文中綁定撤銷信息,但通常密文數(shù)量比用戶數(shù)量大,如果可以在密鑰中綁定撤銷信息,則可以提高系統(tǒng)整體效率,這也是下一步工作中需要考慮的問題。

[1] Sahai A,Waters B.Fuzzy Identity-based Encryption [C]//Proc.of EUROCRYPT’05.Berlin,Germany: Springer-Verlag,2005:237-246.

[2] Goyal V,Pandey O,Sahai A,et al.Attribute-based Encryption for Fine-grained Access Control of Encrypted Data[C]//Proc.of the 13th ACM Conference on Computer and Communications Security.New York, USA:ACM Press,2006:456-468.

[3] Bethencourt J,Sahai A,Waters B.Ciphertext-policy Attribute-based Encryption[C]//Proc.of the 2007 IEEE Conference on Security and Privacy.Washington D.C., USA:IEEE Computer Society,2007:322-329.

[4] Attrapadung N,ImaiH.ConjunctiveBroadcastand Attribute-based Encryption[C]//Proc.of Pairing-based Cryptography-pairing Conference.Berlin,Germany: Springer-Verlag,2009:487-496.

[5] Hur J,Noh D K.Attribute-based Access Control with Efficient Revocation in Data Outsourcing Systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2011,22(7):1214-1221.

[6] Boldyreva A,Goyal V,Kumar V.Identity-based Encryption with Efficient Revocation[C]//Proc.of ACM Conference on Computer and Communications Security.New York,USA:ACM Press,2008:547-558.

[7] Ibraimi L,PetkovicM,NikovaS,etal.Mediated Ciphertext-policy Attribute-based Encryption and Its Application[C]//Proc.of the 10th Int’l Workshop on Information Security Applications.Berlin,Germany: Springer-Verlag,2009:157-166.

[8] Yu Shucheng,Wang Cong.Attribute Based Data Sharing with Attribute Revocation[C]//Proc.of ASIAN ACM Conference on Computer and Communications Security. New York,USA:ACM Press,2010:621-629.

[9] Fan C,Huang V,Rung H.Arbitrary-state Attribute-based Encryptionwith DynamicMembership[J].IEEE Transactions on Computers,2014,68(3):1951-1961.

[10] Jahid S,Mittal P,Borisov N.EASiER:Encryption-based AccessControlin SocialNetworkswith Efficient Revocation[C]//Proc.of the 6th ACM Symposium on Information,Computer and Communications Security. New York,USA:ACM Press,2011:234-239.

[11] Jahid S,Borisov N.PIRATTE:Proxy-based Immediate Revocation of ATTribute-based Encryption[EB/OL]. (2012-08-10).http://arxiv.org/pdf/1208.4877.pdf.

[12] Naor M,Pinkas B.Efficient Trace and Revoke Schemes [C]//Proc. of Financial Cryptography. Berlin, Germany:Springer,2001:366-378.

編輯 索書志

Proxy-based Immediate Attribute Revocation KP-ABE Scheme

LIN Juan,XUE Qing-shui,CAO Zhen-fu
(Department of Computer Science and Engineering,Shanghai Jiaotong University,Shanghai 200240,China)

Attribute revocation is crucial to the practical use of Attribute-based Encryption(ABE).Most of the existing revocable ABE schemes under the indirect revocation model suffer in terms of delaying in revocation or updating keys and ciphertexts.To address this,this paper proposes a proxy-based immediate attribute revocation Key Policy(KP)attributebased encryption under the indirect model without issuing new keys or re-encrypting existing ciphertexts.It achieves attribute revocation by introducing a proxy in the decryption process and reduces the burden for the key authority.The proxy is semi-trusted which revokes user access privileges and cannot decrypt ciphertexts.Analysis results show that the scheme supports fine-grained access control policies and achieves three kinds of revocation including system attribute revocation,user revocation and user attribute revocation.

Attribute-based Encryption(ABE);Key Policy(KP);access control;semi-trusted proxy;attribute revocation;immediate revocation

1000-3428(2014)10-0020-05

A

TP309.2

10.3969/j.issn.1000-3428.2014.10.005

國家“973”計(jì)劃基金資助項(xiàng)目(2012CB723401);國家自然科學(xué)基金資助項(xiàng)目(61170227,61161140320)。

林 娟(1980-),女,碩士研究生,主研方向:密碼學(xué),信息安全;薛慶水,副教授、博士;曹珍富,教授、博士、博士生導(dǎo)師。

2013-10-30

2013-11-25E-mail:linzi320@hotmail.com

中文引用格式:林 娟,薛慶水,曹珍富.基于代理的即時屬性撤銷KP-ABE方案[J].計(jì)算機(jī)工程,2014,40(10):20-24.

英文引用格式:Lin Juan,Xue Qingshui,Cao Zhenfu.Proxy-based Immediate Attribute Revocation KP-ABE Scheme[J]. Computer Engineering,2014,40(10):20-24.