基于时间因子的可撤销可追踪属性基加密方案*

许城洲,王 晨,张文涛

(1.中国航天系统科学与工程研究院,北京 100037；2.中国航天科技集团有限公司,北京 100048)

1 引言

云技术为用户提供了便捷的共享途径和廉价的存储成本。希捷预测，到2025年，全球数据的增长量将达到163 ZB，将数据上传至云存储服务器成为越来越多的人选择。然而，将数据上传至云端会降低用户对数据的控制，有数据泄漏的风险。研究人员提出了很多加密方案[1 - 3]。在基于云技术的数据共享应用中，安全的数据保护和便捷的数据共享成为云环境中需要达成的目标。密文策略属性基加密CP-ABE(Ciphertext-Policy Attribute-Based Encryption)支持“一对多”的访问模式和细粒度的访问控制，被认为是云环境中实现数据安全共享的理想途径。研究人员针对云环境中不同应用场景的数据安全共享，提出了许多CP-ABE方案，使属性基加密机制在高效性、安全性和访问结构表达性等方面有了较大的提升。然而这些方案在前后向安全、用户追踪和撤销等方面仍有较多需解决的问题。

在云环境的应用中，用户撤销和用户属性撤销是CP-ABE方案需要解决的重要问题。例如，用户属性时间到期、用户密钥被盗用和滥用时，方案需要安全撤销机制以维护系统正常运行。撤销分为直接撤销[4 - 6]和间接撤销[7 - 9]2种形式。直接撤销通过证书撤销列表、证书撤销树等实现撤销，间接撤销通过定期发布更新密钥实现撤销。撤销也分为用户撤销[4，10，11]、用户属性撤销[12，13]和系统属性撤销[14]。用户撤销、用户属性撤销后，需要防止恶意用户使用撤销前的密钥对密文进行解密，即方案需要具有前向安全性。Boldyreva等[15]首次提出了可撤销ABE方案，授权机构维护一个撤销列表，周期性对系统用户密钥进行更新，通过不更新撤销用户密钥实现用户撤销。文献[16]利用时间戳为每个属性设定有效时间，通过服务器周期性更新用户密钥实现用户属性撤销。文献[17]通过服务器代理进行属性撤销，在撤销属性时，通过重加密技术生成重加密密钥对用户密钥和密文进行更新。文献[18]提出的支持撤销属性基加密方案完善了撤销方案的前向安全性，访问策略支持“与门”和“或门”，但是在撤销阶段，用户计算开销较大。文献[19]提出了基于属性组的支持属性撤销的属性基加密方案，方案可以抗合谋攻击，但是用户和属性授权机构存储开销较大。文献[20]将用户信息与二叉树相关联，并基于二叉树的管理实现用户撤销和追踪。文献[21]同样基于与用户信息相关联的二叉树实现了方案的可撤销和可追踪功能，并通过将用户属性名和属性特征值分离实现了隐私保护功能，但计算效率较低。

现有的CP-ABE方案中，访问策略一般限定判断用户是否拥有某种属性组合，从而实现访问控制。这些方案无法限定用户拥有属性的时间，即不同用户在不同时间拥有同一属性在访问策略的限定中同样有效。云环境的访问控制应用中，用户可能希望设定某一时间点之前或之后拥有特定属性的人群能够访问自己的数据，因此在该应用场景需求下，需要对用户拥有属性的时间进行区分，即方案需要具有后向安全性。文献[22]设置时间周期树结构管理用户密钥，在用户解密阶段验证用户密钥是否在有效期内，从而实现基于时间的访问控制。文献[23]在其基础上增加了可追踪功能并通过外包降低了本地计算开销，然而方案均基于系统整体时间限定用户密钥有效期，无法在文件中对单个属性进行时间限制。群元素运算计算开销较大，结合时间因子的属性基加密方案解密阶段包含时间认证和属性认证2个阶段，与多因素认证在流程上相似，汪定等[24，25]提出的多因素认证方案使用哈希运算和逻辑位运算实现参数加解密和验证，方案计算开销较低。

为了同时实现CP-ABE方案前后向安全、用户追踪和撤销功能，本文提出一种基于时间因子的可撤销可追踪属性基加密方案。该方案具有用户追踪、用户撤销和用户属性撤销功能，且具有前后向安全性，主要研究工作如下：

(1)提出了一种基于时间因子的属性基加密方案。该方案在生成用户密钥时，根据用户获取属性时间生成时间因子并标记用户密钥中的属性特征值，数据拥有者上传数据时对用户拥有属性时间进行限定，从而实现基于时间和属性的访问控制，丰富了系统访问策略并实现了方案的后向安全性。

(2)实现了快速的用户撤销和用户属性撤销。时间认证服务器保留用户属性时间参数，在用户解密时，基于属性时间参数进行属性时间认证。用户属性撤销时，时间认证服务器更改属性时间参数值并更新用户其他属性时间因子；用户撤销时，时间认证服务器删除属性时间参数即可。方案降低了撤销计算开销，且避免了撤销时对其他用户造成干扰。

(3)实现了对恶意泄露密钥用户的高效追踪和属性时间认证外包。将用户唯一标识uid加密后所得ruid融入用户密钥中，用户密钥泄露时通过分离并解密ruid实现用户追踪。采用认证外包技术将属性时间认证外包给时间认证服务器，降低了用户解密时的本地计算开销。

2 相关知识

2.1 双线性映射

设循环乘法群G和GT的阶为素数q，群G上的一个生成元为g，存在双线性映射e:G×G→GT，该双线性映射具有以下性质：

(2)非退化性：∃g1,g2∈G，满足e(g1,g2)≠1。

(3)可计算性：∀g1,g2∈G，e(g1,g2)可在多项式时间内计算得到。

2.2 困难假设

设G是以g为生成元、阶为素数q的循环乘法群，e为双线性映射，a,b,c是Zq中的随机元素，R是G中的随机元素。判定性双线性Diffie-Hellman DBDH(Decision Bilinear Diffie-Hellman)问题假设定义如下：

给定2个元组:(g,ga,gb,gc,e(g,g)abc)和(g,ga,gb,gc,R)。如果在任意多项式时间内算法A解决G中的DBDH问题的优势为：

ε=|Pr[A(g,ga,gb,gc,Z=e(g,g)abc)=0]

-Pr[A(g,ga,gb,gc,Z=R)=0]|

定理1若对于任何多项式时间算法解决DBDH困难问题的优势ε是可以忽略的，DBDH问题假设成立。

2.3 安全模型

本节给出所提CP-ABE方案的安全模型。该安全模型由攻击者A和挑战者B之间的交互性游戏定义。攻击者以不可忽略的优势攻破DBDH困难问题。

初始化：A选择2个挑战访问结构W0和W1，并发送给B。

系统建立：B运行设置算法，生成系统公开参数MPK，并将其发送给A。

猜测：攻击者输出对τ的猜测结果τ′，如果τ=τ′则A赢得该游戏。

A在该游戏中的优势定义为：adv=|Pr[τ=τ′]-1/2|。

定理2如果在任何多项式时间内，A赢得该游戏的优势可以被忽略，则该CP-ABE方案被认为是选择性CPA安全的。

3 方案描述

3.1 系统形式化描述

本文方案中包含5类实体：属性授权终端AA(AttributeAccess)，负责初始化系统并为每个用户生成用户密钥，接收用户撤销请求或向用户和时间认证服务器发出属性撤销指令；数据拥有者DO(DataOwner)，为数据设置访问策略并根据访问策略对数据进行加密，最后将密文上传至云存储服务器CSS(CloudStorageServer)；CSS,负责存储DO上传的密文和响应用户数据下载需求；数据使用者DU(DataUser)，从授权中心获取用户密钥，从CSS下载密文后将属性密钥时间参数上传至时间验证服务器TVS(TimeVerificationServer)进行验证，用户属性和时间均满足访问策略即可对密文解密；TVS，接收DU上传的用户和密文属性时间参数，进行时间验证并返回验证结果。方案的形式化定义描述如下：

(1)系统建立：AA根据安全参数ρ和系统属性集生成系统公钥MSK和系统私钥MPK。

(2)密钥生成：AA为用户分配属性集，并生成用户唯一身份标识uid、用户唯一时间参数Tr和属性密钥，将Tr发送给TVS，将uid和属性密钥发送给用户。

(3)加密：DO设置访问策略P，使用加密算法对数据m进行加密，生成密文c。

(4)属性时间认证：DU将自己密钥中属性时间因子和密文中属性时间因子上传至TVS，TVS进行属性时间认证并将认证结果返回给DU。

(5)解密：若TVS返回认证结果表明DU的属性集满足P，DU可以进行解密并恢复数据m，否则解密失败。

(6)用户属性撤销：TVS为用户选择新的时间参数Tr′，对用户密钥时间参数进行重加密，用户删除该属性相关参数。

(7)用户撤销：TVS删除本地存储的用户时间参数Tr。

(8)追踪：对用户密钥进行验证，并根据用户中参数解密用户uid从而追踪用户。

3.2 方案概述

基于时间因子的可撤销可追踪的属性基加密方案通过时间因子差异化不同用户的同一属性，丰富了访问策略，同时使方案具有前向安全性和后向安全性，另外方案也支持用户撤销和用户属性撤销，具体构造如下：

(1)系统建立阶段。

令A={A1,A2,…,An}为系统属性空间，ρ为安全参数，循环乘法群G和GT的阶为素数q，群G上的一个生成元为g，双线性映射e:G×G→GT，随机值α∈Zq，计算Y=e(g,g)α，为系统中每个属性Ai选择随机值ki∈Zq(i∈[1,n])，计算Ki=gki。选择2个单向抗碰撞的哈希函数H1:{0,1}*→{0,1}lT，H2:{0,1}*→{0,1}ρ，其中lT为时间因子长度。选择对称加密算法Eu(ku,id)，其中ku为系统加密用户身份标识id密钥。选择非对称加解密算法Ep(kY,m)和Dp(kx,c)，其中kY和kx分别代表加密公钥和私钥，系统公钥和私钥分别为：

MPK=(H1,H2,g,Y,kY,{Ki})

MSK=(α,{ki},ku,kx)

(2)密钥生成。

系统为每个用户分配唯一身份标识uid，选择随机值作为Tr并由AA和TVS保存，计算ruid=Eu(ku,uid)，D0,1=ruid，D0,2=uid，选择随机值vuid∈Zq，计算D1=gα+vuid，授权中心为用户属性集Uid中每个属性Ai选择随机值λi∈Zq，计算D2,i=gλi，标记用户获取属性Ai的时间为Ti,1，计算D3,i=gkiλi+vuidruid，计算D4,i,1=H1(ruid‖uid‖atti‖Tr)⊕Ti,1，其中atti为属性Ai的名称，D4,i,2=H1(uid‖ruid‖Tr‖Ti,1)，用户密钥为(D0,1,D0,2,D1,{D2,i},{D3,i},{D4,i,1,D4,i,2})。

(3)加密。

(4)属性时间认证。

DU将密文中的{C3,i}和密钥中的{D4,i,1,D4,i,2}上传至TVS，TVS计算：

ai‖Ti,2‖attm‖BA=Dp(kx,C3,i)

ht′i=H1(r′uid‖uid′‖att′i‖Tr)

T′i,1=D4,i,1⊕ht′i

TVS根据标记BA比较Ti,2和T′i,1，如果BA标记为前向，Ti,2≥Ti,1；如果BA标记为后向，Ti,2

当用户属性集中所有属性满足访问策略属性时间要求时，TVS返回用户{TVi}。

(5)解密。

DU的属性集时间认证成功会从TVS处返回{TVi}，DU计算：

∏e(g,g)si vuid ruid

DU可以通过计算Cm=H2(c‖m)来判断是否解密成功。如果解密成功，则输出明文m，如果解密失败，返回⊥。

(6)用户属性撤销。

当系统中用户uid需要撤销属性Ai时，AA向TVS发送属性撤销指令，TVS暂停对用户uid的属性时间认证，用户上传自己密钥中的{D4,j,1,D4,j,2|Aj∈Uid}。TVS为用户重新选择Tr′，计算：

ht′j=H1(ruid‖uid‖attj‖Tr)

Tj,1=D4,j,1⊕htj

D′4,j,1=H1(ruid‖uid‖attj‖Tr′)⊕Tj,1

D′4,j,2=H1(ruid‖uid‖Tr′‖Tj,1)

TVS向用户返回{D′4,j,1,D′4,j,2}，更新用户时间参数Tr为Tr′。用户收到TVS返回的消息后，更新本地密钥中的{D4,j,1,D4,j,2}并删除(D2,i,D3,i,D4,i,1,D4,i,2)。

(7)用户撤销。

当系统需要撤销用户uid时，AA向TVS发送用户撤销指令，TVS删除本地用户时间参数Tr即可。

(8)用户追踪。

首先对用户进行以下检查：

D0,1,D0,2∈Zp

D1,{D2,i},{D3,i}∈G

e(D2,i,Ki)e(D1g-α,gD0,1)=e(g,D3,i)≠1

如果用户私钥通过检查，计算uid=Du(ku,ruid)，根据uid得到对应用户；否则，返回⊥。

4 安全性分析

4.1 抗串谋攻击

CP-ABE方案能够抵抗串谋攻击，是为了避免多个属性集不满足访问策略的用户，通过相互交换信息，从而得到满足访问策略的用户属性集。用户对密文进行解密时，须计算得到e(g,g)αs，得到e(g,g)αs需要对密文中的{C1,i}和用户D1进行双线性配对运算：∏e(C1,i,D1)=e(g,g)αs+vuids。vuid是随机生成的，不同的用户的vuid不相等，用户无法通过D1=gα+vuid计算得到α+vuid，因为这是离散对数问题DLP(DiscreteLogarithmProblem)困难的。在用户密钥中vuid同时存在于D3,i=gkiλi+vuidruid中，用户可得gki和gλi，但是无法计算得到gkiλi，这是判定性Diffie-HellmanDDH(DecisionDiffie-Hellmam)困难的。在用户撤销和用户属性撤销时，通过更新或删除用户密钥中的时间参数Tr实现，参数中不包含vuid，用户撤销过程不会造成参数泄露。综上，用户之间合谋也无法突破盲化因子vuid对密文的保护，因此本文方案可以抵抗合谋攻击。

4.2 安全证明

本节采用文献[26]中的安全证明方法证明所提方案在DBDH假设下是选择性CPA安全的。

证明若攻击者A可以以一个不可忽略的优势ε>0在多项式时间内破解本文方案，那么存在一个模拟器β可以在多项式时间内以不可忽略的优势ε/2解决DBDH问题。

循环乘法群G和GT的阶为素数q，群G上的一个生成元为g，双线性映射e:G×G→GT，a,b,c是Zq中的随机元素，R是GT中的随机元素。挑战者D抛掷一枚硬币τ1∈{0,1}，选择四元组(ga,gb,gc,Z)发送给β，模拟器β在之后的步骤中扮演挑战者的角色。当τ1=0时，四元组(ga,gb,gc,Z)=(ga,gb,gc,e(g,g)abc);当τ1=1时，四元组(ga,gb,gc,Z)=(ga,gb,gc,R)。

(1) 初始化。

A首先提交2个挑战访问结构W0和W1，并将其发送给β，β随机抛掷一枚硬币选取随机数τ1∈{0,1}。

(2) 系统建立。

计算Y=e(ga,gb)=e(g,g)ab，为系统中每个属性Ai选择随机值ki∈Zq，计算Ki=gki。选择2个哈希函数H1:{0,1}*→{0,1}lT，H2:{0,1}*→{0,1}ρ。选择对称加密算法Eu(ku,id)，选择非对称加解密算法Ep(kY,m)和Dp(kx,c)。

β将参数(H1,H2,g,Y,kY,{Ki})发送给攻击者A。

(3) 查询阶段1。

(4) 挑战。

A随机选择2个等长的数据M0和M1，并将它们提交给β。β随机选择数τ∈{0,1}对数据Mτ进行加密计算：C1,i=gsi，C2,i=gkisi+aiTi,2，C3,i=Ep(kY,ai‖Ti,2‖attm‖BA)，c=MτV，Cm=H2(c‖Mτ)并发送给A。生成加密密文CT=(c,Cm,{C1,i},{C2,i},{C3,i}),β将密文返回给A。

(5) 查询阶段2。

A重复查询阶段1的询问，限制条件与阶段1相同，β如查询阶段1一样回应A。

(6) 猜测。

A提交一个对τ的猜测值τ′。如果τ=τ′，则τ1=0；否则τ≠τ′，则τ1=1。

当Z=e(g,g)abc时，由DBDH问题，A猜测到τ=τ′的优势为ε，此时：

Pr[τ=τ′|V=e(g,g)abc]≥1/2+ε

当τ=τ′时，β提交对τ1的猜想τ′1=0，此时：

Pr[τ1=τ′1|V=e(g,g)abc]=1/2+ε

当Z=R时，由DBDH问题假设，V是选择的随机数，A无法得到关于τ的任何消息，当τ≠τ′时，A无法区分τ1，此时有Pr[τ≠τ′|V=R]=1/2。当τ≠τ′时，β提交对τ1的猜想τ′1=1，此时有Pr[τ1=τ′1|V=R]=1/2。

综上，挑战者β破解DBDH困难问题的优势为：

Pr[τ1=τ′1|V=R])-1/2≥ε/2

不存在攻击者在多项式时间内可以以不可忽略的优势破解DBDH困难问题，因此不存在以不可忽略的优势打破本文方案，本文方案是选择性CPA安全的。

5 性能分析

本节将文献[8]方案、文献[20]方案、文献[21]方案、文献[23]方案和本文方案在功能和计算开销2个方面进行分析比较。方案中双线性配对运算、椭圆曲线标量乘法和群元素幂运算的运算开销较大，因此忽略其他运算开销较小的运算，如哈希运算、逻辑位运算和加减运算等。部分方案采用计算外包的方式降低本地计算开销，方案计算代价分析时仅考虑本地计算开销。表1中列举了在进行方案性能对比时所用到的符号和说明，其中文献[20,21,23]使用密钥加密密钥KEK(KeyEncryptionKey)树结构。

Table 1 Symbol explanation表1 符号说明

表2给出了本文方案和文献[8,20,21,23]方案的功能对比，本文方案同时实现了用户撤销和用户属性撤销，其余方案仅实现用户撤销或者用户属性撤销。本文方案在撤销用户属性时，仅需要更新用户密钥中的时间标记因子，不需要更新所有密文，降低了运算开销。本文方案在撤销用户时，仅需要删除用户时间参数Tr，从而实现快速撤销；文献[20,21，23]需要更新系统密文；文献[8]需要通过额外设置系统版本标签和更新用户密钥实现。本文方案同时实现了可追踪和可验证功能，文献[8,20,21]中部分实现该功能。本文方案通过为用户每个属性标记属性获取时间，并在解密时与密文中时间标记进行比较，增加了访问策略中对用户拥有属性时间限制功能，实现了方案的后向安全，文献[23]通过标记用户属性有效期实现了方案的后向安全，但是方案没有细化标记用户属性时间；本文方案通过用户密钥更新和Tr标识管理，保证撤销属性用户和撤销用户无法继续解密密文，实现了方案的前向安全性，计算开销基于用户撤销和用户属性撤销。最后方案通过将认证流程外包给时间认证服务器，降低了用户本地计算开销。

Table 2 Comparison of functions表2 功能比较

表3给出了本文方案和文献[8,20,21,23]方案的性能对比。本文方案对用户获取属性时间进行标记，解密时进行时间验证，从而实现了方案的前后向安全并丰富了系统的访问策略；在密钥生成阶段和加密阶段为每个属性生成随机因子，增加了系统抗串谋攻击的能力和提升了密文的安全性；将时间因子相关计算采用哈希运算，降低了因添加访问功能导致的加密阶段和密钥生成阶段计算开销。本文方案通过关键参数控制的方式实现用户撤销和用户属性撤销，不需要通过KEK树实现，不需要进行文献[20,21,23]中与KEK树相关的计算，且方案中使用群元素乘法较少，所以方案中的加密时间和密钥生成时间少于其他方案的。在解密阶段，由于本文方案加密和密钥生成阶段为每个属性生成随机值，解密时需要逐个配对和消解，带来一定的计算开销，本文方案解密开销低于文献[8,21]方案的，高于文献[20,23]方案的。在用户属性撤销阶段，由于仅需要更新撤销用户密钥中属性时间标记，且撤销过程中运算为哈希运算和逻辑位运算，计算均由TVS执行，本地计算开销可忽略不计，文献[20,21,23]需要更新系统中密文实现，用户属性撤销开销低于其他开销，当系统撤销用户时，仅需要删除用户时间参数Tr即可，计算开销忽略不计。

Table 3 Comparison of computing overhead表3 计算代价比较

6 实验仿真

本文对表2中方案进行了实验仿真，实验运行环境为Intel(R) Core(TM) i5-8259U CPU @3.2 GHz，8.00 GB内存，MacOS Big Sur 11.3操作系统。仿真程序采用Python(版本3.8)，基于PyPBC库(版本0.2)和PyCharm开发环境编写。

图1展示了5个方案密钥生成时间对比。由图1可知，本文方案密钥生成阶段时间计算开销低于对比方案的，随着用户属性数量的增加，本文方案所需密钥生成时间增长低于对比方案的。

Figure 1 Comparison of key generation time 图1 密钥生成时间对比

图2展示了5个方案加密时间对比。由图2可知，本文方案加密阶段时间计算开销总体低于对比方案的，随着访问策略中属性数量的增加，本文方案所需加密时间与其他方案增长速度接近。

Figure 2 Comparison of encryption time图2 加密时间对比

图3展示了方案的解密时间对比。由图3可知，本文解密时间高于文献[8,20,23]方案的，本文方案为每个属性生成一个随机值，并添加参数实现追踪功能，解密阶段所需消除的参数较多，方案仅将时间认证外包给服务器，本地解密阶段计算开销较大。

Figure 3 Comparison of decryption time图3 解密时间对比

图4展示了方案的用户撤销时间对比。由图4可知，本文用户撤销时间远低于其他方案的，这是因为文献[21,23]需要维护一个撤销列表，在撤销用户时，更新撤销列表并对密文进行重加密，本文方案在用户撤销时，仅需要TVS删除用户时间参数Tr即可，计算量可忽略。

Figure 4 Comparison of user revocation time图4 用户撤销时间对比

图5和图6分别展示了5个方案密文大小和用户密钥大小对比。由图中可知，本文方案的用户密钥大小随着属性数量增加，增长较快，存储开销高于其他方案的，这是因为本文为用户属性和访问策略中属性增加了时间因子相关的标记和时间因子验证项，增加了存储开销。密文存储开销稍低于其他方案的，但增长速度与其他方案的相近。

Figure 5 Comparison of ciphertext size图5 密文大小对比

Figure 6 Comparison of user key size图6 用户密钥大小对比

7 结束语

为了解决CP-ABE方案中存在的前后向安全、用户追踪和撤销等问题，本文提出了一种基于时间因子的可撤销可追踪的属性基加密方案，通过为属性添加时间标记因子，实现了方案基于时间因子的细粒度访问控制，丰富了系统访问控制策略，实现了方案前后向安全。对于系统中存在用户泄露密钥的风险，增加了可追踪功能。设计了高效的用户属性撤销和用户撤销机制，系统仅需要更新用户密钥，不会对其他用户造成干扰和不需要对系统中文件进行重加密，相比已有的方案，方案撤销效率更高，更适合在用户和系统数据较多的应用场景。本文方案可抗合谋攻击，且在DBDH假设下是选择性CPA安全的。但是，本文方案仍存在一些待优化的问题，如解密阶段用户计算量较大，密钥存储开销和密文存储开销较大，未来工作中希望能够研究并解决。