支持高效撤销的属性加密方案

张兴兰,李建楠

(北京工业大学信息学部，北京 100124)

0 引 言

云计算[1]作为一种新兴的服务方式，把网络中大量不同类型的资源整合起来，提供计算和存储等功能，很大程度上降低了用户成本,提高了资源的利用率。如何在云计算环境中保证数据的安全成为信息安全领域的研究热点。

Sahai等[2]初次提出关于属性加密的理念，为实现云环境下细粒度的访问控制提供了可能。目前关于属性加密的方案分为2种：1)密钥策略的属性加密(KP-ABE)[3]；2)密文策略的属性加密(CP-ABE)[4-5]。在CP-ABE中，密钥和密文都与属性相关联，用户可以共享ABE中相同的属性，对任何属性进行撤销都可能会牵连到具有这一属性的其他用户。

近年来，许多学者针对撤销问题做了大量的研究。Pirretti等[6]的方案分别给每个属性设置有效时间，从而达到属性和密钥阶段性变更。该方法虽然简单，但划分有效时间段的粒度越细，存储和更新密钥的工作量会越大；随着用户数目的快速上升，可信机构对应的任务量也会急剧加大，可扩展性差；不能撤销用户对未解密数据的访问权限。Bethencourt等[4]的方案对用户属性设置截止日期，解密数据时，不仅要求用户的属性集满足加密时采用的访问策略，且属性对应的截止时间必须在密文的有效期之后。该方法降低了存储用户密钥的开销，但不支持属性的及时撤销，且授权机构的工作量比较大。Boldyreva等[7]的方案基于身份加密，但该方案仅支持用户撤销。Do等[8]的方案添加了特别管理组，负责属性撤销时更新密文，而密钥的更新由云服务器来操作，该方案对云服务和资源没有充分利用，造成资源消耗、效率低下等问题。Attrapadung等[9]的方案中，数据拥有者全权负责维护每个属性组的成员列表，支持直接用户撤销，不适用于数据共享系统，因为数据拥有者将数据存储到外部存储服务器之后将不再直接控制数据。Tysowski等[10]的方案结合代理重加密思想，实现对用户的撤销，但是该方案不支持属性撤销，且无法抵抗合谋攻击。文献[11]中引入了半可信的第三方代理，用户撤除是由服务器通过第三方代理重加密实现的，当用户数量剧增时，第三方更新的工作量大，效率会受到严重影响，并且授权机构负责生成包括代理密钥在内的所有密钥，存在严重的密钥托管问题。

由上可知，如何在保证数据机密性和降低数据拥有者计算代价的基础上，利用云服务器的计算和存储能力实现高效、细粒度的访问控制是很有必要的。本文从4个方面作研究：1)优化访问控制结构，在保证数据安全性的前提下，用户权限变动的灵活性明显提升，尤其是涉及大规模用户属性撤销问题；2)提出属性用户组密钥分发方法，不要求用户一直在线，解决了密钥更新滞后问题，实现及时撤销操作；3)由于数据在服务器中始终是以密文形式存放，所以可以适当放宽对服务器的安全限制，将部分计算任务转移给云服务器执行；4)把对用户的撤销转换成属性级别的撤销，使得访问控制更加细粒度化，有效降低系统执行撤销时的计算和传输开销。

1 预备知识

1.1 双线性映射

设p是素数，G1和G2均是p阶乘法循环群，g是G1的生成元，e是双线性映射[12]，表示为e:G1×G1→G2。双线性映射e满足如下3个性质：

1)双线性。对于任意的a,b∈Zp,h∈G1，都满足e(ga,hb)=e(g,h)ab。

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

3)可计算性。对于任意g,h∈G1,存在计算e(g,h)值的有效多项式时间算法。

其中，e(*,*)是一个对称操作,即e(ga,hb)=e(g,h)ab=e(gb,ha)；另外，e(g1·g2,h)=e(g1,h)e(g2,h)，其中g1,g2,h∈G1。

定义1DBDH问题假设。设G0和G1分别表示p阶乘法群，g是群G0的生成元，e:G0×G0→G1是双线性映射。输入g,ga,gb,gc∈G0和元素Z∈G1，判定Z=e(g,g)abc的输出。如果|Pr [Λ(g,ga,gb,gc,e(g,g)abc)=0]-Pr [Λ(g,ga,gb,gc,Z)=0]|≥ε且存在一个多项式时间算法β输出b∈{0,1}，那么敌手在G1上就能以不可忽略的优势ε解决DBDH问题；如果不存在，则认为在G1上DBDH假设成立。

1.2 访问控制结构

定义2访问结构。假设参与访问的集合是{P1,P2,…,Pn}，且P=2{P1,P2,…,Pn}。访问结构Α是集合{P1,P2,…,Pn}的非空子集，即Α⊆P{∅}。若访问结构Α是单调的，则对于∀B,C来说，若B∈A且B⊆C，那么C∈A。授权集是在访问结构Α中的集合，不在Α中的集合是未授权集[13]。

本文采用访问控制树描述访问策略，叶子节点与属性相关联，内部节点由∧、∨布尔运算符表示。例如，图1是一种简单的访问控制结构，同时具有属性a1和a2或属性b1和b2的用户满足访问策略T=(a1∧a2)∨(b1∧b2)。

图1 简单访问控制树

如果某用户要获得访问数据密文的许可，那么其对应的属性集必须符合数据加密时采用的访问策略。对图1来说，用户集合{a1,a2}和集合{b1,b2}都满足解密条件。

2 系统模型和方案形式化定义

2.1 系统模型

本文的系统架构包括4个实体：可信权威机构、数据拥有者、用户和云服务器，如图2所示。

图2 系统架构图

1)可信权威机构。根据用户的角色和身份为其颁发相应的属性集；发布系统公钥和私钥信息。

2)数据拥有者。制定访问控制策略、加密数据，然后将密文文件交给云服务器存储。

3)云服务器。负责数据密文的存储，管理用户的访问请求并提供响应；发布、撤销和更新属性用户组密钥，为每个属性用户组分发随机密钥，供该组内的成员所共享。当用户的某一个属性被撤除时，云服务器相应地更换被撤销属性所对应的组密钥，对密文做相应地更新操作，这样新进入系统的用户或未撤销的用户均可使用最新的私钥解密数据，从而实现灵活的用户和属性撤销。

4)用户。用户向云服务器提出访问请求时，当且仅当用户拥有的属性集合符合加密数据时采用的访问策略，方能解密。此外，用户的属性集可以动态变化，例如属性撤销。

2.2 本方案形式化定义

本方案有7个算法，描述如下：

1)初始化算法Setup：输出系统公钥PK和主私钥MK。

2)用户私钥生成算法AttrKeyGen(MK,S,U)：输入主密钥MK、属性集S∈Attr、属性集S对应的用户集合U∈；输出对应用户ut的私钥SKt,ut∈U。

4)加密算法Encrypt(PK,M,T)：输入系统的公钥PK、访问控制树T和数据明文M；输出密文CT。

5)密文重加密算法ReEncrypt(CT,f(T′),Ω)：输入密文CT、最小属性子集信息f(T′)和属性用户组集合Ω；输出重加密后的密文CT′。

6)解密算法Decrypt(PK,SKt,CT′)：输入系统的公钥PK、密文CT′以及用户私钥SKt；若与私钥SKt关联的属性集符合密文中的访问控制树，则允许解密；否则⊥。

7)密文更新算法CTUpdate(C T′)：当属性用户组Gi中发生变更，即撤销某用户的属性ai，云服务器执行属性用户组密钥更新，进而对原密文相关成分做更新计算。

3 方案设计

本方案设计的思路是将CP-ABE算法同重加密的技术结合，在属性层面完成高效的用户撤销。本方案并不是从头开始建立一个新的CP-ABE方案，而是基于但不限于Cheung等人的CP-ABE[5]，通过构建属性用户组密钥分发方法，扩展密钥的代理更新和密文重新加密的能力来增强现有的构造。

3.1 初始化Setup

输出系统公钥PK={G,g,y,Tj(1jm)},主密钥MK={α,tj(1jm)}。

3.2 密钥生成

该阶段有2个过程：可信权威机构为用户生成私钥；服务器生成路径信息，用户可用于解密属性用户组密钥。

1)AttrKeyGen。

输入：主密钥MK、用户的属性集S∈Attr以及具有S的用户集合U∈。

输出:用户μt∈U对应的私钥SKt={d=gα-δ,{dj=gδtj-1}∀aj∈S}。

2)KEKGen。

图3 KEK二叉树

每个用户ut∈U对应二叉树的一个叶节点，保存了从对应叶子节点到根节点路径上的KEK值，即Pathut={vj∈Γ:KEKj}。例如，用户u1的路径信息为：Pathu1={KEK16,KEK8,KEK4,KEK2,KEK1}。

3.3 加密Encrypt

输入：系统公钥PK、数据明文M和访问控制树T。

图4 访问控制树

1)采用秘密共享方法[15]，从根节点开始，如果节点的标识符为∧且它的孩子节点是未标记状态，那么，对除最后一个孩子节点外的其他孩子节点分别分配一个随机值si，其中1sip-1；最后一个孩子节点的值为(s′是该节点的值)，将得到值后的节点状态标记为已分配。

2)若节点的标识符是∨，且该节点的孩子节点的状态是未分配，设置每个孩子节点的值等于该节点的值，并将状态标记为已分配。

3.4 密文重加密ReEncrypt

云服务器接到密文CT之后做重加密转换计算。数据拥有者将访问控制树T的属性关系表示成关系式形式，并转换成由极小项构成的主析取范式，提取每个极小项中的属性元素，进一步化简得到多个最小属性子集，要求每个属性只属于一个最小属性子集Qi。利用离散数学中范式[16]，以图4的访问控制树T为例，转化成关系式f(T)=((a1∧a2∧a3)∧(a4∨a5))∨((a6∧a7)∨a8)，再转化成主析取范式f(T)=((a1∧a2∧a3)∧(a4∨a5))∨((a6∧a7)∨a8)=(a1∧a2∧a3∧a4)∨(a1∧a2∧a3∧a5)∨(a6∧a7)∨a8。f(T)中的极小项有：(a1∧a2∧a3∧a4)、(a1∧a2∧a3∧a5)、(a6∧a7)和a8，化简得到最小属性子集Q1=a1∧a2∧a3∧a4，Q2=a5，Q3=a6∧a7，Q4=a8，那么f(T′)=Q1∨Q2∨Q3∨Q4。

1)输入：属性用户组集合Ω和最小属性子集信息f(T′)。

2)生成头部信息Hdr。

根据KEK二叉树中最小覆盖子树根节点的信息加密属性用户组密钥。最小覆盖子树是指能够覆盖所有与属性用户组Gj中用户元素相对应的叶子节点，定义为KEK(Gj)[17]。以图3为例，属性用户组Gj={u1,u2,u3,u4,u7,u8}，节点v4是覆盖叶子节点v1、v2、v3、v4的最小子树的根节点，v11是覆盖叶子节点v7、v8的最小子树的根节点，那么KEK(Gj)={KEK4,KEK11}。对于不属于属性组中的用户u，即u∉Gj，则不可能得到关于Gj中的任何KEK信息。

Hdr={{(EK(Kaj))K∈KEK(Gj)}∀aj∈T}

数据密文最终以(Hdr,CT′)的格式储存在云服务器中，当其接收到来自用户的访问请求时，将(Hdr,CT′)返回。只要该用户的属性没有撤销，就可以从头部信息Hdr中得到对应的属性用户组密钥。

3.5 解密

解密包含2个步骤：属性用户组密钥解密和数据密文解密。

1)ReEncrypt。

若用户ut(ut∈Gj)具有属性aj，使用路径信息Pathut同KEK(Gj)求交集得到KEK(KEK∈Pathut∩KEK(Gj))，从而解密Hdr得到属性用户组密钥KQj。若用户ut(ut∉Gj)，则中止计算。接着，用户ut利用属性用户组密钥KQj更新私钥SKt：

2)Decrypt。

若用户u的属性集S符合加密采用的访问控制树T，且用户u相对于S中属性元素来说是有效的，即aj∈S且u∈Gj；令集合S′⊆S，S′是用户u满足T的最小属性集合,否则，不可解密。

①对每个属性aj∈S′，计算：

=e(g,g)δs

②e(c0,d)·e(g,g)δs=e(gs,gα-δ)·e(g,g)δs

=e(g,g)αs

③最后，解密得到：

3.6 属性撤销

在云存储环境中，用户的访问权限应该是动态变化的。当撤除用户的某个属性aj时，权威机构就将该用户从属性aj的用户组Gj中剔除，告知云服务器相应地更换Gj的密钥。此过程不需要数据拥有者参与，而是由云服务器来执行密文更新操作，在保证数据安全性前提下，极大地降低了数据拥有者的运算量。密文更新算法CTUpdate分2步执行：

上述计算过程是针对发生用户变更的属性用户组。对于没有变更的其他属性用户组来说，这一过程不是必须的。

2)云服务器为属性aj对应的属性用户组Gj中的用户重新选择最小覆盖子树，用于计算更新后的头部信息Hdr。

4 安全性证明及性能分析

4.1 安全性证明

定义：若在所有多项式时间内，挑战者能以不可忽略的优势赢得这场游戏的胜利，则证明方案达到选择明文攻击安全。

定理1假设DBDH问题成立。若挑战者能攻破上述安全模型，则至少存在一个能以不能忽略的优势解决DBDH的多项式时间算法。

证明：本文采用反证法进行证明。假设存在一个挑战者Α按照上述模型能够以不能忽略的优势ε攻破本方案，那么模拟器Β就能以不能忽略的优势ε/2来解决DBDH问题。

Init：挑战者Α选择访问控制树T*并提供给模拟器Β。

Setup：模拟器Β随机选择x′∈Zp，并隐含设置α=ab+x′，有e(g,g)α=e(g,g)abe(g,g)x′。对于每个aj∈Attr,1jm，分别选择一个随机值kj∈Zp，若aj∉T*,则Tj=B1/kj,tj=b/kj；若aj∈T*,tj=kj，则Tj=gkj。模拟器Β保存主密钥MSK，并发送系统的公钥PK给挑战者Α。

模拟器Β向挑战者Α返回云服务器产生的属性组密钥KQj和用户私钥skt={d,{dj}∀aj∈S}。

Challenge：挑战者Α发送2个明文消息M0,M1∈GT。模拟器Β抛一枚公平二进制硬币b，返回加密消息Mb。加密过程如下：

2)将访问控制树T*的根节点的值设置为gc，根节点标识为分配状态，其他子节点为未分配状态。递归地对每个未分配的叶子节点，执行如下操作：

①从根节点开始，若标识符为∧且它的孩子节点都是未标记状态，模拟器Β为除最后一个孩子节点外的其他子节点选择一个值hi，其中1hip-1，并给它们分配ghi，为最后一个孩子节点分配值将分配值后的节点标记为分配状态。

②若标识符是∨且它的孩子节点是未标记分配状态，将其每个孩子节点的值设置为gc，标记状态成已分配。

③对每个叶子节点所对应的属性aj∈T*，计算cj=ghjkj。

Phase2：重复Phase1的密钥询问过程。

Guess：挑战者Α输出猜测u′∈{0,1}。若b′=b，模拟器Β输出μ=0，表明模拟器接收到的元组是DBDH元组中Zμ=e(g,g)abc；否则，模拟器Β输出μ=1，表明接收到的元组是随机的且Zμ=e(g,g)θ。

在上述DBDH游戏中，若D，那么Zμ=e(g,g)θ，则密文CT*是随机密文，挑战者没有获得关于Mb的信息，所以：Pr[ b ′≠b|μ=1]=1/2。

当b′≠b时，模拟器Β猜测μ′=1，所以，

Pr [μ′=μ|μ=1]=1/2

若μ=0，那么Zμ=e(g,g)abc，CT*是有效密文,根据定义知挑战者有ε的优势攻破本方案，所以：

Pr [b′=b|μ=0]=1/2+ε

当b′=b时，模拟器Β猜测μ′=0，所以，

Pr [μ′=μ|μ=0]=1/2+ε

那么，模拟器Β可以解决DBDH困难问题的总体优势是：

综上可证，如果挑战者A按照以上安全模型以不能忽略的优势ε攻破了本方案，则存在一种能以不能忽略的优势ε/2解决DBDH问题的多项式时间算法。因为不存在一种多项式时间算法能以不能忽略的优势解决DBDH问题，该问题已知是难解的。所以，不存在能以不能忽略的优势攻破本方案的挑战者A，即证明了本文提出的方案达到CPA安全。

4.2 性能分析

将本文方案与文献[9]和文献[11]分别从功能分析、存储开销和属性撤销代价3个方面进行对比，具体情况如表1～表3所示。

表1 系统功能分析

方案密钥更新用户撤销属性撤销文献[9]及时支持不支持文献[11]延时支持不支持本文方案及时支持支持

表2 存储开销对比

方案主密钥MSK公钥PK密文CT私钥SK文献[9]2|p|(m+7)|g|+|gT|(n+1)|g|+|gT|+|CT|(n+4)|g|文献[11](3m+1)|p|(3m+1)|g|+|gT|(m+1)|g|+|gT|+|CT| (2n+1)|g|本文方案(m+1)|p|(m+1)|g|+|gT||g|+|gT|+|CT|(n+1)|g|

表3 撤销属性时计算时间对比

方 案阶 段数据拥有者加密云服务器计算重加密文献[9]E=2(nT-λ)·ΓΔ+ΓeR=nT·ΓΔ文献[11]--R=(nT-λ)·ΓΔ本文方案--R=(nT-λi)·ΓΔ+Γe

由表1可知，相比于其它2个文献的方案，本文同时支持用户和属性撤销，灵活性有了很大的改善，并且在撤销后做到了密钥的及时更新，保障了系统数据的安全性。

在表3中，Γe代表运行一次双线性配对运算所需要的时间，ΓΔ代表执行一次模幂运算的时间，nT是访问控制树中的属性个数，λ是撤销属性的个数，且λnT，λ′是最小属性子集中属性的个数。对比3种方案，当撤销属性ai∈T时，本方案在系统整体的开销上有了明显改善，这一结果会在4.3节中给出验证。

4.3 实验验证

图5 撤销属性时重加密计算时间

本文在属性撤销时，数据拥有者不需要对文件重加密，这一点相比于文献[9]优势明显。本节仅对比实施撤销操作时3中方案中云服务器执行重加密密文的时间开销。实验采用Matlab进行仿真，并导入MIRACL库和PBC库以满足相关运算需求。假设系统撤销比率为10%，那么撤销属性个数为λ=nT×10%。已知，最小属性子集互不相交，设每个最小属性子集中属性平均个数为4，那么λ′=4λ。本文分别对属性个数为10,15,…,50时，执行密文重加密工作的时间开销进行对比，如图5所示。

由上可知，本文进行属性撤销时花费的计算时间显著降低。在无需数据拥有者参与的情况下，云计算服务器尽可能地减少重加密工作，降低系统整体计算负担并满足了及时撤销的要求，进一步提升了现有的支持撤销方案的高效性以及灵活性。另外，随着属性数量不断地增多，本方案的优势也会更加明显。

5 结束语

本方案基于CP-ABE并借助属性用户组密钥实现双重加密，在此过程中运用了秘密共享方案，采用的访问控制结构可以灵活地表达任意访问策略。此外，本文将用户撤销从系统级别转化为属性级别，利用云服务器的计算能力执行密文重加密工作，有效降低数据拥有者的计算开销，实现高效的访问控制，特别是在撤销时用户和属性数量规模大的情况下，系统效率优势会体现得更加明显。