云存储环境下支持属性撤销的属性基加密方案

孙磊，赵志远，王建华，朱智强

（1. 战略支援部队信息工程大学三院，河南 郑州 450001；2. 61516部队，北京 100062）

1 引言

密码学可以保证信息的完整性、机密性、不可抵赖性、可控性及可用性[1]。属性基加密（ABE,attribute-based encryption）[2]通过用户属性的差异实现数据的细粒度访问控制及灵活共享[3]。目前，ABE方案依据访问结构位置的差异主要分为密钥策略属性基加密（KP-ABE, key-policy ABE）方案[4]和密文策略属性基加密（CP-ABE, ciphertext-policy ABE）方案[5]。KP-ABE方案中，密文和属性相关联，私钥和访问结构相关联，当且仅当密文的属性满足密钥的访问结构时，用户才能解密密文以恢复出明文消息；CP-ABE方案中，私钥和属性相关联，密文和访问结构相关联，当且仅当与私钥关联的属性满足与密文关联的访问结构时，用户才能解密密文，恢复出明文消息。CP-ABE类似于传统访问控制中的基于角色的访问控制，指定具有某些属性的用户可以访问该密文，实现了“一对多”的加密模式，因此，CP-ABE在云存储模式（大量用户、海量数据，且解密方未知）下能够发挥极大价值，受到学术界和产业界的广泛关注，成为当前密码理论的研究热点[6]。

云存储系统中大量用户共享部分相同属性导致撤销某一个用户的属性时往往会影响其他相关用户，因此研究如何撤销用户属性成为一个富有挑战且具有重要意义的课题[7]。Pirretti等[8]第一次提出了属性可撤销的 ABE方案，该方案为系统所有属性指定版本密钥，并定期更新属性的版本密钥，而被撤销的属性无法完成密钥更新以此达到属性撤销的目的。在这种撤销方法中，当未达到更新时刻时，即使撤销用户属性，也不能立刻实现属性撤销，这个时间间隙被称为脆弱性窗口，其影响方案的前向安全和后向安全[9]。

为解决上述问题，Ibraimi等[10]和Yu等[11]分别提出了属性立即撤销的ABE方案，但这2种方案无法实现数据的细粒度访问控制。Hur等[12]提出了一种支持属性级用户撤销的 ABE方案，该方案能够实现实时撤销，不存在脆弱性窗口，但该方案无法抵抗用户合谋攻击。Yang等[13]提出了一种支持属性级用户撤销的 ABE方案，该方案中数据拥有者不需要实时在线参与撤销工作，且具有较高的计算效率，但该方案在随机预言机模型下完成安全性证明，而随机预言机模型是一种较弱的安全模型。Yang等[14]提出了另外一种支持属性撤销的ABE方案中，属性授权机构需要更新密文，同时生成新版本的密钥、更新密钥和私钥，这些计算工作给属性授权机构带来严重的计算负担。马华等[15]提出了一种支持属性撤销的 ABE方案，该方案基于密钥加密密钥树实现了密钥的更新，且在解密过程中，将部分解密运算外包给解密服务器，减少了用户的计算代价。马华等[15]声称该方案能够抵抗用户合谋攻击，但通过分析发现，该方案无法抵抗撤销用户与未撤销用户的合谋攻击。Shiraishi等[16]提出了一种属性可撤销的 ABE方案，但是其基于复杂假设完成安全证明导致安全性较弱。

目前，移动终端的弱计算能力与 ABE方案解密过程中的复杂计算过程相矛盾。因此，将 ABE方案的复杂计算外包给云服务商是一种切实可行的解决办法。Green等[17]提出了一种计算外包ABE方案，该方案通过云服务商将原始密文转变成ElGamal型密文，数据用户通过一次指数运算就可获得明文。Lai等[18]和Li等[19]分别提出了可验证外包解密的ABE方案。另外，Li等[19]所提方案的密文长度与方案所采用的访问结构复杂度无关。

文献[12,15]中，一个群中的用户共享相同的属性群密钥，因此已被撤销的用户和未被撤销的用户可以发起合谋攻击。针对上述问题，本文提出了一种支持属性立即撤销且解密外包的 ABE方案，该方案可以有效抵抗上述合谋攻击，采用外包技术，还可有效减少属性中心和用户的计算负担。本文在标准模型下基于计算性 Diffie-Hellman（CDH,computational Diffie-Hellman）假设完成安全证明。最后，实验表明所提方案具有更高的安全性，且提高了用户的解密效率。

2 理论基础知识

2.1 双线性映射

2.2 线性秘密共享方案

1) 对于每个参与者所持有的秘密份额都可以构成Zp上的向量。

2.3 CDH假设

2.4 密钥加密密钥树

密钥加密密钥（KEK, key encryption key）树[12]是一个完全二叉树，如图1所示。令系统中所有用户集合为系统中的所有属性集合为。设Gi⊂U是拥有属性atti的一个用户集合，被称为属性群。Gi则是可以正常访问属性atti的访问列表。设是属性群集合。例如，若用户分别拥有属性集合{那么

图1 KEK树示意

数据服务管理者（DSM, data service manager）按如下过程构建KEK树。

1) 二叉树的每一个叶子节点关联用户集合U中的每一个用户uk。同时，每个内部节点vj存储一个随机值jθ。

2) 路径节点生成算法Path(uk)：从根节点到叶子节点上的所有节点被定义为用户uk的路径节点，如

3) 最小覆盖集算法Mincs(Gi)：可以涵盖属性群Gi中所有用户的最少节点集合为最小覆盖集。若，则若，则

3 文献[12,15]安全性分析

在 ABE方案中，由于每个属性被多个用户共享，属性撤销是一个极其困难的问题，因此构建一个安全有效的属性撤销ABE方案至关重要。另外，ABE方案一个重要的安全特点就是抵抗用户合谋攻击，但是在阅读分析文献[12,15]时发现，这2种方案是不安全的，且存在用户合谋攻击。下面分别对这2种方案进行安全性分析。

3.1 文献[12]安全性分析

文献[12]提出了属性群概念，并构建KEK树为用户分发属性群密钥，同时完成属性撤销后的密钥更新工作，但是该方案不能够抵抗撤销用户和未撤销用户的合谋攻击。

一个用户的密钥由两部分组成：属性集合关联的密钥sk1（等同于基本ABE用户私钥）和基于KEK树的属性群密钥sk2。sk1和sk2是完全独立的，当一个用户从某个属性群撤销时，该用户将失去sk2，但是该用户的sk1仍然是可用的，因此该用户可以和其他用户合谋获得sk2，完成最终密文解密。

攻击实例：假设消息m用访问结构“教师and计算机”加密。用户u1的属性集合为“学生，计算机”，用户u2的属性集合为“教师，计算机”，则“计算机”的用户集合为所以“计算机”的最小覆盖集为此时关联属性“计算机”的密文头文件用节点v4的随机值4θ加密。u1的路径节点是的路径节点是

当没有属性撤销时，u2能够通过解密获得sk2,u2，通过属性集合获得sk1,u2，最终解密密文获得消息m。

当u2改变行业从事密码学时，该用户的属性“计算机”将被撤销，则“计算机”的用户集合为所以“计算机”的最小覆盖集为，此时关联属性“计算机”的密文头文件将通过用节点v8的随机值θ8加密。即使用户u2仍然拥有关联属性集合“教师，计算机”的私钥sk1,u2，由于其没有θ8，不能完成密文头解密，因此用户u2也不能完成最终密文解密。但是用户u1和用户u2合谋，u1将随机值θ8泄露给u2，u2将通过θ8完成对密文头的解密，再结合sk1,u2完成解密获得消息m。

3.2 文献[15]安全性分析

文献[15]基于文献[12]构建，属性集合关联的密钥sk1和KEK树分发的属性群密钥sk2仍然是完全独立的，因此该方案也不能抵抗撤销用户和未撤销用户的合谋攻击。其分析过程如3.1节所述，这里不再赘述。

4 RO-CP-ABE方案系统及安全模型

本节首先描述了支持属性撤销的属性基加密（RO-CP-ABE, CP-ABE with attribute revocation and outsourced decryption）方案的系统模型及其各组成部分的功能，然后对其进行形式化的描述，最后给出该方案的安全模型。

4.1 系统模型

本文提出了一种支持属性立即撤销的属性基加密方案，系统模型主要包括以下4类实体。

属性机构（AA, attribute authority）：AA是一个完全可信的权威机构，主要负责生成系统公钥和系统主私钥，同时管控属性密钥分发等工作。

云服务商（CSP, cloud service provider）：CSP主要是指第三方云存储提供商，本文定义的CSP包括DSM、计算服务和存储服务。数据拥有者将加密的数据上传至CSP，减少了用户的存储负担。为了减少用户（数据拥有者和数据用户）的计算负担，当撤销属性时，DSM完成密文更新工作；当数据解密时，CSP承担了解密过程中的部分计算。同时本文假设CSP是诚实并好奇的（honest but curious）。

数据拥有者（DO, data owner）：DO在将数据上传至CSP之前需要用对称密钥PK加密数据，然后基于本文所提方案加密对称密钥PK，通过对PK的安全共享完成数据的细粒度访问控制。

数据用户（DU, data user）：DU即系统中的消费者，能够自由地访问云中的密文数据资源。属性机构根据其属性为其生成私钥并用于解密密钥密文。若其属性没有被撤销且满足访问结构，则用户能够计算出最终明文。

4.2 形式化定义

首先给出本文相关符号及其含义，如表1所示。

表1 相关符号及其含义

RO-CP-ABE方案包含以下5个阶段。

1) 系统初始化阶段

AASetup(1λ)→{PK,MSK}：AA运行该算法，输入安全参数RK=λ，输出系统公钥PK和系统主私钥MSK。

DSMSetup(PK)→{DPK,DSK}：DSM 运行该算法，输入PK，输出DSM的公钥DPK和主私钥DSK。

2) 私钥生成阶段

AAKeyGen(id,PK,DPK,MSK,S)→{RK,SK,KEK′}：AA运行该算法，输入PK、DPK、MSK和属性集合S，输出用户私钥RK、转换密钥SK和属性群初始密钥KEK′。

DSMKeyGen(KEK′,S)→KEK ：DSM运行该算法，输入KEK′和S，输出用户属性群密钥KEK。

3) 数据加密阶段

Encrypt(PK,(M,ρ),m)→CT′：输入系统公钥PK、访问结构(M,ρ)和明文消息m，输出中间密文CT′。

DSMEncrypt(PK,DSK,CT′)→{Hdr,CT}：输入PK、DPK和CT′，输出密文头Hdr和最终密文CT。

4) 数据解密阶段

OutDecrypt(PK,Hdr,CT,SK,KEK)→CT：CSP运行该算法，输入PK、Hdr、CT和SK，输出转换密文。

Decrypt(PK,CT,CT,RK)→m：DU运行该算法，输入和RK，输出明文数据m。

5) 用户属性撤销阶段

UpKEK(DSK,KEK,attx)

运行该算法，输入DSK、KEK和被撤销属性attx，输出新的属性群密钥

ReEncryption(Hdr,CT,attx)：DSM运行该算法，输入Hdr、CT和被撤销属性attx，输出新的密文头和密文

4.3 安全模型

为证明所提方案可以有效抵抗用户合谋攻击，定义敌手可以询问2种类型密钥：1) 已撤销用户的私钥询问，其中，，但已撤销挑战属性；2) 未撤销用户的私钥询问，其中，，但S包含挑战属性。证明过程如下。

初始化A选择挑战属性Type-I和挑战访问结构并发送给B。其中，若att∗∉S，则一定有

系统建立B运行AASetup和DSMSetup后得到PK、MSK、DPK和DSK。然后，B更新关联属性att∗的密钥对和。最后，B将PK、DPK和发送给A，自己保留MSK、DSK和

询问阶段1A可以询问以下2种类型密钥。

已经被撤销。B运行AAKeyGen和DSMKeyGen算法获得RKI、SKI和KEKI，然后将它们发送给A。2) Type-II私钥询问：用户uII的属性集合SII不满足访问结构但是uII拥有属性。B运行AAKeyGen和DSMKeyGen算法获得RKII、SKII和KEKII，然后将它们发送给A。挑战阶段A提交2个等长消息m0和m1。B选择随机值b∈{0,1}，并运行Encrypt和DSMEncrypt算法获得Hdr*和CT，最后将二者传递给A。

询问阶段2类似询问阶段1。

猜测阶段A输出。若b′=b，则A赢得游戏，攻破所提方案。A攻破所提方案的优势定义为：

定义 1假设没有多项式时间的敌手能够以不可忽略的优势来攻破上述安全模型，则所提方案是选择安全的。

5 RO-CP-ABE方案构造

本节给出RO-CP-ABE方案的具体构建方法，并基于CDH假设给出了方案的安全性证明。

5.1 方案构造

1) 系统初始化阶段

AASetup(1λ)→{PK,MSK}：该算法首先选择阶为素数p的循环群G和GT，g是群G的生成元，存在映射e:G×G→GT。随机选取α,a∈Zp，随机选取h1,h2,…,hn∈G。输出系统主私钥MSK=gα和系统公钥PK=(g,e(g,g)α,ga,h1,h2,…,hn)。

DSMSetup(PK)→{DPK,DSK}：DSM 为每一个属性atti(1≤i≤n)选择一个随机指数ti∈Zp并计算Ti=gti，输出DSM的公钥DPK={Ti|1≤i≤n}和主私钥DSK={ti|1≤i≤n}。

2) 私钥生成阶段

AAKeyGen(id,PK,DPK,MSK,S)→{RK,SK,KEK′}：该算法随机选择r∈Z，然后计算K′=gα+arid，idp L′=grid，对于任意 atti∈S，计算K′=hridii，kek′=Trid。然后随机选择λ∈Z，计算K=(K′)λ，iip L=(L′)λ，Ki=(Ki′)λ，keki=(kek′i)λ。最后输出用户私钥RK=λ，转换密钥SK=(K,L,{Ki})和属性群初始密钥KEK′={atti,keki},atti∈S。

DSMKeyGen(KEK′,S)→KEK：该算法按2.4节中 KEK树为用户生成属性群密钥。对于每一个atti∈S，DSM 计算ϕi=Path(uid)∩Mincs(Gi)。若ϕi=∅，DSM停止计算；若ϕi≠∅，DSM计算，其中随机值θj所对应节点vj∈ϕi。然后输出KEK={atti,vj,keki,KEKi},atti∈S。

3) 数据加密阶段

Encrypt(PK,(M,ρ),m)→CT′：该算法随机选择向量用于共享加密指数s。对于1≤i≤l，计算，其中Mi是M的第i行。然后计算，对于。最后输出中间密文

DSMEncrypt(PK,DSK,CT′)→{Hdr,CT}：对于访问结构(M,)ρ中每一个属性atti，DSM随机选择并调用算法。然后重新加密中间密文CT′获得，计算密文头最后DSM将(CT,Hdr)上传到云服务商进行存储。

4) 数据解密阶段

当数据用户的属性满足密文的访问结构且用户属性未被撤销时，可以通过以下过程计算获得明文。

OutDecrypt(PK,Hdr,CT,SK,KEK)→CT：云服务商根据转换密钥SK和属性群密钥KEK计算T′、T′和，如式(1)～式(3)所示，然后云服务商将CT和CT发送给数据用户。

5) 用户属性撤销阶段

UpKEK(DSK,KEK,attx)当用户uz的属性attx被撤销时，DSM随机选择xσ并计算，然后用和替代DPK和DSK中的Tx和tx，获得新的 DSM 公钥和主私钥。DSM更新属性群并重新计算例如，，则。当用户u6的属性attx被撤销时，，则对于每一个数据用户，DSM计算然后计算和其中随机值对应节点最后，DSM 用替换KEK中的

ReEncryption(Hdr,CT,attx)DSM随机选择，重加密密文：最后

更新密文头为

5.2 安全证明

定理1若CDH假设在群G中成立，则没有多项式时间敌手能够攻破RO-CP-ABE方案，其中挑战矩阵为

证明若A在qI次Type-I询问和qII次Type-II询问后，攻破所提方案的优势为不可忽略的值ε=AdvA。那么，可以创造一个B能够以不可忽略的优势攻破CDH假设。

初始化挑战者将和发送给仿真者B，A选择挑战访问结构和挑战属性并传递给B。其中，若att∗∉S，则一定有

系统建立B随机选取并计算。输出公钥和系统主私钥MSK=gα。对于每一个属性B选择一个随机指数并计算。对于att∗，B随机选取x计算。输出公钥和主私钥然后B更新的密钥对，设置B更新 DSM 的公钥和DSM的主私钥。注意：为理论值，实际情况下B不知道z1，因此也不能计算

询问阶段1A可以询问2种类型密钥，B设置2个列表LI和LII，并初始化2个列表为空。

用户u的属性集合S满足访问结构(M∗,ρ∗)，II但是uI的属性已被撤销。B首先查看中是否存在uI。若存在，则B将发送个敌手A；否则，B随机选择，计算，其隐含设置。对于i≠x且atti∈SI，计算B产生并计算。其中，随机值θj与节点关联；针对， B 计算。然后，B随机选择值，计算获得

用户uII的属性集合SII不满足访问结构但是uII拥有属性。B首先查看中是否存在uII。若存在，则B将发送个敌手A；否则，B随机选择，计算。对于i≠x且，仿真者B计算，而后求交集然后，B根据交集结果计算，其中随机值jθ所对应节点对于，计算和其中随机值所对应节点

挑战阶段A提交2个等长的消息m0和m1。B随机选择b∈{0,1}和向量其用于共享加密指数s。对于1≤i≤l，计算，其中是M∗的第i行。然后，B计算

对于i≠x且，B随机选择k∈Z，ip并计算；对于，计算其意味着。B最终计算密文为

询问阶段2类似询问阶段1。

猜测阶段A输出一个值作为对b的猜测。假设A猜测b′=b，且。然后，仿真者B分别从LI和LII中选择对于，存在LI中的和LII中的相结合，使等式(7)成立。

如果B没有中止游戏，那么A的视觉和真实的攻击视觉相同。假设敌手A进行了qI次Type-I询问和qII次Type-II询问，B从LI和LII中正确地选中和的概率是，因此，B攻破CDH假设的优势为

6 方案分析及仿真

6.1 理论分析

6.1.1 功能比较

表 2表明对比方案的访问结构都具有强表达性，且可以灵活地表示属性的组合。所有方案都实现了属性级的用户撤销。文献[12,15]没有给出形式化的安全证明，相比较而言，文献[13,16]和本文方案给出了形式化安全证明，但只有本文方案基于弱假设 CDH完成安全证明。另外，在解密过程中，文献[15]和本文方案将部分计算外包给 CSP，有效地减少了用户的计算量。

6.1.2 通信成本

在进行通信成本对比之前，给出各符号所代表的含义，|p|、|g|、|gT|分别代表Zp、G、GT中元素的长度，|Ck|代表KEK的长度，nc、nk、na分别代表访问结构、私钥和系统中的属性数量，nu代表系统中的用户数量。

通信成本主要由密钥和密文产生，本文方案与相关方案的通信成本对比情况如表3所示。

AA与DU之间的通信成本主要由密钥产生。由于文献[15]和本文方案采用了解密外包技术，因此属性机构需要传送给数据用户一个最终解密密钥RT。另外，本文方案需要属性机构传输nk|g|个kek密钥给数据用户，用于后续生成属性群密钥。

AA与DO之间的通信成本主要由公钥产生。属性机构只需将公钥发送给DO，然后DO使用公钥对明文消息加密。

表2 本文方案与相关方案的功能对比

表3 本文方案与相关方案的通信成本对比

CSP与DU之间的通信成本主要由密文产生。文献[12,15]和本文方案使用了 KEK树技术，所以CSP不仅要发送密文，还要发送密文头和KEK密钥。文献[12,15]中，CSP需要额外发送大小为的密文头和大小为的属性群密钥。本文方案中，CSP需要额外发送大小为的密文头和大小为的属性群密钥，DU需要发送个kek密钥给云服务商。另外，文献[15]和本文方案采用了外包解密技术，因此DU需要将其大小为的外包密钥发送给CSP，由CSP代为解密。

CSP与DO之间的通信成本主要由DO生成的密文产生。

通过原理分析发现，本文方案与其他方案相比在存储成本与通信成本的开销方面基本持平，在某些方面开销略大。但是本文方案基于弱假设且在标准模型下完成了方案的安全性证明，能够抵抗用户的合谋攻击；本文方案将复杂的解密计算外包给CSP，同时由CSP完成属性群密钥更新和密文更新操作，有效较少用户的计算量。另外，文献[12,15]无法抵抗撤销用户与未撤销用户之间的合谋攻击，而抵抗用户合谋攻击时ABE方案最基本的安全需求。综合分析，本文方案具有一定的优势，更适用于实际情况。

6.2 实验仿真

本文基于 Ubuntu系统搭建实验环境，并基于Charm实现本文所提方案。首先本文用 10个属性构建了访问结构，并分别执行上述5种对比方案，每种方案执行10次，然后取其平均值作为最终值。需要注意，本文给出的时间为属性机构、DO和DU的计算时间，而云服务具有强大的计算能力，因此这里没有列出CSP的计算时间。5种方案各个阶段执行时间对比如图2(a)所示。

系统建立阶段文献[13]的执行时间大约是其他方案的2倍，这是因为文献[13]在系统初始化阶段需要为每个属性设置2个公共属性密钥。密钥生成阶段本文方案执行时间要大于其他方案，这是因为本文方案属性机构需要为每个属性设置一个kek密钥，同时本文方案采用外包技术，属性机构需要将密钥盲化。数据加密阶段文献[13]的执行时间同样是其他方案的 2倍，这是因为进行密文加密时，文献[13]需要为每个属性额外计算2个用于撤销后更新密文的组件，而其他方案撤销计算由第三方执行。数据解密阶段由于文献[15]和本文方案采用了外包解密技术，因此需要较少的计算量，这对于资源有限的用户至关重要。

本文方案由 CSP完成属性群密钥更新和密文更新计算，因此本节只仿真加解密计算。

如图2(b)所示，加密时间与访问结构复杂度呈正相关。另外，文献[13]需要为每个属性额外计算2个用于撤销后更新密文的组件，而其他方案撤销计算由第三方执行，所以文献[13]所需执行时间大约是其他方案的2倍，这在上文中已经分析。而其他4种方案的加密时间大致相同。

如图2(c)所示，解密时间与解密所需属性数量呈线性增长关系，由于文献[15]和本文方案采用了外包解密技术，其用户将复杂的计算外包给CSP，只需要进行少量计算就能够完成解密任务。在解密计算中，文献[15]只需计算一个双线性对操作和一个GT中的指数运算，而本文方案只需计算一个GT中的指数运算，与属性数量无关。

图2 仿真时间对比

综合分析，本文方案对于属性机构的计算需求稍高于其他方案；由于采用外包解密技术，相对于其他方案，本文方案对于用户的计算需求明显小于其他方案；同时，由DSM完成属性撤销过程中的全部计算任务，有效较少了AA和用户的计算量，因此可以得出本文方案在计算效率方面有较大优势。

7 结束语

属性级用户撤销是 ABE方案的一个重点研究方向。本文研究现有方案发现文献[12,15]存在用户合谋攻击，其原因为 2种方案中的KEK对于属性群中用户完全相同。基于此，本文提出了一种支持属性撤销的 ABE方案，有效地解决了上述问题。所提方案可以有效抵抗撤销用户与未撤销用户的合谋攻击，同时，该方案将复杂的解密计算外包给CSP，减轻了DU的计算负担。在标准模型下基于CDH假设完成安全证明。最后从理论和实验这 2个方面对所提方案的效率与功能进行了分析，结果表明所提方案可以安全实现属性级用户撤销，并具有快速解密的能力。