ABE属性加密

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software,2011,22(6):1299−1315 [doi: 10.3724/SP.J.1001.2011.03993] http://www.jos.org.cn ©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563 属性基加密机制∗ 苏金树, 曹 丹+, 王小峰, 孙一品, 胡乔林 (国防科学技术大学 计算机学院,湖南 长沙 410073) Attribute-Based Encryption Schemes SU Jin-Shu, CAO Dan+, WANG Xiao-Feng, SUN Yi-Pin, HU Qiao-Lin (School of Computer, National University of Defense Technology, Changsha 410073, China) + Corresponding author: E-mail: luckycaodan@gmail.com Su JS, Cao D, Wang XF, Sun YP, Hu QL. Attribute-Based encryption schemes. Journal of Software, 2011,22(6):1299−1315. http://www.jos.org.cn/1000-9825/3993.htm Abstract: Attribute-Based encryption (ABE) scheme takes attributes as the public key and associates the ciphertext and user’s secret key with attributes, so that it can support expressive access control policies. This dramatically reduces the cost of network bandwidth and sending node’s operation in fine-grained access control of data sharing. Therefore, ABE has a broad prospect of application in the area of fine-grained access control. After analyzing the basic ABE system and its two variants, Key-Policy ABE (KP-ABE) and Ciphertext-Policy ABE (CP-ABE), this study elaborates the research problems relating to ABE systems, including access structure design for CP-ABE, attribute key revocation, key abuse and multi-authorities ABE with an extensive comparison of their functionality and performance. Finally, this study discusses the need-to-be solved problems and main research directions in ABE. Key words: ABE; access control policy; revocation; key abuse; multi-authorities 摘 要: 由于属性基加密(attribute-based encryption,简称 ABE)机制以属性为公钥,将密文和用户私钥与属性关联, 能够灵活地表示访问控制策略,从而极大地降低了数据共享细粒度访问控制带来的网络带宽和发送结点的处理开 销 .因此 ,ABE 在细粒度访问控制领域具有广阔的应用前景 .在对基本 ABE 机制及其两种扩展 :密钥-策略 ABE(KP-ABE)和密文-策略 ABE(CP-ABE)进行深入研究、分析后,针对 ABE中的 CP-ABE机制访问结构的设计、 属性密钥撤销、ABE 的密钥滥用、多授权机构等难点问题进行了深入探讨和综合分析,对比了现有研究工作的功 能及开销.最后讨论了 ABE未来需进一步研究的问题和主要研究方向. 关键词: ABE;访问控制策略;密钥撤销;密钥滥用;多机构 中图法分类号: TP393 文献标识码: A 随着互联网和分布式计算技术的发展,在分布开放的计算环境中进行数据共享和处理的需求越来越多.资 源提供方需要制定灵活可扩展的访问控制策略,从而控制数据的共享范围,也需要在与用户的通信过程中保证 ∗ 基金项目: 国家高技术研究发展计划(863)(2009AA01A403-2); 国家重点基础研究发展计划(973)(2009CB320503) 收稿时间: 2010-08-25; 定稿时间: 2011-01-31 CNKI 网络优先出版: 2011-03-07 17:14, http://www.cnki.net/kcms/detail/11.2560.TP.20110307.1714.000.html 1300 Journal of Software 软件学报 Vol.22, No.6, June 2011 数据的机密性.大规模分布式应用也迫切需要支持一对多的通信模式,从而降低为每个用户加密数据带来的巨 大开销.传统的基于公钥基础设施(public key infrastructure,简称 PKI)的加密机制能够保护数据机密性,但是存 在 3 个重大缺陷:一是资源提供方必须获取用户的真实公钥证书,否则无法加密;二是资源提供方需要用接收群 体中每个用户的公钥加密消息,并将密文分别发送给相应的用户,导致处理开销大和占用带宽多的问题;三是广 播加密[1−3]技术虽然部分解决了效率问题,却要求资源提供方在加密前获取用户列表,这会产生另外两个次生 问题:分布式难以一次获取接收群体的规模与成员身份;分布式应用列举用户身份会损害用户隐私. 为了解决第 1 个重大缺陷 ,Shamir[4]和 Boneh 等人 [5]提出并实现了基于双线性对技术的身份基加密 (identity-based encryption,简称 IBE)机制,直接使用用户的身份作为公钥,使得资源提供方无需在线查询用户的 公钥证书.Sahai 和 Waters[6]在 IBE 技术的基础上提出属性基加密(attribute-based encryption,简称 ABE)机制,实 现基于属性的加解密,能够进一步解决第 2 个和第 3 个重大缺陷.ABE 机制具有以下 4 个特点:一是资源提供方 仅需根据属性加密消息,无需关注群体中成员的数量和身份,降低了数据加密开销并保护了用户隐私;二是只有 符合密文属性要求的群体成员才能解密消息,从而保证数据机密性;三是 ABE 机制中用户密钥与随机多项式或 随机数相关,不同用户的密钥无法联合,防止了用户的串谋攻击;四是 ABE 机制支持基于属性的灵活访问控制 策略,可以实现属性的与、或、非和门限操作.ABE 机制的高效性、抗串谋性和策略表示灵活性使得它在细粒 度访问控制[7−9](审计日志、付费电视系统等)、定向广播[7]、组密钥管理[10,11]、隐私保护[8,12,13]等领域具有良好 的应用前景. 最初提出的基本 ABE 机制[6]仅能支持门限访问控制策略.为了表示更灵活的访问控制策略,学者们进一步 提出密钥-策略 ABE(KP-ABE)[7]和密文-策略 ABE(CP-ABE)[14]两类 ABE 机制.ABE 机制的复杂性导致其本身 仍存在一些需要解决的重要问题:(1) CP-ABE 机制中的策略由消息发送方制定,使得系统公钥设计的复杂性与 策略复杂性相关,限制了访问结构的设计;(2) ABE 机制中用户密钥与属性相关,属性的动态性增加了密钥撤销 的开销和难度;(3) ABE 机制中用户私钥由授权机构产生,且用户私钥与用户的隐私信息(如 ID)无关,造成了授 权机构和用户都可能泄露用户私钥,无法分清密钥泄露的责任;(4) 多机构 ABE 能够分担授权机构的责任,也满 足分布式应用的多机构协作的需求,对ABE的设计也提出了挑战.针对以上提到的 4个问题,ABE机制已成为近 年来学者们研究的热点,并在密码和安全领域的期刊和学术会议上发布了不少好的研究成果. 本文对当前研究成果进行归纳分析和,第 1 节给出本文符号和术语定义,详细阐述基本 ABE,KP-ABE 和 CP-ABE,并指出 ABE 中的难点问题.针对这些难点问题,第 2 节分析比较 CP-ABE 访问结构设计的与门、树 和线性秘密共享机制(linear secret sharing scheme,简称 LSSS)矩阵技术.第 3 节阐述 ABE 的 3 种属性撤销机制, 即间接撤销、直接撤销以及混合撤销模式的主要算法.第 4 节对比分析防止密钥滥用的 CP-ABE 和 KP-ABE 技 术.第 5 节分别介绍多机构 ABE 中采用与不采用中央授权机构的系统结构.最后进行总结,并指出 ABE 的未来 可能研究方向. 1 ABE 机制 ABE 属于公钥加密机制,其面向的解密对象是一个群体,而不是单个用户.实现这个特点的关键是引入了属 性概念.属性是描述用户的信息要素,例如:校园网中的学生具有院系、学生类别、年级、专业等属性;教师具有 院系、职称、教龄等属性.群体就是指具有某些属性值组合的用户集合.例如,计算机学院本科生就是指院系属 性值为计算机学院、学生类别属性值为本科生的一个群体. ABE 使用群体的属性组合作为群体的公钥,所有用户向群体发送数据使用相同公钥.上例中,{计算机学院, 本科生}作为向计算机学院本科生发送密文的公钥.而私钥由属性授权机构根据用户属性计算并分配给个体. 1.1 术语定义 本文用到的符号见表 1.ABE 机制通过访问结构表示策略,以双线性对为技术基础,并基于各种数学难题和 假设构建安全性.下面分别给出本文基本概念的形式化定义. 苏金树 等:属性基加密机制 1301 定义 1(访问结构[15]). 假定{P1,P2,…,Pn}是参与方的集合, 1 2{ , ,..., }2 nP P PP = .访问结构A是{P1,P2,…,Pn}的非空 子集,即A⊆P\{∅}.若访问结构A是单调的,则∀B,C,若 B∈A且 B⊆C,那么 C∈A. 定义 2(双线性对[5]). 映射 e:G1×G1→G2 若满足下列特征就是双线性对:(1) 双线性:∀a,b∈Zq,∀f,h∈G1,都有 e(f a ,hb)=e(f,h)ab,称映射 e:G1×G1→G2 是双线性的;(2) 非退化性:∃f∈G1,使 e(f,f)≠1;(3) 可计算的:∀f,h∈G1,存在一 个有效的算法计算 e(f,h).注意:e(*,*)是对称操作,即 e(f a ,hb)=e(f,h)ab=e(f b ,ha). 定义 3(计算 Diffie-Hellman(CDH)问题[16]). 随机选择 *, qa b Z∈ ,给定三元组(g,ga,gb),计算 gab. 定义 4(判定双线性 Diffie-Hellman(DBDH)问题[16]). 随机选择 * 2, , ,qa b c Z R G∈ ∈ ,给定元组(g,ga,gb,gc,R),判 断等式 e(g,g)abc=R 是否成立. 定义 5(判定线性(D-Linear)问题[17]). 随机选择阶为 q 的群 G 的生成元 g,f,v,随机选择指数 a,b∈Zq,R∈G,给 定元组(g,f,v,ga,f b ,R),判断等式 va+b=R 是否成立. 定义 6(选择密文攻击(IND-CCA)游戏[16]). 敌手和受挑战者进行如下交互:(1) 受挑战者对加密进行 系统建立,输出公私钥对,并将公钥交给敌手;(2) 敌手可以向受挑战者进行一些解密询问,受挑战者解密密文,返 回结果给敌手;(3) 敌手选择两个明文M0,M1,然后发送给受挑战者.受挑战者投掷一个公平硬币 b∈{0,1},对明文 Mb 加密,得到密文 C*并发送给敌手;(4) 敌手可以继续向受挑战者进行一些同步骤(2)中的解密询问,但询问密 文不能为 C*;(5) 最后,受挑战者必须回答 0 或者 1(记为 b′),作为对密文 C*的猜测. 若 b′=b,则敌手在该游戏中获胜.敌手在游戏中的优势定义为 Pr[b′=b]−1/2. 若在上面的交互中,敌手不能进行任何解密询问,则此游戏称为选择明文攻击(IND-CPA)游戏.对于一个加 密方案,如果任意概率多项式时间(PPT)的敌手在上述游戏中的优势是可忽略的,则称该加密方案是 IND-CCA 安全,简称 CCA 安全.对应选择明文攻击游戏,称为 IND-CPA 安全,简称 CPA 安全.CPA 安全是公钥加密机制的 最基本要求,CCA 安全是公钥加密机制更强的安全性要求.目前所提出的 ABE 方案基本上都是 CPA 安全,但很 多达不到 CCA 安全. Table 1 Notations 表 1 符号说明 Notation Definition Notation Definition Gi Group or operation in group(exponentiation,multiplication) (i=1,2), g is a random generator of G1 Zq Group{0,…,q−1} under multipli- cation modulo q. q is a prime Ce e operation, e denotes bilinear pairing n Number of attributes in system N′ 1 n iiN n=′ = ∑ is the total number of possible value of attributes, where attribute i has ni possible values AC Attributes with ciphertext C AAk The kth authority, k∈{1,…,N}, N denotes the number of authorities Ak Attributes managed by AAk S Least interior nodes satisfying an access structure(include the root) Au Attributes of user u L* Bit-Length of element in * |*| Number of elements in * 1.2 ABE基本机制 ABE 访问控制系统的参与实体包括授权机构和用户.授权机构监管属性并为用户颁发属性密钥;用户分为 消息发送方和接收方.Sahai 和 Waters[6]提出基本 ABE(fuzzy IBE),系统中的每个属性用散列函数映射到 *qZ 中, 密文和用户密钥都与属性相关.该机制支持基于属性的门限策略,即只有用户属性集与密文属性集相交的元素 数量达到系统规定的门限参数时才能解密.例如,图书馆中某论文的属性集为{计算机,安全,英文,博士},且该论 文的属性加密门限参数为 2,则属性集为{计算机,路由,博士}的用户可以访问该论文,而属性集为{机械,博士}的 用户无法访问该论文. 基本 ABE 机制包括 4 种算法:Setup,Extract,Encrypt,Decrypt.系统初始化时根据安全参数运行 BDH 参数生 成器[5],产生两个阶为素数 q 的群 G1,G2,以及双线性对 e:G1×G1→G2.d 为门限参数. (1) Setup(d):授权机构执行,选择 y,t1,…,tn∈Zq,系统公钥 PK 为 11( ,..., , ( , ) )ntt ynT g T g Y e g g= = = .主密钥 MK 1302 Journal of Software 软件学报 Vol.22, No.6, June 2011 为(y,t1,…,tn). (2) KeyGen:授权机构执行,生成用户 u 的私钥.随机选择一个(d−1)次多项式 p,令 p(0)=y,用户私钥 SK 为 ( ){ } . u itp i i i AD g ∀ ∈= (3) Encrypt:发送方执行,用属性集 AC 加密消息 2M G∈ .随机选择 s∈Zq,密文为  ( , ( , ) ,{ } ).i C t ss ys C i i AA E Y M e g g M E g ∀ ∈= = =   (4) Decrypt:接收方执行.若|Au∩AC|>d,则选择 d 个属性 i∈Au∩AC,计算 e(Ei,Di)=e(g,g)p(i)s,再用拉格朗日插 值找到 Ys=e(g,g)p(0)s=e(g,g)ys,得到 M=E/Ys. 上述机制中,KeyGen 算法采用 Shamir 门限秘密共享机制[18],将秘密 y 嵌入到 SK 的各个构件 Di 中,实现门 限策略;SK 与随机多项式 p 有关,使得不同用户无法结合私钥实施串谋攻击.Encrypt 算法采用双线性对加密消 息,并且密文构件 Ei 与属性相关,从而规定了解密必须的属性;随机数 s 可以防止多次加密情况下用户首次解密 成功即可解密后续密文的问题.在上述基本 ABE 机制中,PK 与系统属性数目线性相关,幂运算次数和双线性对 数目较多.Pirretti 等人[19]和 Baeky 等人[20]提出了性能更优的算法. 基本 ABE 只能表示属性的“门限”操作,且门限参数由授权机构设置,访问控制策略并不能由发送方决定. 而许多现实应用需要按照灵活的访问控制策略支持属性的与、或、门限和非操作,实现发送方在加密时规定访 问控制策略.由于基本 ABE 无法支持灵活的访问控制策略,Goyal 等人[7]提出由接收方制定访问策略的 KP-ABE 机制,支持属性的与、或、门限操作.Bethencourt 等人[14]提出由发送方规定密文的访问策略的 CP-ABE 机制.图 1 和图 2 分别说明了 KP-ABE 和 CP-ABE 的工作流程. KP-ABE 机制[7]如图 1 所示,用户密钥采取树结构描述访问策略 Au-KP,树的叶节点集合为 Au.密文与属性集 AC 相关,只有 AC 满足 Au-KP,用户才能解密密文.KP-ABE 与基本 ABE 机制的区别在于 KeyGen 和 Decrypt 算法. KeyGen 算法仍采用秘密共享机制,采取自顶向下的方式为树中每个节点 x 定义一个次数比节点的门限值小 1 的随机多项式 px,令 px(0)=pparent(x)(index(x)),其中,parent(x)表示 x 的父节点,index(x)表示 x 的父节点给 x 的编号. 而根节点 r 的 pr(0)=y,使得主密钥 y 分散到对应于叶节点的私钥构件 Di 中.Decrypt 算法对访问策略树自底向上 采用递归过程解密每个节点,得到恢复明文所需的秘密值.图 1 中,AC 满足策略 Au1-KP,解密需计算的树中内部节 点集合 S 为{AND}. 由于共享机制不支持属性的“非”操作,Ostrovsky 等人[21]采用 Naor 和 Pinkas[22]的广播撤销机制实现表示 “非”的 KP-ABE 机制,策略表示更加灵活.但是该机制的密文和用户密钥大小,加解密开销都翻倍.Lewko 和 Waters[17]改进 OSW07[21]的算法,缩短系统公钥长度,但增加了密文长度. AC: {comedy,English,USA} Sender 1) Setup: PK, MK Reciver 1 Reciver 2 3) Encrypt(PK,M,AC): C 2) KeyGen(PK,MK,Au-KP): SK Ac satisfies Au1-KP? Decrypt, get M Ac satisfies Au2-KP? Fail USA Au1-KP 4) Decrypt(C,SK,PK) action Au2-KP M AC AND comedy AND English Yes No Au-KP PK, SK PK Authority Fig.1 KP-ABE illustration 图 1 KP-ABE 机制示意图 CP-ABE 机制[14]如图 2 所示,密文采取树结构描述访问策略 AC-CP,实现由消息发送方决定的访问控制策略. 苏金树 等:属性基加密机制 1303 CP-ABE 中,用户密钥与属性集 Au 相关,只有 Au 满足 AC-CP,用户才能解密密文.CP-ABE 与基本 ABE 的算法不同, 且 PK 和 MK 的长度与系统属性数目无关.CP-ABE 的 KeyGen 算法采用两级随机掩码方式防止用户串谋,用户 私钥构件与第 2 级随机数相关.Encrypt 算法中,访问树的实现方式与 KP-ABE[7]的 KeyGen 算法相似,区别是 pr(0)=s,并且叶节点对应密文构件 Ei.Decrypt 算法与 KP-ABE[7]类似,但双线性对操作数目翻倍.图 2 中,Au1 满足 AC-CP,解密需计算的树中内部节点集合 S为{OR,2-of-3,AND}.Ostrovsky 等人[21]也可以实现表示“非”的 CP-ABE 机制. Authority Sender 1) Setup: PK, MK Reciver 1 Reciver 2 AC-CP 2-of-3 AND OR route cryptlogy 3) Encrypt(PK,M,AC-CP): C PK Au1: {doctor,attack,cryptology} Au2: {master, cryptology, analyze} 2) KeyGen(PK,MK,Au): SK Au1 satisfies AC-CP? Decryt, get M Fail 4) Decrypt(C,SK,PK) attack doctor master Au2 satisfies AC-CP? M AC-CP PK, SK Au Yes No Fig.2 CP-ABE illustration 图 2 CP-ABE 机制示意图 上述 3 种 ABE 算法在复杂性假设、策略灵活性和适用范围方面有着明显的差别.基本 ABE[6]和 KP-ABE[7] 均采取 DBDH 假设,而 CP-ABE[14]采取一般群模型.基本 ABE 仅表示门限策略,适用于对策略要求简单的应用. KP-ABE和CP-ABE机制支持复杂策略,适用于细粒度数据共享的应用.KP-ABE机制中,用户规定对接收消息的 要求,适用于查询类的应用,如付费电视系统、视频点播系统、数据库访问等;而 CP-ABE 机制中,发送方规定访 问密文的策略,适合访问控制类应用,如社交网站的访问、电子医疗系统等.3 种基本机制的比较见表 2. Table 2 Comparision of basic ABE, KP-ABE and CP-ABE 表 2 基本 ABE,KP-ABE 和 CP-ABE 的比较 System Ciphertext User’s secret key Encrypt Decrypt Policy Basic ABE[6] 1 2| |C G GA L L+ 1| |u GA L |AC|G1+2G2 dCe+2dG2 Threshold KP-ABE[7] 1 2| |C G GA L L+ 1| |u GA L |AC|G1+2G2 |AC|Ce+2|S|G2 And, or, threshold CP-ABE[14] 1 2(2 | | 1)C G GA L L+ + 1(2 | | 1)u GA L+ (2|AC|+1)G1+2G2 2|Au|Ce+(2|S|+2)G2 And, or, threshold 1.3 ABE难点问题与研究内容 算法的正确性和安全性、密钥管理、可扩展性是安全协议研究的核心问题.ABE 机制采用访问结构表示访 问策略,而策略的灵活性会导致访问结构的复杂.当前的 KP-ABE 实现了复杂的访问结构,支持灵活的访问策略, 并基于 DBDH 假设达到 CPA 安全.而 CP-ABE 中策略的灵活性使得系统公钥设计复杂,限制了访问结构的设计. ABE 系统中,属性的动态性增加了密钥撤销的复杂性;且属性密钥与用户标识无关,导致无法预防和追踪非法用 户持有合法用户的私钥(盗版密钥).而大规模的分布式应用需要 ABE 机制支持多机构协作,以满足可扩展性、 容错性的需求.这些因素给 ABE 的研究带来了挑战,主要包括以下几个方面: (1) CP-ABE 机制访问结构设计难.KP-ABE 的系统公钥以及与复杂访问结构相对应的用户私钥都由授权 机构生成,密文的解密只由授权机构控制.而 CP-ABE 的系统公钥由授权机构产生,访问结构由加密者设计,密文 的解密由授权机构与加密者共同控制.因此在 CP-ABE 中,访问结构的复杂度增加了系统公钥设计的复杂性,从 1304 Journal of Software 软件学报 Vol.22, No.6, June 2011 而增加了采用标准的复杂性假设证明机制安全性的难度,使访问结构的设计受限; (2) 属性密钥撤销开销大.ABE 中,用户密钥与属性相关,而系统的动态变化经常引起属性失效或从属关系 变更,因而 ABE 属性密钥的撤销成为研究重点.ABE 的属性密钥撤销分为 3 种情况:整个用户的撤销、用户的 部分属性撤销和系统属性的撤销.撤销用户需作废该用户的密钥,而不影响未撤销的用户;撤销用户的某个属 性,不能影响具备该属性其他用户的权限;系统属性撤销影响具有该属性的所有用户.ABE 中,属性与用户的多 对多关系增加了支持上述 3 种撤销需求的属性密钥撤销机制的设计难度; (3) ABE 的密钥滥用.ABE 中,用户私钥只与用户属性相关,而与用户的任何特定信息无关,无法防止盗版密 钥的产生.除了用户会泄露自己的私钥外,掌握所有用户私钥的授权机构也可能透露合法用户的私钥.故在出现 盗版密钥时,无法确定是用户还是授权机构泄露了私钥,责任追究困难.盗版密钥难预防和难界定责任,使 ABE 机制中的密钥滥用问题尤为突出,难以解决; (4) 多机构下的用户授权.基本 ABE 属于单授权机构情形,不能满足大规模分布式应用对不同机构协作的 需求;授权机构必须完全可信,违背了分布式应用要求信任分散的安全需求;授权机构管理系统中所有属性,为 用户颁发密钥,工作量大,成为系统的性能瓶颈.多授权机构 ABE 不仅能够满足分布式应用的需求,而且可将单 授权机构的信任和工作量分散到系统的所有授权机构上,故研究多机构情况下的 ABE 是必要的.但是,每个授 权机构独立颁发密钥和用户密钥准确性的需求,给多机构 ABE 的研究带来了挑战. 当前,ABE 的研究工作分为 ABE 机制、ABE 的撤销机制、ABE 的可追责性以及多授权机构 ABE 机制, 重点研究内容如图 3 所示.根据图 3 中研究内容的分类,下面主要分析 ABE 的研究进展. Fig.3 Research of ABE 图 3 ABE 研究内容 2 CP-ABE 的访问结构设计 CP-ABE 机制中,加密者控制访问策略,策略越复杂,系统公钥设计得也越复杂,机制的安全性证明越困难.为 达到标准复杂性假设下的 CPA 安全,CP-ABE 的主要研究工作都集中于表示访问策略的访问结构的设计.根据 采取的访问结构不同,CP-ABE 的研究工作分为“与”门、访问树和 LSSS 矩阵 3 类. 2.1 “与”门访问结构 Cheung 和 Newport[10]采用“与”门表示访问策略,首次在 DBDH 假设下证明 CP-ABE 机制的安全性.之后, Nishide 等人[23]和 Emura 等人[24]在 CN07[10]的基础上分别实现了策略的隐藏和效率的提高. CN07[10]最先基于 DBDH 假设构建 CPA 安全的 CP-ABE 机制,并采用 CHK[25]技术扩展到 CCA 安全.引入 文字 i 表示属性 i 与其非¬i,访问结构为文字上的与门,不出现在与门中的系统属性用无关紧要表示.Setup 算法 中,随机选择 y,t1,…,t3n∈Zq 作为主密钥,系统公钥中的 Tk 由 3 部分组成,分别对应属性在与门中为正、非 Research of ABE ABE schemes KP-ABE CP-ABE Basic ABE Multi- authorities ABE Accountability of ABE Revocation schemes of ABE Direct revocation Indirect revocation Hybrid mode With CA Without CA Trusted CA Honest but curious CA Anonymity No anonymity KP-ABE CP-ABE Hidden policy Published policy Authority Semi-trusted third party AND gate Tree LSSS matrix Two values per attribute Several values per attribute Tree without bound Bounded tree 苏金树 等:属性基加密机制 1305 和无关紧要的情况.KeyGen 算法为每个系统属性 i 选择一个随机数 ri,令 1 , n y r iir r D g − == =∑ % ;并根据 i 与用户属 性集 A u 的关系生成密钥构件 / ( )i ir ti uD g i A= ∈ 或 / ( )i n ir ti uD g i A+= ∉ ;然后计算 2/i n ir tiF g += ,组成用户私钥 {1,..., }( ,{ , } )i i i nSK D D F ∈= % .Encrypt 算法选择随机数 s 加密消息,并根据系统属性 i 与密文属性集 AC 的关系生成密 文构件 si iE T= (i∈AC 且 i=i)或 si n iE T += (i∈AC 且 i=¬i),而 i∉AC 时, 2si n iE T += .Decrypt 算法根据 AC 中每个属性与 Au的关系选择私钥构件进行解密运算.但访问结构仅实现了属性的“与”和“非”操作,并且 PK 和密文的大小以及 加/解密时间都与系统属性数目线性相关,效率低. 基于 DBDH 和 D-Linear 假设,Nishide 等人[23]提出抗串谋的、策略隐藏的 CP-ABE 机制.系统属性有多个 候选值.访问结构采用“与”门,每项可以是对应属性候选值集合的一个子集.发送方根据访问结构中各项对系统 属性取值的不同要求产生两部分密文构件,Decrypt 算法根据用户属性集中各项的值选择相应的密文构件解密, 从而隐藏密文策略.采取 BW07[26]技术使接收方获取解密成功与否的消息,但增加了密文和用户密钥长度以及 解密开销.Emura等人[24]基于 DBDH假设,采用与 NYO08[23]相同的访问结构,首次提出密文长度不变的 CP-ABE 机制,提高了算法效率.上述两种算法仅支持属性的与操作. 2.2 树访问结构 提出 CP-ABE 机制的 BSW07[14]采用树结构表示灵活的访问控制策略,但其安全性证明仅基于一般的群假 设.为了在 DBDH 假设下实现策略灵活的 CP-ABE 机制,Goyal 等人[27]和 Liang 等人[28]采用有界树结构.Ibraimi 等人[29]采用一般的访问树结构,消除了界限条件的约束. Goyal 等人[27]基于 DBDH 假设提出有界的密文-策略属性基加密(BCP-ABE),提供一种将 KP-ABE 转换为 CP-ABE 的方法,支持任何有界多项式大小的访问公式(包括与、或和门限操作).主要技术与 GPSW06[7]类 似.Setup 算法规定参数(d,c),d 为访问树最大高度,c 为树中非叶节点的子女节点最大数目.同时,构造一棵(d,c)- 通用访问树 Tu,然后根据 Tu 生成 PK 和 MK.安全性证明中,(d,c)控制了攻击者的询问能力.Encrypt 算法将(d,c)- 有限访问树 T 转换为(d,c)-有限标准访问树 Tn,然后构造 Tn 到 Tu 的映射,最后根据映射完成加密.但是,标准型转 换添加了大量非叶节点,增加了加密开销.T 的叶节点高度越不整齐,系统效率越低,因此该方法实际并不可行. Liang等人[28]改进了 BCP-ABE[27]机制,跳过中间标准型的转化,直接构造新的 Tu.T直接映射到 Tu,缩短了系 统公钥、用户私钥和密文的长度,提高了加/解密算法的效率.在 T 的叶节点高度不整齐时,效果显著.另外,该机 制采用 DBDH 假设和不可伪造的一次签名(one time signature,简称 OTS)技术,扩展为 CCA 安全. Ibraimi 等人[29]基于 DBDH 假设,提出一种新思路实现支持属性的与、或和门限操作的 CP-ABE 机制.首先 实现一个基本 CP-ABE 机制,访问结构为由与、或节点组成的 l 叉树(l>1).Encrypt 算法采用模加机制赋值给与 节点的子女节点,直接将秘密值赋给或节点的子女节点.用户的私钥与一个随机数相关,能够防止用户串谋.然 后采用 Shamir 的门限秘密共享技术[18]扩展基本 CP-ABE 机制,得到支持属性与、或、门限操作的 CP-ABE 机 制,其加解密开销低于 BSW07[14]. 2.3 LSSS矩阵访问结构 与 GJPS08[27]采取转换方式实现 CP-ABE 不同,Waters[30]首次直接实现强数值假设下支持属性与、或和门 限操作的 CP-ABE 机制.采用判定性并行双线性 Diffie-Hellman 指数(decisional Parallel Bilinear Diffie-Hellman Exponent,简称 DPBDHE)[31]假设.采用 LSSS 访问结构[15](M,ρ),其中,M 为l×n 矩阵.Setup 算法选择随机数 a, α∈Zq ,h1,…,hn∈G1,令 MK=gα,PK=(g ,e(g,g)α,ga,h1,…,hn).KeyGen 选取随机数 t , ( , ,at tSK K g g L gα= = = | )tx x uK h x A= ∀ ∈ .加密算法选择向量 2( , ,..., ) nn qv s y y Z= ∈r 产生密钥构件.使用 CHK[25]技术能够扩展为 CCA 安 全.但 W08[30]机制的密文长度、加/解密时间都随着访问结构的复杂性线性增长. Lewko 等人[32]采用双系统加密机制[33,34],首先用完全可行的方法实现 CCA 安全的 CP-ABE 机制.访问结构 也采取 LSSS 矩阵,支持任何单调的访问公式表示策略.先构造一次使用 CP-ABE 机制,规定公式中每个属性只 能使用一次;然后将一次使用 CP-ABE 机制转换为属性多次使用的 ABE 机制,Setup 算法规定了属性被使用的 1306 Journal of Software 软件学报 Vol.22, No.6, June 2011 最大次数.转换不会增加密钥和密文的大小.与以往 ABE 机制不同,群 G1,G2 以 3 个不同素数的乘积作为阶,以这 3 个素数为阶的 G1 的子群具有正交性.该机制基于 3 个 3 素数子群判定问题(3P-SDP)[34]证明了 CCA 安全. 2.4 分 析 综上所述,CN07[10]首先提出在 DBDH 假设下可证安全的 CP-ABE.W08[30]最先在 DPBDHE 假设下实现支 持属性“与”、“或”和“门限”操作的 CP-ABE.LOST10[32]提出可行的 CCA 安全的 CP-ABE.表 3 对比分析了各机 制采取的访问结构、支持的策略、安全证明采用的假设和 ID 模型.表 4 比较了各机制中系统公钥、主密钥、 用户私钥和密文的长度.其中,密文的长度不计访问结构.表 5比较了各机制的加解密时间.访问结构为(d,c)-有界 树 T[27,28]的情形下(d≥1,c≥2),用Σ*表示将树*扩展为子女数目都为 c 的树所增节点集合,则 | | | | 1nT TΣ Σ> > .设 LOST10[32]中 3 个素数分别为 q1,q2 和 q3,则群的阶 q′=q1q2q3.ITHJ09[29]中 w′ ⊆ Au 为满足访问结构最小属性集. Table 3 Comparision of security proof and policy complexity in CP-ABE 表 3 CP-ABE 机制的安全证明与策略复杂性对比 Access structure System Assumption Model Supported policy Two values/attribute CN07[10] DBDH Selective And, not NYO08[23] DBDH, D-Linear Selective And AND gate Several values/attribute EMNOS09[24] DBDH Selective And BSW07[14] Group model Adaptive And, or, threshold Tree without bound ITHJ09[29] DBDH Selective And, or, threshold GJPS08[27] DBDH Selective Bounded and, or, threshold Tree Bounded tree LCLX09[28] DBDH Selective Bounded and, or, threshold W08[30] DPBDHE Selective And, or, threshold LSSS matrix LOST10[32] 3P-SDP Adaptive And, or, threshold Table 4 Comparision of size of keys and ciphertext in CP-ABE 表 4 CP-ABE 机制中各密钥与密文长度的比较 System PK MK SK Ciphertext CN07[10] 1 2(3 1) G Gn L L+ + (3 1) qZn L+ 1(2 1) Gn L+ 1 2( 1) G Gn L L+ + NYO08[23] 1 2(2 1) G GN L L′ + + (2 1) qZN L′ + 1(3 1) Gn L+ 1 2(2 1) G GN L L′ + + EMNOS09[24] 1 2( 2) G GN L L′ + + ( 1) qZN L′ + 12 GL 1 22 G GL L+ BSW07[14] 1 23 G GL L+ 1qZ GL L+ 1(2 | | 1)u GA L+ 1 2(2 | | 1)C G GA L L+ + ITHJ09[29] 1 2( 1) G Gn L L+ + ( 1) qZn L+ 1(| | 1)u GA L+ 1 2(| | 1)C G GA L L+ + GJPS08[27] 1 2 1( 1)d d G Gnc c L L − + − + 1( ) q d d Znc c L − + 1 1(| | 1)d du GA c c L − + − 1 2(| | | |)nC T G GA L LΣ+ + LCLX09[28] 1 2 1 1 1 d d G G cn c L L c −⎛ ⎞+ − +⎜ ⎟−⎝ ⎠ 1 1 q d d Z cn c L c −⎛ ⎞+⎜ ⎟−⎝ ⎠ 1 1 | | 1 1 d d u G cA c L c −⎛ ⎞+ −⎜ ⎟−⎝ ⎠ 1 2 (| | | |)C T G GA L LΣ+ + W08[30] 1 2( 2) G Gn L L+ + 1GL 1(| | 2)u GA L+ 1 2(2 | | 1)C G GA L L+ + LOST10[32] 1 2( 2) G Gn L L+ + 1qZ GL L+ 1(| | 2)u GA L+ 1 2(2 | | 1)C G GA L L+ + Table 5 Comparision of computational time in CP-ABE 表 5 CP-ABE 机制的计算开销比较 System Encrypt Decrypt CN07[10] (n+1)G1+2G2 (n+1)Ce+(n+1)G2 NYO08[23] (2N′+1)G1+2G2 (3n+1)Ce+(3n+1)G2 EMNOS09[24] (n+1)G1+2G2 2Ce+2G2 BSW07[14] (2|AC|+1)G1+2G2 2|Au|Ce+(2|S|+2)G2 ITHJ09[29] (|AC|+1)G1+2G2 (|w′|+1)Ce+(|w′|+1)G2 GJPS08[27] 1 2(| | | ) 2|nC TA G GΣ+ + 2(| | | |) 2(| | | |)n nu T e TA C S GΣ Σ+ + + LCLX09[28] (|AC|+|ΣT|)G1+2G2 (|Au|+|ΣT|)Ce+2(|S|+|ΣT|)G2 W08[30] (4|AC|+1)G1+2G2 (2|Au|+1)Ce+3|Au|G2 LOST10[32] (4|AC|+1)G1+2G2 (2|Au|+1)Ce+3|Au|G2 由表 3 可知:在标准假设下,只有 W08[30]和 ITHJ09[29]支持属性的与、或、门限操作;只有 CN07[10]支持属性 苏金树 等:属性基加密机制 1307 的非操作.由表 4 和表 5 可知:EMNOS09[24]的用户私钥和密文最短、加/解密开销最低;ITHJ09[29]的加/解密开销 比 W08[30]低;BSW07[14]的系统公钥和主密钥与系统属性无关,具有最短的系统公钥;W08[30]的主密钥最短.目前 的研究工作仍没有实现基于标准数值理论假设的支持属性与、或、门限和非操作的 CP-ABE 机制. 3 ABE 的属性撤销机制 ABE 中的属性撤销分为用户撤销、用户属性撤销和系统属性撤销 3 种情况.撤销用户时,直接作废该用户 的所有权限;撤销用户属性时,需保证该用户失去该属性对应的权限,而具有该属性的其余用户仍具备此权限; 撤销系统属性时,所有与该属性相关的用户都受影响,执行起来比较简单. 根据撤销由机构还是发送方执行,当前 ABE 撤销机制的研究工作分为间接撤销和直接撤销两类.根据 Attrapadung 和 Imai[35]的定义,在间接撤销模式下,授权机构周期性释放密钥的更新,只有未撤销的用户才能更 新密钥,从而使已撤销用户的密钥无效.在直接撤销模式下,发送者在加密消息时规定撤销列表,直接实现属性 密钥的撤销.间接撤销的优势在于发送者无需获取撤销列表.直接撤销的优势在于所有未撤销用户无需更新密 钥,减轻授权机构的负担.AI09b[35]结合两种撤销模式的优点,提出了混合撤销模式. 3.1 间接撤销 ABE 撤销机制的大部分研究工作都采用间接撤销模式.前期的研究由授权机构执行撤销[14,19,36],加密过程 都与时间有关,属性只有到期失效时才能撤销;更新阶段,授权机构的工作量大.为减轻授权机构的负担并实现 属性的即时撤销,后期工作引入半可信第三方[37,38],但要保证第三方的诚实性. Pirretti 等人[19]最早提出 ABE 机制属性撤销的:每个属性包含一个有效期.授权机构周期性地释放属性 的最新版本,并重新颁发所有用户的密钥信息.若删除系统的某个属性,机构停止发布该属性的最新版本,在周 期性更新所有用户密钥时,不再颁发与该属性对应的密钥构件.如需撤销某个用户的属性,机构撤销用户私钥中 该属性的最新版本.该方法简单,但存在不少缺点:加密方需与机构协商属性有效期;用户需保存每个时间段的 密钥,撤销日期的粒度越细,密钥存储开销越大;属性密钥更新阶段,用户与机构在线交互,授权机构的工作量随 用户数目线性增长,系统的可扩展性不好;属性也无法在到期前撤销. 为消除加密方与授权机构的协调,并降低用户密钥存储开销,Bethencourt 等人[14]提出一种 CP-ABE 的密钥 更新思路.授权机构给每个用户的属性一个终止日期,密文附带时间信息.解密要求用户属性满足密文的访问策 略,且终止日期在密文附带的时间之后.但在密钥更新过程中,用户仍需与授权机构在线交互,授权机构的工作 量与属性到期的用户数量线性相关.另外,该机制不支持属性的即时撤销. Boldyreva 等人[36]采用二叉树提出可撤销的 ABE 机制,支持 KP-ABE 中用户的撤销.每个用户与二叉树的 叶节点相关,密钥更新数量与用户数量为对数关系.用户密钥分为两部分:一部分与访问结构相关,称为私钥,由 授权机构生成;另一部分与时间相关,称为密钥更新,由授权机构公布,对全体用户可见,消除了密钥更新过程中 的在线交互.授权机构撤销用户时,停止公布该用户的密钥更新,密文与属性集和时间相关.这种算法具有 KP- ABE 的抗串谋特性,保证了算法的安全性,但不支持属性的即时撤销. 为了实现属性的即时撤销,Ibraimi 等人[37]