随着分布式存储与计算技术(如云存储和云计算)的迅速发展与成熟, 研究具备匿名性特点的密码机制变得尤为重要.Sahai和Waters^[1]将基于身份的加密算法加以扩展和改进, 提出了基于模糊身份的加密方案.该方案首次引入属性的概念, 用属性集合表示用户, 以实现对其的匿名性保护; 同时, 基于特定的访问结构对数据进行加密, 只有用户属性满足访问结构时, 才能成功解密密文.在此基础上, 相关学者展开了一系列基于属性的密码机制研究^[2-4], 并根据访问策略嵌入位置的不同, 将属性基加密算法分为密文策略和密钥策略两类:密钥策略的属性基加密方案(key-policy attribute-based encryption, 简称KP-ABE)^[2]将解密策略与用户的私钥绑定, 密文策略的属性基加密方案(ciphertext-policy attribute-based encryption, 简称CP-ABE)^[3]则将密文与解密策略绑定.

属性基加密方案使用属性集合来描述用户, 然而在实际应用中, 不同的用户往往具有部分相同的属性, 而且这些属性存在属性到期、密钥泄露、属性变更等问题.因此, 属性撤销成为属性基加密方案中亟需解决的问题, 即:在用户属性变更时, 如何及时更新用户权限, 确保用户不能使用旧密钥解密密文.其中研究的难点在于在对某一用户的属性进行撤销时, 不影响系统中拥有该属性的其他用户.此前, 大多数的ABE方案^[5-8]主要关注访问策略的表达能力, 并未着重考虑属性撤销问题.2009年, Attrapadung等人^{[9, 10]}在已有ABE方案的基础上, 结合基于身份的组播加密技术^[11]与线性秘密共享(LSSS)技术^[12], 提出了ABE方案的两种撤销模式:间接撤销和直接撤销.

●  间接撤销由授权机构执行, 采用半可信仲裁者方式或在密钥中加入时间信息, 通过周期性地更换密钥实现属性撤销.目前的大多数方案都采用间接撤销^[13-15], 其优势在于加密时不需要获取撤销列表, 使用比较灵活.但间接撤销的撤销代价比较大, 且需要授权中心进行密钥更新, 容易形成系统瓶颈;

●  在直接撤销模式下, 发送方将撤销列表直接嵌入到密文中完成用户属性的撤销, 因此不影响其他用户, 但存在撤销粒度较粗的问题.而方案[10, 16-18]只能解决用户撤销问题, 即撤销某用户的所有权限, 但不能针对部分权限进行修改, 因此同样无法实现细粒度的属性撤销.

为了实现细粒度的属性直接撤销, 学者们先后提出了一系列改进方案^[19-24].Hur^[19]采用二叉树方法, 提出了一种支持属性直接撤销的CP-ABE方案.然而, 该方案缺乏严格的安全模型和安全性证明, 并且无法抵抗合谋攻击.王鹏翩等人^[20]通过为用户分配两个访问树的方法实现了属性的细粒度撤销, 但该方案只能在密文中嵌入一个属性的撤销信息, 无法满足属性变化频繁的实际应用需求.文献[21]中, Ibraimi等人通过半可信第三方持有部分密钥与撤销列表的方式实现属性的即时撤销, 但需要确保第三方的高度可信与实时在线.上述所有支持撤销的属性基加密方案不仅在属性撤销上存在或多或少的不足, 更普遍存在一个安全隐患:属性授权中心掌握所有用户的私钥, 因此可以伪装成任意一名用户解密密文^[25].一旦授权中心被攻破, 用户存储在云端的加密信息即可被非法获取并使用.

本文针对现有方案的不足, 提出一种抗不可信授权中心破译攻击的支持细粒度属性直接撤销的CP-ABE方案.该方案采用访问树结构实现访问策略, 当用户属性满足访问树判别条件时, 即可解密密文.针对不可信授权中心的问题, 本方案中用于生成用户私钥的秘密参数β和t_j分别由系统中心SA(system authority)和属性授权机构AA(attribute of authority)产生, 从而约束了不可信授权中心的攻击能力, 有效避免了密文破译攻击.在属性撤销方面, 本方案采用属性授权中心实时更新属性撤销名单, 并结合密文重加密的方式, 可以对任意用户的任意属性单独进行撤销, 而不影响其他用户, 以确保属性的细粒度撤销.同时, 通过在密文中嵌入与用户撤销属性相关的秘密信息, 产生与属性撤销名单一一对应的密文, 保证密文只能够被有效用户解密.与Attrapadung方案^[10]相比, 本文方案能够实现细粒度的属性直接撤销.本文对属性可直接撤销的CP-ABE方案进行了严格的形式化安全定义, 并在随机预言机模型下证明所提方案在适应性选择密文攻击下具备密文不可区分性, 并能抵抗不可信授权中心的破译攻击.性能分析表明:本文方案在保证更细的撤销粒度和系统安全性前提下, 算法效率也具有一定的优势.

本文第1节介绍相关的预备知识.第2节给出属性可直接撤销的CP-ABE方案及其安全性的形式化定义.第3节提出支持细粒度属性直接撤销的CP-ABE方案.第4节从正确性、安全性、效率等3个方面对所提方案进行证明和分析.最后对全文进行总结.

1 预备知识

本节给出基于属性加密方案的相关定义与困难问题假设.

1.1 拉格朗日插值法

若已知f(x)在互不相同的d处的函数值, 即函数过d个已知的点, 那么能够构造出d-1阶的x的多项式函数f(x), 且此f(x)是存在且唯一确定的, 其求解方法如下:

$f(x) = \sum\limits_{i = 1}^d {f({x_i})\left( {\prod\limits_{j = 1, j \ne i}^d {\frac{{x - {x_j}}}{{{x_i} - {x_j}}}} } \right)} $

(1)

称公式(1)为拉格朗日插值多项式.

1.2 访问树

访问树是访问结构的一种表达形式, 不仅支持门限方式的访问策略, 也支持表达“与”、“或”等逻辑运算.为方便表述, 对于访问树中的任意节点x, 有如下定义.

●  Parent(x):节点x的父节点, 对根节点root外的所有节点有效;

●  Children(x):节点x的子节点集合;

●  Num(x):节点x的子节点个数;

●  index(x):节点x在同一层次节点中的序号, 即为其父节点的子节点集合中的编号;

●  attr(x):节点x表征的属性, 当且仅当x为叶子节点时有效.

访问树中的每一个非叶子节点都表征一个门限, 门限值n_x满足1≤n_x≤Mum(x).“或”门的门限值n_x=1, “与”门的门限值n_x=Num(x).

定义2(访问结构(access structure)).令参与方集合为P={P₁, P₂, …, P_n}, 访问结构A是2^P的一个非空集合.访问结构A中的集合称为授权集合, 不在访问结构A中的集合称为非授权集合.

1.3 困难问题假设

定义3(判定性q-BDHE假设(decision q bilinear Diffie-Hellman exponent assumption)).设群G₁, G₂是p阶循环群, 双线性映射e:G₁×G₁→G₂, 给定随机生成元g, 随机数s, a∈Z_p, 计算:

$Y = (g, {g^s}, {g^a}, {g^{({a^2})}}, ..., {g^{({a^n})}}, {g^{({a^{n + 2}})}}, ..., {g^{({a^{2n}})}}).$

给定随机数V∈_RG₂, 若不存在有效算法C能够在多项式时间内以不可忽略的优势区分V与$e{(g, g)^{{a^{n + 1}}s}}$, 则假设成立.

定义4(DDH问题假设(decision Diffie-Hellman problem)).设群G₁, G₂是p阶循环群, 双线性映射e:G₁× G₁→G₂, 随机生成元为g, 随机数x, y, z∈Z_p, 给定元组⟨g, g^x, g^y, g^xy⟩和⟨g, g^x, g^y, g^z⟩, 若不存在有效算法C能够在多项式时间内以不可忽略的优势判断z是否等于xy mod p, 则假设成立.

2 算法形式化定义与安全模型 2.1 形式化定义

本节给出可撤销的密文策略属性基加密方案的形式化定义.CP-ABE方案中, 密文与断言(Γ, term)相关联, 其中, Γ代表属性集合, Φ代表满足term的Γ的非空子集.假设ω为解密者的属性集合, 只有存在ω'∈Φ使得ω'⊆ω, 解密者才能成功解密密文.

直接可撤销的密文策略的基于属性加密(CP-ABE)方案涉及3个实体:系统中心、属性授权机构、用户, 由以下6个算法构成.

(1) 初始化算法Setup(1^λ)→(PK, MK):由系统中心运行的概率性随机算法, 输入安全参数1^λ, 系统中心输出公开参数PK和系统主密钥MK;

(2) 密钥生成算法KeyGen(ID, ω, MK)→SK_{ID, ω}:由属性授权机构运行的概率性随机算法, 输入MK、用户的身份ID及其属性集合ω, 属性授权机构输出用户的私钥SK_{ID, ω};

(3) 加密算法Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M, R, PK)→CT:由数据拥有者运行的一个概率性随机算法, 输入系统公开参数PK、明文消息M、访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销信息R, 输出密文CT;

(4) 重加密算法ReEncrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M, R, PK)→CT:由系统中心运行的概率性随机算法, 输入系统公开参数PK、密文CT、访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销信息R, 输出新密文CT;

(5) 解密算法Decrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, SK_{ID, ω}, CT, R)→M:由解密者运行的一个确定性算法, 输入私钥SK_{ID, ω}、与访问策略${\mathit{\Gamma} _{{\omega ^*}}}$对应的密文CT和属性撤销信息R, 如果${\mathit{\Gamma} _{{\omega ^*}}}(\omega ) = 1$, 且SK_{ID, ω}不涉及R中的撤销事件时, 则输出明文消息M, 否则输出错误符号⊥;

(6) 撤销算法Revocation(MK, ID_k, λ_k, attr(j))→R:由属性授权机构运行的确定性算法, 输入待撤销属性attr(j)及用户ID_k, 输出属性撤销信息R.

2.2 安全模型

在此给出适用于本文算法的安全特性的形式化定义.

定义5.一个基于属性的加密方案Π=(Set, KGen, Rev, Enc, ReE, Dec)在选择密文攻击下是不可区分的, 如果没有概率多项式时间的敌手A以一个不可忽略的优势ε在以下游戏中获胜.

(1) 初始化:挑战者C运行初始化算法, 利用系统安全参数产生公共参数PK和主密钥MK.如果敌手A为恶意系统中心SA, C将PK和秘密参数⟨α, β, λ_i⟩发送给A, MK保密; 如果敌手A为恶意属性授权机构AA_k, C将PK, MK和秘密参数α发送给A, 秘密参数⟨β, λ_i⟩保密.敌手A输出挑战访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销列表R;

(2) 阶段1:敌手A适应性地执行一系列预言机询问.

a) 私钥解析询问:选择用户ID_i及其属性集ω_i, 向C询问对应用户的私钥, 要求ID_i∈R或ω_i不满足访问策略${\mathit{\Gamma} _{{\omega ^*}}}$, C运行KeyGen算法产生私钥$S{K_{{\omega _i}}}$, 并将$S{K_{{\omega _i}}}$发送给A;

b) 密文解析询问:选择密文CT, 向C询问在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下CT对应的明文M, C运行Decrypt算法恢复出明文M, 并发送给A;

(3) 挑战:敌手A选择两条长度相等的明文M₀, M₁发送给挑战者.挑战者C随机选取b∈{0, 1}, 运行Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M_b, R, PK)算法, 生成消息M_b在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下的询问密文CT^*, 并返回结果给A;

(4) 阶段2:如阶段1所示, A继续执行私钥解析询问和密文解析询问;

(5) 猜测:敌手A输出对b的猜测b'.如果满足以下条件, 则敌手A在游戏中获胜.

ⅰ) b'=b;

ⅱ) A未对(${\mathit{\Gamma} _{{\omega ^*}}}$, CT^*, R)进行密文解析询问.

定义6.一个基于属性的加密方案Π=(Set, KGen, Rev, Enc, ReE, Dec)能够抵抗不可信授权中心的破译攻击, 如果没有概率多项式时间的敌手A以一个不可忽略的优势ε在以下游戏中获胜.

(1) 初始化:挑战者C运行初始化算法, 利用系统安全参数产生公共参数PK和主密钥MK.如果敌手A为恶意系统中心SA, C将PK和秘密参数⟨α, β, λ_i⟩发送给A, MK保密; 如果敌手A为恶意属性授权机构AA_k, C将PK, MK和秘密参数α发送给A, 秘密参数⟨β, λ_i⟩保密.敌手A输出挑战访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销列表R;

(2) 阶段1:敌手A适应性地执行一系列预言机询问.

a) 私钥解析询问:选择用户ID_i及其属性集ω_i, 向C询问对应用户的私钥, 要求ID_i∈R或ω_i不满足访问策略${\mathit{\Gamma} _{{\omega ^*}}}$, C运行KeyGen算法产生私钥$S{K_{{\omega _i}}}$, 并将$S{K_{{\omega _i}}}$发送给A;

b) 密文解析询问:选择密文CT, 向C询问在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下CT对应的明文M, C运行Decrypt算法恢复出明文M, 并发送给A;

(3) 挑战:C运行Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M^*, R, PK)算法生成消息M^*在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下的密文CT^*, 并返回结果给A;

(4) 阶段2:如阶段1所示, A继续执行私钥解析询问与密文解析询问;

(5) 攻击:游戏最后, A输出消息M', 如果满足以下条件, 则A在游戏中获胜.

ⅰ) M'=M^*;

ⅱ) A未对(${\mathit{\Gamma} _{{\omega ^*}}}$, CT^*, R)进行密文解析询问.

3 细粒度属性直接可撤销的CP-ABE加密方案

本文在Attrapadung等人方案^[10]的基础上, 提出一种属性可直接撤销的CP-ABE方案, 所提CP-ABE方案支持加密方定制访问树结构.方案由初始化、密钥生成、属性撤销、加密、重加密、解密这6个阶段组成.

3.1 初始化Setup(1^λ)

系统中心SA(system authority)选择一个双线性映射e:G₁×G₁→G₂, 其中, G₁, G₂是两个q阶循环群.然后, 选取生成元g, h, v∈G₁, 随机数α, β∈Z_q, 并且计算Z=e(g, g)β, v^β.最后输出系统公开参数PK=⟨g, v^β, e, Z, q⟩.对于系统中的每一名认证用户ID_i, SA选取唯一的秘密参数λ_i∈Z_q, 通过安全信道发送λ_i, β至用户, 发送α, h至各个属性授权机构AA_k, 其中, k∈{1, ..., n}为各属性属权机构的编号, n为系统中属性授权机构的数量.

定义属性域U, U中的元素为属性映射的整数(mod q).对于任意属性j∈U, 若属性授权机构AA_k拥有其密钥分发权限, 即j∈AA_k, 则AA_k选择秘密随机数${t_j} \in Z_q^*$, 计算${T_j} = {g^{{t_j}}}$.最后输出属性公钥$PK = {\langle {\{ {T_j}\} _{j \in A{A_k}}}\rangle _{k \in \{ 1, 2, ..., n\} }}$、属性私钥$MK = {\langle {\{ {t_j}\} _{j \in A{A_k}}}\rangle _{k \in \{ 1, 2, ..., n\} }}$.

3.2 密钥生成KeyGen(λ_i, ω, MK)

具有属性集ω的用户ID_i向属性授权机构AA_k发送λ_i并申请对应私钥, AA_k针对任意属性j∈ω∩AA_k, 计算:

${S_{i, j}} = {g^{\frac{{\alpha {\lambda _i}}}{{{t_j}}}}}{h^{\frac{\alpha }{{{t_j}}}}}, {W_i} = {g^{\alpha {\lambda _i}}}.$

用户ID_i收到S_{i, j}, W_i后, 计算$W_i^* = {W_i} \cdot {g^{ - \beta }} = {g^{\alpha {\lambda _i} - \beta }}$.最终用户ID_i的私钥为$S{K_{I{D_i}, \omega }} = \langle {\lambda _i}, W_i^*, {S_{i, 1}}, ..., {S_{i, |\omega |}}\rangle .$

在此过程中, 由于各属性授权机构AA_k无法得到秘密参数β, 而系统中心SA无法获取属性私钥t_j的信息, 因此可以确保不可信的属性授权机构和系统中心均无法解密用户密文.

3.3 属性撤销Revocation(MK, ID_k, λ_k, attr(j))

各属性授权中心AA_k公开维护一个用户属性撤销列表R_k.

当用户ID_rev的属性attr(j)被撤销时, 将λ_rev加入属性attr(j)的撤销列表List_attr(j)中并计算$\{ {L_{attr(j), rev}} = $ ${g^{\alpha {\lambda _{rev}}}}{v^{\beta {t_j}}}{h^\alpha }\} $, 最终将属性attr(j)的相关撤销信息$(attr(j), {\{ {\lambda _{rev}}, {L_{attr(j), rev}}\} _{rev \in Lis{t_{attr(j)}}}})$加入R_k.

●  若属性无相关撤销用户, 则计算${L_{attr(j)}} = {v^{\beta {t_j}}}{h^\alpha }$, 将二元组加入R_k;

●  若用户ID_rev被撤销, 则计算该用户所有属性的L_{attr(j), rev}, 并添加至R_k.

3.4 加密Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M, R, PK)

获取所有属性授权机构AA_k最新的属性撤销列表${R_k} = \{ (j, {\{ {\lambda _{rev}}, {L_{j, rev}}\} _{rev \in Lis{t_j}}})\} $.加密方选择随机数$s, r \in Z_q^*$, 计算C₀=M·Z^sr, C^*=g^sr.

加密方选择访问树策略${\mathit{\Gamma} _{{\omega ^*}}}$, 如下所示, 从根节点root开始由上至下为每个内部节点选取n_x-1阶多项式q_x.

●  根节点root:q_root(0)=s, 其余n_root-1个系数随机选取;

●  内部节点x:q_x(0)=q_parent(index(x));

●  叶子节点leaf_j:${q_{lea{f_j}}}(0) = {q_x}(index(lea{f_j}))$;

●  对于任意属性j∈ω^*, List_j=∅, 计算${C_{1, j}} = T_j^{{q_{lea{f_j}}}(0) \cdot r}, {C_{2, j}} = L_j^{{q_{leaf}}_j(0) \cdot r}$;

●  对于任意属性j∈ω^*, List_j≠∅, 遍历j的撤销列表List_j, 选择|List_j|个随机数${u_1}, ..., {u_{_{|Lis{t_j}|}}}$, 满足${u_1} + ... + {u_{|Lis{t_j}|}} = $ ${q_{lea{f_j}}}(0)$, 计算${\{ {C_{1, j, rev}} = T_j^{{u_{rev}} \cdot r}, \;{C_{2, j, rev}} = L_{j, rev}^{{u_{rev}} \cdot r}\} _{j \in {\omega ^*}, rev \in Lis{t_j}}}$;

●  最后输出密文$CT = \langle {C_0}, {C^*}, {\{ C{}_{1, j}, {C_{2, j}}\} _{j \in {\omega ^*}, Lis{t_j} = \emptyset }}, {\{ {C_{1, j, rev}}, {C_{2, j, rev}}\} _{j \in {\omega ^*}, rev \in Lis{t_j}}}\rangle $.

3.5 重加密ReEncrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M, R, PK)

已知密文$CT = \langle {C_0}, {C^*}, {\{ C{}_{1, j}, {C_{2, j}}\} _{j \in {\omega ^*}, Lis{t_j} = \emptyset }}, {\{ {C_{1, j, rev}}, {C_{2, j, rev}}\} _{j \in {\omega ^*}, rev \in Lis{t_j}}}\rangle $, 当访问结构涉及的属性发生撤销事件时, 用户需对密文进行重加密.

●  若撤销前, 属性j∈ω^*, List_j=∅, 则选择随机数$u_{rev}^*$, 计算重加密密文:${C_{1, j, rev}} = {C_{1, j}} \cdot T_j^{ - u_{rev}^* \cdot r}, {C_{2, j, rev}} = {C_{2, j}} \cdot $ $L_j^{ - u_{rev}^* \cdot r} = L_j^{({q_{lea{f_j}}}(0) - u_{rev}^*) \cdot r}, {C_{1, j, rev^*}} = T_j^{u_{rev}^* \cdot r}, {C_{2, j, rev^*}} = L_j^{u_{rev}^* \cdot r}$, 替换原有密文即可;

●  若撤销前, 属性j∈ω^*, List_j≠∅, 则选择随机数$u_{rev}^*$, 计算重加密密文${C_{1, j, rev}} = {C_{1, j, rev}} \cdot T_j^{ - u_{rev}^* \cdot r} = T_j^{({u_{rev}} - u_{rev}^*) \cdot r}$, ${C_{2, j, rev}} = {C_{2, j, rev}} \cdot L_j^{ - u_{rev}^* \cdot r} = L_j^{({u_{rev}} - u_{rev}^*) \cdot r}, {C_{1, j, rev^*}} = T_j^{u_{rev}^* \cdot r}, {C_{2, j, rev^*}} = L_j^{u_{rev}^* \cdot r}$, 替换原有密文即可.

3.6 解密Decrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, SK_{ID, ω}, CT, R)

解密算法如下递归进行:对于访问树${\mathit{\Gamma} _{{\omega ^*}}}$中的每个叶子节点leaf_j, 查询属性撤销列表R.

●  若该属性无相关撤销信息, 即j∈ω∩ω^*, List_j=∅, 计算:

$DecryptNode(CT, S{K_{ID, \omega }}, lea{f_j}) = \frac{{e({S_{i, j}} \cdot {v^\beta }, {C_{1, j}})}}{{e(g, {C_{2, j}})}} = e{(g, g)^{\alpha r{\lambda _i} \cdot {q_{lea{f_j}}}(0)}};$

●  若该属性具有撤销信息, 即j∈ω∩ω^*, List_j≠∅, 计算:

$DecryptNode(CT, S{K_{I{D_i}, \omega }}, lea{f_j}) = {\prod\limits_{rev \in Lis{t_j}} {\left( {\frac{{e({S_{i, j}} \cdot {v^\beta }, {C_{1, j, rev}})}}{{e(g, {C_{2, j, rev}})}}} \right)} ^{\frac{{{\lambda _i}}}{{{\lambda _i} - {\lambda _{rev}}}}}} = e{(g, g)^{\alpha r{\lambda _i}{q_{lea{f_j}}}(0)}}.$

对于访问树${\mathit{\Gamma} _{{\omega ^*}}}$的非叶子节点x, 设该节点的子节点为z, 调用DecryptNode(CT, SK_{ID, ω}, z)的计算结果, 记为F_z. 令S_x为任意n_x个F_z≠⊥的子节点z的集合, F(x)计算如下:

$\begin{array}{*{35}{l}} F(x) = \prod\nolimits_{z \in {S_x}} {F{{(z)}^{{\Delta _{i, {S_x}}}(0)}}} \\ \ \ \ \ \ \ \ \ = \prod\nolimits_{z \in {S_x}} {{{(e{{(g, g)}^{\alpha r{\lambda _i} \cdot {q_z}(0)}})}^{{\Delta _{i, {S_x}}}(0)}}} \\ \ \ \ \ \ \ \ \ = \prod\nolimits_{z \in {S_x}} {{{(e{{(g, g)}^{\alpha r{\lambda _i} \cdot {q_{parent(z)}}(index(z))}})}^{{\Delta _{i, {S_x}}}(0)}}} \\ \ \ \ \ \ \ \ \ = \prod\nolimits_{z \in {S_x}} {{{(e{{(g, g)}^{\alpha r{\lambda _i} \cdot {q_x}(i)}})}^{{\Delta _{i, {S_x}}}(0)}}} \\ \ \ \ \ \ \ \ \ = e{(g, g)^{\alpha r{\lambda _i}{q_x}(0)}}. \\ \end{array} $

当且仅当用户ID所拥有的属性集ω满足${\mathit{\Gamma} _{{\omega ^*}}}$, 用户才能递归计算出$F(root) = e{(g, g)^{\alpha {\lambda _i}rs}}$.

最后, 通过如下计算恢复明文M:

$M = \frac{{{C_0} \cdot e({C^*}, W_i^*)}}{{F(root)}}.$

4 方案分析 4.1 正确性分析

用户能够成功解密的条件是用户的属性集ω满足访问树结构${\mathit{\Gamma} _{{\omega ^*}}}$, 且用户用于解密的属性不在撤销名单中.利用拉格朗日插值定理, 可以递归地恢复出s, 进而解密出明文, 具体推导过程如下:

$M = \frac{{{C_0} \cdot e({C^*}, W_i^*)}}{{F(root)}} = \frac{{M \cdot {Z^{sr}} \cdot e({g^{sr}}, {g^{\alpha {\lambda _i} - \beta }})}}{{e{{(g, g)}^{\alpha {\lambda _i}rs}}}} = \frac{{M \cdot e{{(g, g)}^\beta }^{sr} \cdot e({g^{sr}}, {g^{\alpha {\lambda _i} - \beta }})}}{{e{{(g, g)}^{\alpha {\lambda _i}rs}}}} = M.$

4.2 安全性分析

定理1.在随机预言机模型及q-BDHE问题假设下, 本文提出的基于属性的加密方案在适应性选择密文攻击下是密文不可区分的.

证明:假设存在敌手A以不可忽略的优势ε攻破上述方案的密文不可区分性, 则可以构造一个有效的算法C, 以不可忽略的优势解决q-BDHE问题.记攻击者A访问私钥解析预言机、密文解析预言机的次数分别为q_k, q_D.

假定给算法C一个q-BDHE问题的实例:给定$Y = (g, {g^s}, {g^a}, {g^{({a^2})}}, ..., {g^{({a^q})}}, {g^{({a^{q + 2}})}}, ..., {g^{({a^{2q}})}})$与随机数V∈_RG₂, C的目标是调用A为子程序, 区分出随机数V与$e{(g, g)^{{a^{q + 1}}s}}$.C仿真如下.

(1) 初始化:挑战者C随机选择元素s, a, 计算$Y' = (g, {g^s}, {g^a}, {g^{({a^2})}}, ..., {g^{({a^n})}}, {g^{({a^{n + 2}})}}, ..., {g^{({a^{2n}})}})$.然后, 挑战者C运行Setup(1^λ)算法, 抛掷一枚公平的二元随机硬币μ∈{0, 1}:若μ=0, 令β=aⁿ⁺¹, 计算$Z = e{(g, g)^{{a^{n + 1}}}}$, 其中, n表示属性个数; 否则, 随机选择元素V∈G₂.挑战者将Y=(Y', V)发送给A.令t_j=a^j, j∈[1, n), 产生公钥PK=⟨g, v^β, e, Z, q, {T_j}_j∈U⟩与系统主密钥MK, 将公钥发送给敌手A, 敌手A输出挑战身份$\bar \lambda $、挑战访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销列表R;

(2) 阶段1:敌手A进行多项式界次数的预言机询问.

a) 私钥解析询问:C维护一个含有数组$({\omega _i}, {\lambda _i}, {W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$的列表key^list.当A选择用户ID_i及其属性集ω_i, 向C询问对应用户的私钥时, C检查列表key^list中是否有对应的询问结果:如果有, 则返回对应值$({W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$; 否则, C操作如下.

  若${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) \ne 1$, 对于属性j∈ω_i, 令α=a, 计算${S_{i, j}} = {g^{\frac{{a{\lambda _i}}}{{{t_j}}}}}{h^{\frac{a}{{{t_j}}}}} = {g^{\frac{{{\lambda _i}}}{{{a^{j - 1}}}}}}, {W_i} = {g^{a{\lambda _i} - {a^{n + 1}}}}$.C返回结果给A, 并记录$({\omega _i}, {\lambda _i}, {W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$到列表key^list;

  否则, ${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$, 当λ_i∈R时, 预言仿真过程同上;

  否则, ${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$且λ_i∉R, C停止并输出“FAILURE”(该事件用E₁表示);

b) 密文解析询问:C维护一个含有数组$({\omega _i}, {\lambda _i}, {\mathit{\Gamma} _{{\omega ^*}}}, {M_k}, C{T_k})$的列表Dec^list.当A在访问结构${\mathit{\Gamma} _{{\omega ^*}}}$下发送一个挑战用户λ_i、一个属性集合ω_i与密文CT_k给挑战者C进行密文解析询问时, C检查列表Dec^list中是否有对应的询问结果:如果有, 则返回对应明文M_k; 否则, C操作如下.

  若${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$, λ_i∉R且CT_k≠CT^*, C运行Decrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, SK_{ID, ω}, CT, R)算法, 解密出明文M_k, 返回给A, 并记录相应信息到列表Dec^list;

  否则, C停止并输出“FAILURE”(该事件用E₂表示);

(3) 挑战:敌手A挑战方案的不可区分性:A分别选择两条长度相等的明文M₀, M₁.挑战者C随机选取b∈{0, 1}, 运行Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M_b, R, PK)算法, 生成消息M_b在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下的密文CT^*, 并返回结果给A; 若μ=0, 则令r=1, ${C_0} = {M_b} \cdot {Z^{sr}} = {M_b} \cdot e{(g, g)^{{a^{n + 1}}s}}, $C^*=g^sr=g^s; 若μ=1, 则令C₀=V^sr, C^*=g^sr;

(4) 阶段2:如阶段1所示, A继续执行多项式界次数的私钥解析和密文解析询问;

(5) 猜测:敌手A输出对b的猜测b'.

若b=b', C输出对μ的猜测μ'=0;否则, 输出对μ的猜测μ'=1.所以, C成功输出$\mu \mathop = \limits^? \mu '$作为对q-BDHE问题的一个实例的解答.

分析C在这个游戏中的优势:

ⅰ)预言机的回答是有效的, 除非事件E₁, E₂发生;

ⅱ)如果A能够区分密文与密文间的不同, 则C能解决q-BDHE问题的一个实例.

总而言之, 如果事件E₁, E₂都没有发生, 则A能攻破所提方案的不可区分性.现在计算C能解决q-BDHE问题的优势:当μ=0时, ${C_0} = {M_b} \cdot {Z^{sr}} = {M_b} \cdot e{(g, g)^{{a^{n + 1}}s}}$是一条合法密文, 攻击者可以发挥全部攻击优势ε=Pr[b=b']-1/2, 则μ=0时, C获胜的概率为Pr[b=b'|μ=0]=Pr[b=b']=ε+1/2;当μ=1时, C₀=M_bV^sr相当于G₂上随机选取的元素, 不包含明文M_b的任何信息, 因此攻击者失去攻击优势, 则μ=1时, C获胜的概率为Pr[b=b'|μ=1]=Pr[b≠b']=1/2.综上所述, C能解决q-BDHE问题的优势为

$ \text{Pr}[b=b'\left] -1/2=\text{Pr} \right[b=b'|\mu =0\left] \cdot \text{Pr} \right[\mu =0\left] +\text{Pr} \right[b=b'|\mu =1\left]\\ \cdot \text{Pr} \right[\mu =1]-1/2=(\varepsilon +1/2)\cdot 1/2+1/2\cdot 1/2-1/2=\varepsilon /2. $

定理2.在随机预言机模型及DDH问题假设下, 本文提出的基于属性的加密方案能够抵抗不可信授权中心的破译攻击.

证明:假设存在敌手A以不可忽略的优势ε攻破上述方案, 则可以构造一个有效的算法C, 以ε'≈ε/2的优势解决DDH问题.记攻击者A访问私钥解析预言机、密文解析预言机的次数分别为q_k, q_D.

假定给算法C一个DDH问题的实例:输入g^x, g^y, g^z∈G₁, 挑战者C的目标是以A作为子程序, 判断z=xy mod q是否成立.C仿真过程如下所示.

(1) 初始化:挑战者C运行Setup(1^λ)算法, 产生公钥PK=⟨g, v^β, e, Z, q, {T_j}_j∈U⟩与系统主密钥MK.C抛掷一枚公平的二元随机硬币μ∈{0, 1}:若μ=0, 令z=β, 计算Z=e(g, g)^z; 否则, 随机选择x, y∈Z_q, 计算Z=e(g, g)^xy.若敌手A为恶意系统中心SA, C将PK和秘密参数⟨α, β, λ_i⟩发送给A, MK保密; 若敌手A为恶意属性授权机构AA_k, C将PK, MK和秘密参数α发送给A, 秘密参数⟨β, λ_i⟩保密.敌手A输出挑战访问策略${\mathit{\Gamma} _{{\omega ^*}}}$和属性撤销列表R;

(2) 阶段1:敌手A进行多项式界次数的预言机询问.

a) 私钥解析询问:C维护一个含有数组$({\omega _i}, {\lambda _i}, {W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$的列表key^list.当A选择用户ID_i及其属性集ω_i、向C询问对应用户的私钥时, C检查列表key^list中是否有对应的询问结果:如果有, 则返回对应值$({W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$; 否则, C操作如下.

  若${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) \ne 1$, 对于属性j∈ω_i, 令α=a, 计算${S_{i, j}} = {g^{\frac{{a{\lambda _i}}}{{{t_j}}}}}{h^{\frac{a}{{{t_j}}}}} = {g^{\frac{{{\lambda _i}}}{{{a^{j - 1}}}}}}, {W_i} = {g^{a{\lambda _i} - {a^{n + 1}}}}$.C返回结果给A, 并记录$({\omega _i}, {\lambda _i}, {W_i}, {\{ {S_{i, j}}\} _{j \in {\omega _i}}})$到列表key^list;

  否则, ${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$, 当λ_i∈R时, 预言仿真过程同上;

  否则, ${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$且λ_i∉R, C停止并输出“FAILURE”(该事件用E₁表示);

b) 密文解析询问:C维护一个含有数组$({\omega _i}, {\lambda _i}, {\mathit{\Gamma} _{{\omega ^*}}}, {M_k}, C{T_k})$的列表Dec^list.当A在访问结构${\mathit{\Gamma} _{{\omega ^*}}}$下发送一个挑战用户λ_i、一个属性集合ω_i与密文CT_k给挑战者C进行密文解析询问时, C检查列表Dec^list中是否有对应的询问结果:如果有, 则返回对应明文M_k; 否则, C操作如下.

  若${\mathit{\Gamma} _{{\omega ^*}}}({\omega _i}) = 1$, λ_i∉R且CT_k≠CT^*, C运行Decrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, SK_{ID, ω}, CT, R)算法, 解密出明文M_k, 返回给A, 并记录相应信息到列表Dec^list;

  否则, C停止并输出“FAILURE”(该事件用E₂表示);

(3) 挑战:A分别选择两条长度相等的明文M₀, M₁.挑战者C随机选取b∈{0, 1}, 运行Encrypt(${\mathit{\Gamma} _{{\omega ^*}}}$, M_b, R, PK)算法, 生成消息M_b在访问策略${\mathit{\Gamma} _{{\omega ^*}}}$下的密文CT^*, 将CT^*发送给A;

(4) 阶段2:如阶段1, 攻击者进行多项式次预言机询问;

(5) 猜测:攻击者A输出对b的猜测b', 若b=b'则A赢得游戏, 则C成功输出μ=μ'作为对DDH问题的一个实例的解答, 即该方案无法抵抗不可信授权中心的破译攻击.

分析C在这个游戏中的优势.

ⅰ)只要事件E₁, E₂不发生, 则预言机返回的的结果是正确的;

ⅱ)若A赢得游戏, 则C能够解决给定DDH问题的实例.

总而言之, 如果事件E₁, E₂都没有发生, 则A能攻破所提方案的不可区分性.现在计算C能解决DDH问题的优势:当μ=0时, C₀=M_b·Z^sr=M_b·e(g, g)^zsr是一条合法密文, 攻击者可以发挥全部攻击优势ε=Pr[b=b']-1/2, 则μ=0时, C获胜的概率为Pr[b=b'|μ=0]=Pr[b=b']=ε+1/2;当μ=1时, C₀=M_b·e(g, g)^xysr相当于G₂上随机选取的元素, 因此攻击者失去攻击优势, 则μ=1时, C获胜的概率为Pr[b=b'|μ=1]=Pr[b≠b']=1/2.综上所述, C能解决DDH问题的优势为

$ \text{Pr}[b=b'\left] -1/2=\text{Pr} \right[b=b'|\mu =0\left] \times \text{Pr} \right[\mu =0\left] +\text{Pr} \right[b=b'|\mu =1\left]\\ \times \text{Pr} \right[\mu =1]-1/2=(\varepsilon +1/2)\times 1/2+1/2\times 1/2-1/2=\varepsilon /2. $

若所提方案无法抵抗不可信授权中心的破译攻击, 则该方案是适应性选择密文攻击下的不可展性不安全的.因为若敌手以一种可控的方式, 通过修改密文来修改相应的明文, 则它可以对挑战密文进行修改, 然后通过预言机的帮助获取修改后密文对应的明文, 最后, 利用明文间的相互关系输出挑战密文对应的明文.由于公钥密码体制适应性选择密文攻击下的不可区分性等价于适应性选择密文攻击下的不可展性, 因此敌手无法在多项式时间内解密挑战密文, 所以本文所提的基于属性的加密方案能够抵抗不可信授权中心的破译攻击.

4.3 性能分析

本节就密钥长度、密文长度、加密阶段和解密阶段的计算代价、撤销机制、访问策略、重加密功能、能否解决授权中心不可信问题等方面与文献[10, 13, 16-18, 21-24]中的方案进行对比, 以评估本方案的性能.比较结果见表 1.

表 1中, T_bp表示一次双线性对运算所需的时间复杂度, T_exp表示一次G₁群上的模幂运算所需的时间复杂度, |A|表示所有属性的数量, |B|表示访问策略中声明的属性的数量, |C|表示用户拥有属性的数量, |D|表示用户解密使用的属性的数量, r表示撤销事件的数量.

从表 1可以看出:在已有的结果中, 本方案的密钥长度仅次于文献[24]中的方案.文献[13, 23]需要给每个用户颁发所有属性相应的密钥, 因此密钥长度较长; 而文献[10, 16-18, 21, 22]中的方案与本方案类似, 只需要给每个用户颁发自身属性相应的密钥, 减少了密钥长度.同时, 为了确保能够抵抗合谋攻击, 本方案引进了一个私有变量, 因此比文献[24]中的方案增加了1|G₁|bit.

为了实现对用户属性的细粒度撤销, 本方案采用在密文中直接嵌入撤销信息的方法, 需要产生与属性撤销名单一一对应的密文, 因此在密文长度上本方案并不具备优势, 为(2|B|+2)|G₁|bit.虽然文献[23, 24]中的方案的密文长度较小且具有恒定大小, 为5|G₁|, 但这两个方案只支持AND结构的访问策略, 不够灵活, 并且大部分计算任务需要由属性授权中心执行, 在用户与属性数目较大时, 易造成性能瓶颈.文献[13, 21]中的方案的密文长度比本文方案略短, 但文献[13]中的方案采用了间接撤销模式, 而文献[21]中的方案则通过与半可信第三方的交互来实现属性的直接撤销, 通信代价较大.文献[10, 16, 18]中的方案的密文长度与本方案相近, 但这3个方案只支持用户撤销, 不支持属性撤销, 撤销粒度粗.文献[17, 22]中的方案为了抵抗合谋攻击, 需要对密文进行随机化处理, 因此这两个方案密文长度较大, 分别为(4|B|+1)|G₁|bit和(3|B|+2r+2)|G₁|bit.总体而言, 在保证良好的系统安全性、灵活性以及更细的属性撤销粒度前提下, 本文方案具有较短的密文长度.

综合加密与解密的计算量, 文献[24]中的方案的计算代价最少, 为5T_exp+(5+r)T_bp, 但该方案将大量的计算任务交由属性授权中心执行, 其安全性高度依赖于属性授权中心的可靠性, 且该方案的解密计算量与属性撤销频率呈线性关系, 不适用于属性变化频繁的云计算环境中.相比于其他方案, 本方案在计算代价上具有较大优势, 仅比文献[21]中的方案增加了(|B|+1)T_exp.而文献[21]中的方案使用了两部分密钥, 且解密时需要跟属性授权中心进行认证, 增加了通信代价.方案[13]采用属性的间接撤销, 需要在属性变化时颁发新的密钥, 并且计算代价与所有属性的集合大小相关, 当属性集合过大时, 解密方可能无法负荷相应的计算量.而文献[10, 16-18, 22, 23]中的方案都存在计算代价大且与属性撤销频率呈线性关系的问题.本文方案不仅实现了细粒度属性的直接撤销, 并且采用了访问树结构, 能够保证密文的灵活使用, 在计算效率上也进行了优化, 更加实用.

从功能性进行分析, 主要集中于细粒度属性直接撤销, 而重加密是实现上述功能的重要方法, 即:当用户属性撤销事件发生时, 对已经生成并发布的密文重新进行加密, 以避免属性被撤销用户解密该密文.文献[10, 17, 21, 22]并不支持重加密, 文献[13, 16, 18, 23, 24]中的方案虽然具备重加密功能, 但是存在撤销粒度粗(如文献[16, 18]中的方案), 或访问策略表达能力弱(如文献[13, 23, 24]中的方案)的缺点.本文方案在树状访问结构基础上, 通过引入属性撤销列表, 给出了高效的重加密算法, 从而实现了细粒度的属性直接撤销功能.在安全性方面, 本文方案能够防止不可信授权中心的侵权行为, 而绝大多数方案都不具备该特性, 因此, 本文方案在安全性上得以加强.

综上所述, 本文方案采用树状访问结构实现了用户属性的细粒度直接撤销, 在保证安全性的前提下, 具有更高的撤销效率; 同时, 所提方案能够抵抗不可信授权中心的破译攻击, 更加适用于用户属性变化频繁的云计算环境中.

5 结论

本文提出一种支持细粒度属性直接撤销的CP-ABE方案, 该方案采用树结构的访问策略, 有效解决了现有方案撤销代价与安全性难以兼顾的问题.性能分析表明, 新方案在密钥长度与计算量上具有一定优势, 并且能够防止不可信授权中心解密用户隐私数据的行为, 可以有效避免云计算环境中因数据共享带来的安全隐患.