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

林 娟,薛慶水,曹珍富

(上海交通大學計算機科學與工程系,上海200240)

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

林 娟,薛慶水,曹珍富

(上海交通大學計算機科學與工程系,上海200240)

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

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

1 概述

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

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

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

2 預備知識

2.1 雙線性配對

令G0,G1為加法循環群,GT為乘法循環群,以上3個群的階均為素數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)可計算性:任取P∈G0,Q∈G1,均存在有效算法可以求得e(P,Q)。

2.2 訪問結構

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

3 模型定義

3.1 方案模型

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

(1)Setup(1λ,n)→(MSK,PK):授權機構調用該初始化算法。輸入安全參數1λ、密文屬性集中屬性數量的最大可能值n,輸出系統公鑰PK和系統私鑰MSK。

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

(3)KeyGen(ID,T,MSK,PK)→SKID:授權機構調用該密鑰生成算法。輸入用戶的唯一身份標識ID∈U(U為所有用戶標識的集合)、訪問結構T、系統私鑰MSK和系統公鑰PK,輸出為用戶ID的私鑰SKID。

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

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

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

3.2 安全模型

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

4 KP-ABE方案

給攻擊者。

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

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

4.1 基本思想

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

4.2 方案具體實現

方案具體實現過程如下:

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

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

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

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

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

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

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

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

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

5 安全性與性能分析

5.1 安全性分析

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

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

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

5.2 性能分析

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

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

6 結束語

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

[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”計劃基金資助項目(2012CB723401);國家自然科學基金資助項目(61170227,61161140320)。

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

2013-10-30

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

中文引用格式:林 娟,薛慶水,曹珍富.基于代理的即時屬性撤銷KP-ABE方案[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.