基于代理的即时属性撤销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.