在线/离线的可追责属性加密方案

张 凯 马建峰 张俊伟 应作斌 张 涛 刘西蒙

1(西安电子科技大学通信工程学院 西安 710071)

2(西安电子科技大学计算机学院 西安 710071)

3(安徽大学计算机科学与技术学院 合肥 230601)

4(新加坡管理大学信息系统学院 新加坡 178902)

(629zhangkai@163.com)

随着云计算技术的快速发展，人们越来越多地将数据存储在云服务器上以减少本地的存储和管理开销.然而，使用云存储服务在给人们带来了极大便捷的同时，也对数据的安全性造成了威胁.远端云服务器可能会查看甚至出售用户的敏感数据以获取商业利益.因此，利用加密技术来保护用户的敏感数据是非常必要的.传统的公钥加密技术能够保证用户将自己的数据秘密分享给一个指定的用户.然而，在许多情形下，用户希望所有满足指定访问策略的用户都能够访问数据，从而实现细粒度的访问控制.例如，病人希望自己的医疗数据能被A医院的所有内科医生访问.

为了解决上述问题，Sahai和Waters[1]在2005年提出了属性加密(attribute-based encryption, ABE)的概念.在ABE方案中，用户的解密能力依赖于自身的属性.因此，ABE在保护数据机密性的同时，可以实现数据的细粒度访问控制.在密文策略属性加密[2](ciphertext-policy ABE, CP-ABE)中，用户的私钥对应于自身属性，密文对应于一个访问策略，当且仅当用户的属性满足访问策略时，用户才能够成功解密.虽然现有的ABE方案[2-6]支持细粒度访问控制，但效率过低和私钥泄露仍是阻碍其实际应用的2个关键问题.

近年来，ABE中的私钥泄露问题[7-11]越来越受到研究者们的重视.在CP-ABE方案中，多个用户可能拥有相同的属性，从而有相同的解密能力.若一个恶意用户出售自己的私钥，则难以通过这个私钥找出该用户.例如一个病人想利用ABE来分享自己的医疗信息给A医院的内科医生，而张三和李四都是A医院的内科医生.如果张三和李四中某人泄露了私钥，则难以判断是谁泄露的私钥.另一方面，ABE虽然实现了细粒度访问控制，但效率要比传统加密低得多.例如在CP-ABE方案中，用户的加密时间是和访问策略的复杂性成线性关系的.因此，使用CP-ABE加密会给用户造成巨大的时间开销和能源开销，尤其是会对使用移动设备进行操作的用户造成巨大挑战.

针对上述问题，本文在素数阶群下构造了一个在线/离线的可追责CP-ABE(online/offline traceable CP-ABE, OO-T-CP-ABE)方案.此外，我们在标准模型下证明了方案是选择性安全(selectively secure)和可追责的.方案的特点总结为4点：

1) 可追责.当恶意用户泄露或出售自己的私钥时，能够利用追责算法追踪到该用户的身份.

2) 在线/离线加密.加密的绝大部分运算是在离线阶段提前执行的，在线加密数据所带来的计算开销较小，因此适合于资源受限的移动设备使用.

3) 大属性域(large universe).整个系统的属性域并不需要在系统建立时固定，而且公钥长度并不随属性个数的增加而增加.这使得方案有较好的扩展性.

4) 丰富的访问策略.访问策略可以表示为任意单调访问结构，从而能够支持灵活的访问控制.

1 相关工作

Sahai和Waters[1]在2005年首次提出了ABE的概念.随后，Goyal等人[3]将ABE划分为密钥策略ABE (key-policy ABE, KP-ABE)和CP-ABE.此后，选择性安全的CP-ABE方案[2,4]和自适应安全(adaptively secure)的CP-ABE方案[5-6]也被陆续提出.2011年，Lewko和Waters[12]在合数阶群下构造了第1个支持大属性域的CP-ABE方案.相比于文献[1-6]，文献[12]中的方案并不需要在系统建立时确定属性域，而且公钥的长度与属性个数无关.之后，Rouselakis和Waters[13]在素数阶群下构造了一个更加高效的支持大属性域的CP-ABE方案.近年来，为了提高ABE方案的效率，可外包解密的ABE[14]、在线/离线ABE[15]和密文长度固定的ABE[16]方案也被相继提出.然而，上述方案[14-16]并不能够对恶意用户进行追责，因此存在用户私钥泄露的风险.

文献[7-8]首先研究了ABE的追责问题.但是文献[7-8]中的访问策略只能表示为“与门和通配符(AND gates with wildcard)”.针对此问题，Liu等人提出了支持任意单调访问结构的白盒追责ABE[9]和黑盒追责ABE[10]方案.随后，Ning等人[11]提出了一个支持大属性域的可追责CP-ABE方案.但已有的可追责CP-ABE方案[7-11]的在线加密开销过大，从而会严重影响用户在移动设备上的使用体验.与文献[7-11]相比，本文提出的ABE方案不仅支持恶意用户追责，而且支持在线/离线加密，从而大幅减少了用户的在线加密开销.

2 背景知识

2.1 访问结构

定义1. 访问结构[17].设{P1,P2,…,Pn}为所有参与者组成的集合.一个集合A⊆2{P1,P2,…,Pn}是单调的，当且仅当对任意B,C，如果B∈A，且B⊆C，则C∈A.一个(单调)访问结构(access structure)A是由{P1,P2,…,Pn}的非空子集组成的(单调)集合，即A⊆2{P1,P2,…,Pn}{∅}.包含在A中的集合称为授权集合，不包含在A中的集合称为非授权集合.

2.2 线性秘密共享

定义2. 线性秘密共享[17].定义在参与者集合P上的一个秘密共享方案Π称为在p上是线性的，当满足2个条件：

1) 每个参与者关于s∈p的秘密分享值组成p上的一个向量.

2) 存在一个Π的分享生成矩阵M∈l×np和函数ρ:[l]→P.对于i∈[l]，函数ρ将其映射到参与者

ρ(i).随机选择y2,y3,…,yn∈p，令列向量y=(s,y2,y3,…,yn)T，则My是秘密s关于Π的l个分享份额.其中分享份额λi=(My)i属于参与者ρ(i).

文献[17]指出任何一个线性秘密共享方案(linear secret sharing scheme, LSSS)都具有如下线性重构性质.如果Π是访问结构A的一个LSSS，S是A中的一个授权集合，I={i:ρ(i)∈S}⊆{1,2,…,l}，则存在常数{ωi∈p}使得s.

2.3 双线性群和困难问题假设

本文将在素数阶双线性群(prime order bilinear groups)下构造方案，并基于素数阶双线性群中的2个困难问题假设来证明方案的安全性.

设G和GT都是阶为素数p的循环群，g是G的生成元.双线性对e:G×G→GT是一个满足2个条件的映射：

1) 双线性.∀u,v∈G,e(ua,vb)=e(u,v)ab.

2) 非退化性.e(g,g)≠1.

如果双线性对e:G×G→GT和群中的运算都是可以有效计算的，则称G是一个素数阶双线性群.

定义3.q-1假设[13].G是阶为素数p的双线性群，g是G的生成元.群G中的q-1难题定义如下：随机选取a,s,b1,b2,…,bq∈p，给定

{gai/bj}(i,j)∈[2q,q],i≠q+1,{gs aibj/bj′,

区分GT中的随机元素R和e(g,g)s aq+1.

一个算法A解决群G中的q-1难题的优势为ε，当：

|Pr[A(D,e(g,g)s aq+1)=0]-
Pr[A(D,R)=0]|≥ε.

若没有一个多项式时间算法能够以不可忽略的优势解决群中的q-1难题，则称群中的q-1假设成立.

定义4.q′-SDH假设[18].G是阶为素数p的循环群，g是G的生成元.群G中的q′-SDH难题定义如下：随机选取x∈*p，给定(g,gx,gx2,…,gxq′)，计算其中c∈*p.

一个算法A解决群G中的q′-SDH难题的优势为ε，当：

若没有一个多项式时间算法能够以不可忽略的优势解决群中的q′-SDH难题，则称群中的q′-SDH假设成立.

3 在线离线可追责ABE的定义和安全模型

本文方案是在密钥封装机制(key encapsulation mechanism， KEM)下定义的，即基于属性的加密是用来加密会话密钥的，而该会话密钥能够作为对称加密的密钥来加密任意长度的消息.

3.1 定 义

一个在线/离线的可追责密文策略属性密钥封装机制(online/offline traceable CP-AB-KEM， OO-T-CP-AB-KEM)包括6个算法：

1)Setup(λ,U).该算法输入安全参数λ和属性域U，输出公钥PK和主密钥MSK.此外，该算法初始化一个追责列表T=∅.

2)KeyGen(MSK,PK,id,S).该算法输入主密钥MSK、公钥PK、用户的身份id和一个属性集合S⊆U，输出一个对应于(id,S)的用户私钥SKi d,S，并将id加入列表T中.

3)Offline.Encrypt(PK).该算法输入公钥PK，输出一个间接密文IT.

4)Online.Encrypt(PK,IT,(M,ρ)).该算法输入公钥PK、间接密文IT和一个访问策略(M,ρ)，输出一个会话密钥key和一个密文CT.

5)Decrypt(SKi d,S,PK,CT).该算法输入公钥PK、对应于属性集S的私钥SKi d,S、对应于访问策略(M,ρ)的密文CT.如果属性集S不满足访问策略(M,ρ)，直接输出⊥表示解密失败；否则，输出一个会话密钥key.

6)Trace(PK,T,SK).该算法输入公钥PK、追责列表T、私钥SK.该算法首先检查SK是否为一个合理的私钥以确定是否有必要进行追责.如果SK是一个合理的私钥，则输出SK对应的身份id；否则，输出符号Λ表示SK不是一个合理的私钥.

3.2 选择性安全模型

本节通过一个敌手和挑战者之间的游戏给出OO-T-CP-AB-KEM的安全模型.具体游戏描述如下：

1) 初始化.敌手声明并发送自己要攻击的访问策略(M*,ρ*)给挑战者.

2) 系统建立.挑战者运行Setup(λ,U)→(PK,MSK)，并将公钥PK发给敌手.

3) 询问阶段1.敌手向挑战者询问对应于属性集(id1,S1),(id2,S2),…,(idq1,Sq1)的私钥.对于所有i∈[q1]，挑战者运行KeyGen(MSK,PK,idi,Si)→SKi di,Si，并将SKi di,Si发送给敌手.这里要求对任何i∈[q1]，Si都不满足访问策略(M*,ρ*).

4) 挑战.挑战者运行Online.Encrypt(PK,Offline.Encrypt(PK),(M*,ρ*))→(key*,CT*)算法，并随机选择b∈{0,1}.如果b=0，则将(key*,CT*)发送给敌手；如果b=1，则在会话密钥空间中选择一个随机值R，并将(R,CT*)发送给敌手.

5) 询问阶段2.这一阶段和询问阶段1相同.敌手继续向挑战者询问对应于属性集(idq1+1,Sq1+1),(idq1+2,Sq1+2),…,(idqs,Sqs)的私钥.同样地,对于所有i∈[qs]，要求Si不能满足访问策略(M*,ρ*).

6) 猜测.敌手输出对于b的猜测结果b′∈{0,1}.

敌手在上述游戏中获胜的优势被定义为|Pr[b=b′]-1/2|.

定义5. 如果任何多项式时间敌手在上述游戏中获胜的优势都是可忽略的，则称一个OO-T-CP-AB-KEM方案是选择性安全的.

3.3 可追责性安全模型

本节通过一个敌手和挑战者之间的游戏给出OO-T-CP-AB-KEM中可追责性的定义.具体追责游戏描述如下：

1) 系统建立.挑战者运行Setup(λ,U)→(PK,MSK)，并将公钥PK发送给敌手.

2) 询问阶段.敌手向挑战者询问对应于属性集(id1,S1),(id2,S2),…,(idqs,Sqs)的私钥.对于所有i∈[qs]，挑战者运行KeyGen(MSK,PK,idi,Si)→SKi di,Si，并将SKi di,Si发送给敌手.

3) 私钥伪造.敌手输出一个私钥SK*.

敌手在上述游戏中获胜的优势被定义为Pr[Trace(PK,T,SK*)∉{Λ,id1,id2,…,idqs}].

定义6. 如果任何多项式时间敌手在上述游戏中获胜的优势都是可忽略的，则称一个OO-T-CP-AB-KEM方案是可追责的.

4 支持在线离线加密的可追责CP-ABE方案

本节将在KEM情形下构造一个支持追责和在线/离线加密的CP-ABE方案，并且在标准模型下证明方案是选择安全和可追责的.最后，我们给出了本文方案和相关方案的性能对比.

4.1 方案构造

此处假定LSSS 访问策略中的矩阵最多有P行，后面将指出如何去除这个限制条件.具体的OO-T-CP-AB-KEM方案构造如下：

1)Setup(λ,U).该算法首先选择一个阶为素数p的双线性群G.e:G×G→GT是一个定义在G上的双线性对;然后随机选择g,h,u,v,w∈G和α,a∈p，输出公钥PK=(G,p,g,h,u,v,w,e(g,g)α,ga)和主密钥MSK=(α,a);最后建立一个空的追责列表T.

2)KeyGen(MSK,PK,id,S={A1,A2,…,Ak}⊆p).该算法随机选择r,r1,r2,…,rk∈p和c∈*p{-a}，如果c已经存在于列表T中，则重新选择随机元c;然后计算并对所有i∈[k]计算Ki,2=gri,Ki,3=(uAih)riv-(a+c)r;最后输出用户的私钥SKi d,S=(S,K0,,K1,,{Ki,2,Ki,3}i∈[k])，并将数组(c,id)加入到追责列表T中.

3)Offline.Encrypt(PK).该算法选择随机数s∈p，计算key=e(g,g)α s,C0=gs,=ga s;然后对所有的j∈[P]，随机选择,xj,tj∈p，并计算最后输出间接密文IT=(key,s,C0,，{,tj,xj,Cj,1,Cj,2,Cj,3}j∈[P]).

4)Online.Encrypt(PK,IT,(M,ρ)).该算法输入公钥PK、间接密文IT和LSSS访问策略(M,ρ).其中M是一个l×n矩阵，且l≤P，ρ:[l]→p将矩阵的每一行Mj映射到属性ρ(j).首先随机选择y2,…,yn∈p，令向量y=(s,y2,…,yn)T;然后对所有的j∈[l]，计算λj=(My)j，Cj,4=λj-,Cj,5=tj(xj-ρ(j));最终得到会话密钥key=e(g,g)α s和密文CT=((M,ρ),C0,，{Cj,1,Cj,2,Cj,3,Cj,4,Cj,5}j∈[l]).

其中j是属性ρ(i)在集合S={A1,A2,…,Ak}中的索引，即ρ(i)=Aj.

S={A1,A2,…,Ak}⊆p,
∈*p,K0,K1,,Ki,2,Ki,3∈G；

(1)

(3)

存在i∈[k]使得:

(4)

因此有：

4.2 选择性安全证明

本节将证明本文方案在q-1假设下是选择性安全的.首先证明如下引理.

引理1. 如果 HW (Hohenberger-Waters)方案[15]是选择性安全的，则本文的OO-T-CP-AB-KEM 方案是选择性安全的.

证明. 为了证明这个引理，我们将指出：在选择性安全模型下，如果有一个多项式时间敌手A能以不可忽略的优势ε攻破OO-T-CP-AB-KEM方案，则能利用敌手A构造一个模拟者B以同样的优势ε攻破HW方案.C是HW方案中与模拟者B交互的挑战者.

1) 初始化.敌手A首先发送自己要攻击的访问策略(M*,ρ*)给模拟者B，B将(M*,ρ*)发送给挑战者C.其中M*是一个l×n矩阵，ρ*:l→p将矩阵的每一行映射到属性ρ*(j).

5) 询问阶段 2.这一阶段和询问阶段1相同.

6) 猜测.敌手A发送给B对于b测猜结果b′.最后，B输出b′.

由于上述分布对于敌手A来说是完美的，因此，如果A能够以优势ε攻破我们的OO-T-CP-AB-KEM方案，则模拟者B能以同样的优势ε攻破HW方案.

证毕.

此外，下述2个引理已在文献[13,15]中被证明.

引理2[15].如果RW(Rouselakis-Waters)方案[13]是选择性安全的，则HW方案[15]也是选择性安全的.

引理3[13].如果q-1假设成立，且挑战矩阵M*的大小l×n满足l,n≤q，则RW方案是选择性安全的.

定理1. 如果q-1假设成立，且挑战矩阵M*的大小l×n满足l,n≤q，则本文的OO-T-CP-AB-KEM方案是选择性安全的.

证明. 由引理1、引理2和引理3可以直接得出.

证毕.

4.3 可追责性安全证明

本节将证明本文方案在q′-SDH假设下是可追责的.首先证明如下引理.

引理4. 假设BB(Boneh-Boyen)签名方案[18]在弱选择消息攻击下是存在性不可伪造的，则本文的OO-T-CP-AB-KEM方案是可追责的.

证明. 假设对于本文的OO-T-CP-AB-KEM方案，存在一个多项式时间敌手A能以不可忽略的优势ε赢得3.3中的追责游戏，则能构造出一个模拟者B在弱选择消息攻击下，以同样的优势ε伪造一个BB签名.C是BB签名方案中与模拟者B交互的挑战者.

2) 询问阶段.在这一阶段，敌手A进行q次私钥询问，模拟者B回答A的私钥询问.当A进行第j(j≤q)次私钥询问时，A发送(idj,Sj={A1,A2,…,AK}⊆p)给B并询问OO-T-CP-AB-KEM方案中对应的私钥.B首先随机选择cj∈*p，如果cj已经在列表T中，则重新选择cj∈*p，然后向C询问cj的BB签名.C返回给B签名).B随机选择r,r1,r2,…,rk∈p，然后计算：

对于cj=-a这种极小概率发生的情形，C返回给B的签名为(cj,1)，这时B需要重新选择cj∈*p，并重复上述过程.最后将私钥SKi dj,Sj=(Sj,K0,j,,K1,j,,{Ki,2,j,Ki,3,j}i∈[k])发送给A，并将数组(c,id)加入到追责列表T中.

3) 私钥伪造.敌手A输出一个私钥SK*给B.

S={A1,A2,…,Ak}⊆p,
∈*p,K0,K1,,Ki,2,Ki,3∈G;

(5)

(7)

假设K1=gt，其中t是p中的未知元.由式(6)可得因此由式(7)可得

证毕.

此外，由文献[18]，我们有以下引理.

引理5[18].如果q′-SDH假设成立，且进行私钥询问的次数qs≤q′，则在弱选择消息攻击下BB签名方案[18]是存在性不可伪造的.

定理2. 如果q′-SDH假设成立，且进行私钥询问的次数qs≤q′，则本文的OO-T-CP-AB-KEM方案是可追责的.

证明. 由引理4和引理5可以直接得出.

证毕.

4.4 移除对访问策略的限制

4.5 方案对比

表1给出了本文方案与相关方案的性能对比.其中,l表示LSSS访问策略中矩阵的总行数，ET表示群GT中的指数运算，EG和MG分别表示群G中的指数和乘法运算.相比群G和GT中的运算，p中的运算开销很小，因此表1中忽略了p中的运算开销.

从表1中可以看出，文献[15]中方案的在线加密开销很小，但是并不支持对恶意用户追责，存在恶意用户出售私钥的风险.文献[9，11]和本文方案都支持用户追责和LSSS访问策略，因此在实现灵活访问控制的同时，可以追踪泄露私钥的用户身份.然而，文献[9]并不支持大属性域，即系统的属性域需要在系统建立之初确定.如果后面新加入的属性超出了属性域，则需要重新建立系统，这导致文献[9]中方案的可扩展性较差.文献[11]尽管支持大属性域，但方案的加密过程全部需要用户在线完成，这会使得在线加密的时间和能源开销较大，不适用于移动设备进行加密.相比于文献[9，11]，本文方案的加密开销几乎全部在离线阶段，这样使用移动设备的用户可以在能源充足时进行离线加密操作，当需要加密具体数据时，只需要消耗较少能源就能够快速完成在线加密.

5 结束语

本文在素数阶双线性群下构造了一个支持在线/离线加密的可追责CP-ABE方案，并且在标准模型下证明了方案是选择性安全和可追责的.在本文方案中，如果一个恶意用户泄露自己的私钥，则可以通过追责算法确定恶意用户的身份.本文方案不仅支持任意的单调访问结构，而且绝大部分的加密操作是在离线阶段完成的，更适用于资源受限的移动设备.此外，本文方案是支持大属性域的，因此在实际应用中具有较好的扩展性.

[1] Sahai A, Waters B. Fuzzy identity-based encryption[G] //LNCS 3494: Proc of EUROCRYPT’05. Berlin: Springer, 2005: 457-473

[2] Bethencourt J, Sahai A, Waters B. Ciphertext-policy attribute-based encryption[C] //Proc of IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2007: 321-334

[3] 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 Conf on Computer and Communications Security. New York: ACM, 2006: 89-98

[4] Waters B. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[G] //LNCS 6571: Proc of PKC’11. Berlin: Springer, 2011: 53-70

[5] Lewko A, Okamoto T, Sahai A, et al. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption[G] //LNCS 6110: Proc of EUROCRYPT’10. Berlin: Springer, 2010: 62-91

[6] Okamoto T, Takashima K. Fully secure functional encryption with general relations from the decisional linear assumption[G] //LNCS 6223: Proc of CRYPTO’10. Berlin: Springer, 2010: 191-208

[7] Hinek M J, Jiang Shaoquan, Safavi-Naini R, et al. Attribute-based encryption with key cloning protection [EB/OL]. International Association for Cryptologic Research (IACR), (2008-11-12)[2017-01-08]. http://eprint.iacr.org/2008/478

[8] Li Jin, Ren Kui, Kim K. A2BE: Accountable attribute-based encryption for abuse free access control [EB/OL]. International Association for Cryptologic Research (IACR), (2009-04-14) [2017-01-08]. http://eprint.iacr.org/2009/118

[9] Liu Zhen, Cao Zhenfu, Wong D S. White-box traceable ciphertext-policy attribute-based encryption supporting any monotone access structures[J]. IEEE Trans on Information Forensics and Security, 2013, 8(1): 76-88

[10] Liu Zhen, Cao Zhenfu, Wong D S. Traceable CP-ABE: How to trace decryption devices found in the wild[J]. IEEE Trans on Information Forensics and Security, 2015, 10(1): 55-68

[11] Ning Jianting, Dong Xiaolei, Cao Zhenfu, et al. White-box traceable ciphertext-policy attribute-based encryption supporting flexible attributes[J]. IEEE Trans on Information Forensics and Security, 2015, 10(6): 1274-1288

[12] Lewko A, Waters B. Unbounded HIBE and attribute-based encryption[G] //LNCS 6632: Proc of EUROCRYPT’11. Berlin: Springer, 2011: 547-567

[13] Rouselakis Y, Waters B. Practical constructions and new proof methods for large universe attribute-based encryption[C] //Proc of the 20th ACM Conf on Computer and Communications Security. New York: ACM, 2013: 463-474

[14] Green M, Hohenberger S, Waters B. Outsourcing the decryption of ABE ciphertexts[C] //Proc of USENIX the Security Symp. Berkeley, CA: USENIX Association, 2011: 523-538

[15] Hohenberger S, Waters B. Online/offline attribute-based encryption[G] //LNCS 8383: Proc of PKC’14. Berlin: Springer, 2014: 293-310

[16] Xiao Siyu, Ge Aijun, Ma Chuangui. Decentralized attribute-based encryption scheme with constant-size ciphertexts[J].Journal of Computer Research and Development, 2016, 53(10): 2207-2215 (in Chinese)

(肖思煜, 葛爱军, 马传贵. 去中心化且固定密文长度的基于属性加密方案[J]. 计算机研究与发展, 2016, 53(10): 2207-2215)

[17] Beimel A. Secure schemes for secret sharing and key distribution [D]. Haifa, Israel: Technion-Israel Institute of Technology, Faculty of Computer Science, 1996

[18] Boneh D, Boyen X. Short signatures without random oracles and the SDH assumption in bilinear groups[J]. Journal of Cryptology, 2008, 21(2): 149-177