为了对人群进行细粒度划分, Sahai等人^[1]将身份的概念泛化, 于2005年提出了属性的概念.在其方案中, 用户身份被描述为一系列属性的集合, 每个属性对应唯一的密钥, 只要用户属性满足解密策略, 他就可以通过解密获得相应的信息, 从而实现多对多的加解密过程.目前, 基于属性的加密方案(attribute-based encryption, 简称ABE)可以分为两类:一类是密钥策略的属性基加密方案(key-policy attribute-based encryption, 简称KP-ABE)^[2−4], 即将解密策略与用户密钥绑定; 另一类是密文策略的属性基加密方案(ciphertext-policy attribute-based encryption, 简称CP-ABE)^[5−7], 即将解密策略与密文绑定.

属性的概念同样可以应用于数字签名, 形成基于属性的签名体制(attribute-based signature, 简称ABS).在该体制中, 属性授权机构(attribute of authority, 简称AA)负责用户属性密钥的分发和管理, 只有满足签名策略的用户才能对相应的消息进行签名, 任何人均可利用公开参数验证签名的合法性.由于基于属性的签名体制具有表达能力强、使用灵活、便于隐匿签名者身份等优点, 因此逐渐成为相关领域的研究热点.2005年, Burnett等人^[8]提出了基于模糊身份的签名方案, 该方案被认为是首个广义ABS方案.随后, Guo等人^[9]和Maji等人^[10]于2008年分别提出了真正意义的ABS方案.文献[9]的方案采用自底向上(bottom-up)构造访问控制树的方式, 允许签名者使用自身拥有的属性进行签名.然而该方案并未对签名者的隐私进行保护, 且缺乏完整的形式化定义和安全性证明.文献[10]中的方案虽然具备签名者隐私保护功能且支持任意访问结构, 但其安全性只能在一般群模型(generic group model)下得到证明.随后, 为了更好地保护签名者的隐私, 环签名^[11]的思想被引入到属性基签名体制中, 形成了基于属性的环签名方案(attribute-based ring signature, 简称ABRS).由于环签名具备无条件匿名性、自发性和群特性等优点, 因此ABRS方案在签名过程中没有组织过程, 无需群管理员参与, 可以很好地保护签名者的隐私.首个基于属性的环签名方案由Li等人^[12]于2008年提出, 但该方案只能实现(n, n)门限签名(其中, n为签名策略声明属性集合中元素的个数), 并且在签名过程中, 针对每个属性需要计算3个子签名, 验证过程需要进行3n次双线性对运算, 因此效率很低, 实用性较差.随后, 一系列改进ABRS方案^[13−21]相继被提出.

由于基于属性的环签名方案通常被应用于对匿名性要求较高的环境, 因此, 匿名性的强弱是评判一个ABRS方案优劣的重要依据.匿名性通常可以分为两类:计算匿名性(computational anonymity)和无条件匿名性(unconditional anonymity).针对ABRS方案, Shahandashti等人^[14]为了更好地区分方案匿名性强弱, 又将无条件匿名性细分为无条件弱匿名性(unconditional weak anonymity)和无条件强匿名性(unconditional strong anonymity), 匿名性分类及定义如下.

(1) 计算匿名性:将方案的匿名性规约为求解某一数学难题(如离散对数问题、大整数分解问题、Diffi-Hellman问题等)的困难性.如果存在某一敌手能够在多项式时间内有效求解这一困难问题, 则该方案的匿名性将会被攻破.

(2) 无条件弱匿名性:指即便存在某一敌手(包括属性授权机构)计算能力不受限, 也无法在多项式时间内从拥有”签名属性集合”的群体成员中揭露签名者的真实身份.

(3) 无条件强匿名性:除满足无条件弱匿名性之外, 任何敌手(包括属性授权机构)甚至无法在多项式时间内从“声明属性集合”中揭露“签名属性集合”的信息.

目前, 仅有部分ABRS方案^{[14, 17, 19, 21]}可以实现无条件强匿名性, 大多数方案由于在签名验证阶段需要使用实际签名属性集合, 因此只能实现无条件弱匿名性, 而文献[20]中的方案仅能实现计算匿名性.

除匿名性之外, 抗合谋攻击性对于衡量ABRS方案的优劣同样重要.合谋攻击是指拥有互补属性集合的恶意用户相互勾结, 通过组合密钥的方式, 伪造他们各自无法单独产生的签名.目前, 仅有少数ABRS方案^{[20, 21]}可以抵抗这种攻击.文献[20]中的方案通过将用户身份信息直接嵌入属性密钥的方式, 虽然能够确保签名不能由多个用户合谋产生, 但是由于引入了身份信息, 导致方案匿名性退化, 只能实现计算匿名性.

此外, 现有的ABRS方案大多只包含一个属性授权机构(AA), 该AA负责系统中所有属性密钥的分发和管理, 一旦AA被敌手控制, 整个系统就会被攻破.利用分布式的方式, 将属性密钥分发和管理权限交由不同的AA分别管理, 可以克服上述安全瓶颈.2007年, Chase^[22]首先将这一思想应用于属性基加密体制.随后, Maji等人^[10]于2008年提出了分布式属性基签名的概念, 但其并未给出具体的实现方案.首个多属性授权机构的ABRS方案由Li等人^[17]于2010年提出, 该方案包含一个系统中心(central authority)、多个AA和终端用户这3种类型的实体.其中, 系统中心负责生成并分发各AA的私钥, 而各AA则负责用户不同属性密钥的分发和管理.该方案虽然通过分布式的方式分散了AA的权限, 但仍然要求系统中心绝对可信, 因此并未完全克服属性密钥托管这一缺陷.随后, Li等人^[21]借鉴Chase等人^[23]提出的密钥匿名分发协议对文献[17]中的方案进行完善, 提出一个改进的ABRS方案, 但是密钥匿名分发协议的引入, 导致该方案在密钥分发阶段, AA除了需要为用户生成属性密钥之外, 还需额外产生t²个密钥来克服属性密钥托管问题, 其中, t为属性授权机构集合中AA的数量.这无疑在降低AA工作效率的同时增加了AA与用户之间的通信代价.此外, 该方案签名门限固定, 且只能在单属性授权机构条件下, 被证明具备匿名性和不可伪造性, 并未给出抗合谋攻击的形式化安全证明.综上可以看出:如何设计形式化可证明安全且同时具备无条件强匿名性和抗合谋攻击性的无可信中心分布式ABRS方案, 是一个亟待解决的问题.

本文针对现有ABRS方案无法同时具备无条件强匿名性和抗合谋性, 并且存在密钥托管、签名门限固定、验证效率低下等问题, 提出一个分布式无中心授权的属性基可变门限环签名方案, 并给出该方案在随机预言机模型及多属性授权机构条件下的形式化定义和安全模型.本方案利用DKG(distributed key generation)协议^{[24, 25]}将可信的系统中心移除, 把属性密钥的分发和管理权限交由不同的AA, 在解决效率瓶颈的同时, 克服了属性密钥托管这一缺陷.在密钥生成过程中, 将属性密钥与用户身份标识绑定, 保证签名只能由满足签名策略的用户独立产生, 在签名过程中, 引入用户身份模糊因子保护签名者的隐私, 确保方案在抵抗合谋攻击的前提下还具备无条件强匿名性.另外, 通过借鉴Ferrara等人^[26]的思想, 提出了一种适用于本方案的批验证算法.该算法能够将验证计算复杂度由nO(·)降为O(·)+n, 其中, n为待验证签名(可以由多个用户在不同的签名策略下产生)的数量, O(·)为验证单个签名的计算复杂度, 有效提高了验证效率.在随机预言机模型(random oracle model, 简称ROM)和CDH(computational Diffie-Hellman)困难问题假设下, 本文方案能够被证明在适应性选择消息和断言攻击下是存在性不可伪造的, 并能抵抗由拥有互补属性集合的恶意用户发动合谋攻击.

本文第1节回顾相关的预备知识.第2节给出分布式属性基门限环签名方案的形式化定义和安全模型.第3节提出一个分布式无中心授权的属性基可变门限环签名方案.第4节从匿名性、不可伪造性和抗合谋攻击这3个方面对所提出的方案进行安全性证明.第5节通过效率比较和性能分析对所提出的方案进行综合评价.最后对全文进行总结.

1 预备知识 1.1 双线性对

定义1. 假设G₁, G₂是阶为素数p的循环群, g是群G₁的生成元, 映射e:G₁×G₁→G₂是一个双线性对, 如果e满足以下性质.

1) 双线性性:对于任意群元素g₁, g₂∈G₁和随机数a, b∈Z_p, 满足$e(g_1^a,g_2^b) = e{({g_1},{g_2})^{ab}};$

2) 非退化性:存在群元素g₁, g₂∈G₁, 满足e(g₁, g₂)≠1, 其中, 1是G₂的单位元;

3) 可计算性:存在有效算法可以在多项式时间内计算e(g₁, g₂)的值.

1.2 CDH困难问题假设

定义2. 假设G₁, G₂是阶为素数p的循环群, g是群G₁的生成元, 对于任意a, b∈Z_p, 给定元组〈g, g^x, g^y〉, 若不存在有效算法能够在多项式时间内以不可忽略的优势计算g^xy, 则假设成立.

1.3 批验证假设

定义3. 给定算法Psetup(1^τ)→(q, g₁, g₂, G₁, G₂, G_T, e), 对于任意j∈[1, n], 其中, q为大素数, τ为安全参数, n∈poly(τ), 任意选取群中固定元素A和Z_q上的随机向量μ=(μ₁, …, μ_n), 若等式$\prod\nolimits_{j = 1}^n {{A^{{\mu _j}}}} = \prod\nolimits_{j = 1}^n {{Y^{(j)}}^{{\mu _j}}} $成立, 则等式A=Y^(j)成立.

1.4 拉格朗日插值定理

定义4. 假设f(x)为x的d−1次多项式函数, 任意给定多项式上d个不同的点(x_i, f(x_i)), 则通过下式可以唯一确定任意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)}. $

通过上式定义拉格朗日系数${\mathit{\Delta} _{i,S}}(x) = \prod\limits_{j \in S,j \ne i} {\frac{{x - {x_j}}}{{{x_i} - {x_j}}}} $, 其中, S为这d个元素的集合.

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

本文使用门限断言${\mathit{\Upsilon} _{t,{\omega ^*}}}( \cdot )$表示签名策略, 其中, ω^*为断言声明属性集合; t为动态签名门限, 满足1≤t≤d, d为AA预设门限值.假设签名者拥有属性集合ω, 若|ω∩ω^*|≥t, 则${\mathit{\Upsilon} _{t,{\omega ^*}}}(\omega ) = 1$, 表示签名者可以产生合法签名; 否则${\mathit{\Upsilon} _{t,{\omega ^*}}}(\omega ) = 0$, 表示签名者无法产生合法签名.

本方案由属性授权机构和用户两种类型的实体构成, 包含初始化、密钥分发、签名、验证这4个阶段, 各阶段具体过程如下:

1) 初始化算法Setup(1^λ):由各属性授权机构AA_k运行的概率性随机算法, 输入安全参数λ, 输出系统公开参数params和系统秘密参数privates.

2) 密钥生成算法KeyGen(ω_ID):由各属性授权机构运行的概率性随机算法, 输入params、privates、用户的身份ID及其属性集合ω_ID, 输出用户相应的属性密钥SK.

3) 签名算法Sign(ϒ, params, m, SK):由签名者运行的概率性随机算法, 输入params、消息m及用户相应的属性密钥SK, 输出签名σ.

4) 验证算法Verify(ϒ, params, m, σ):由验证者运行的确定性算法, 输入params、消息m及签名σ, 若可以判定${\mathit{\Upsilon} _{t,{\omega ^*}}}({\omega _{ID}}) = 1,$则签名σ有效, 输出true; 否则, 输出false.

2.2 安全模型

本节给出分布式属性基门限环签名方案的安全模型.分布式属性基门限环签名方案除了应该满足不可伪造性和匿名性之外, 还应该能够抵抗拥有互补属性集合的恶意成员通过组合密钥的方式发动合谋攻击.其中, 无条件强匿名性是指给定某断言下的合法签名, 任何攻击者(包括各属性授权机构AA_k)即便其计算能力不受限, 且可以获得系统所有用户的任意属性密钥, 也无法在多项式时间内从满足该断言的用户集合中揭露签名者的实际身份.不可伪造性是指任何不满足门限断言的用户均无法在多项式时间内单独伪造该断言下的合法签名.抗合谋攻击是指任何拥有互补属性集合的恶意用户无法通过组合密钥的方式在多项式时间内伪造他们各自无法独立产生的合法签名.

2.2.1 无条件匿名性

定义5. 基于属性的环签名方案具备无条件匿名性, 如果不存在攻击者A(即便其计算能力不受限)能够在多项式时间内以一个不可忽略的优势在以下游戏中获胜.

1) 初始化:A声明挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}}$.挑战者C运行初始化算法, 将生成的系统公开参数params和系统秘密参数privates全部发送给A, 因此, A可以生成系统中所有用户的任意属性密钥.

2) 挑战:A随机选取消息m和用户ID₁(属性集合为ω₁), ID₂(属性集合为ω₂), 满足${\mathit{\Upsilon} _{{t_k},\omega _k^*}}({\omega _1}) = {\mathit{\Upsilon} _{{t_k},\omega _k^*}}({\omega _2}) = 1$, 并将m, (ID₁, ω₁), (ID₂, ω₂)发送给C.C首先运行密钥生成算法生成(ID₁, ω₁), (ID₂, ω₂)对应的密钥集合SK₁, SK₂, 然后抛掷一枚公平硬币b∈{1, 2}, 调用签名算法, 使用SK_b为m生成签名σ_b, 最后, 将σ_b发送给A.

3) 猜测:A输出对b的猜测b', 若b=b', 则A赢得游戏.

2.2.2 不可伪造性

定义6. 基于属性的环签名方案在适应性选择消息和断言攻击下, 是存在性不可伪造的, 如果不存在攻击者A能够在多项式时间内以一个不可忽略的优势在以下游戏中获胜.

1) 初始化:假设攻击者A已经攻破的l−1个属性授权机构组成集合Ψ, 其余未被攻破的属性授权机构组成集合T, A声明挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \mathit{\Psi} \cup \bar l}}$, 其中, $A{A_{\bar l}} \in T$.挑战者C运行初始化算法生成系统公开参数params和系统秘密参数privates, 并将params和集合Ψ中成员的秘密参数发送给A.

2) 询问阶段:A可以适应性地进行多项式次散列询问、密钥解析询问、签名询问.C将相应的仿真结果发送给A.

3) 伪造阶段:游戏最后, A输出消息m^*的签名σ^*.如果满足以下条件, 则A赢得游戏.

➢ $ Verify({\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \mathit{\Psi} \cup \bar l}},params,{m^*},{\sigma ^*}) = {\text{true}}{\text{.}}$

➢ 任何属性集合ω, 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}(\omega ) = 1$, 未进行密钥解析询问.

➢ (ω, m^*)未进行签名询问.

2.2.3 抗合谋攻击性

定义7. 基于属性的环签名方案在适应性选择消息和断言攻击下是抗合谋攻击的, 如果不存在攻击者A能够在多项式时间内以一个不可忽略的优势在以下游戏中获胜.

1) 初始化:同定义6的初始化过程.

2) 询问阶段:同定义6的询问过程.

3) 挑战阶段:A随机选择用户ID₁(属性集合为ω₁), ID₂(属性集合为ω₂), 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega _{1,\bar l}}) \ne 1,{\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega _{2,\bar l}}) \ne 1$, 且存在属性子集${\omega '_{1,\bar l}} \subseteq {\omega _{1,\bar l}},{\omega '_{2,\bar l}} \subseteq {\omega _{2,\bar l}}$, 构成属性集合${\omega '_{\bar l}} = {\omega '_{1,\bar l}} \cup {\omega '_{2,\bar l}}$, 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega '_{\bar l}}) = 1$.分别对(ID₁, ${\omega '_{1,\bar l}}),(I{D_2},{\omega '_{2,\bar l}})$进行密钥解析询问, 获得相应的属性密钥集合$S{K'_{1,\bar l}},S{K'_{2,\bar l}}$, 组成新的属性密钥集合.

$ S{K'_{\bar l}} = S{K'_{1,\bar l}} \cup S{K'_{2,\bar l}}. $

4) 伪造阶段:游戏最后, A输出消息m^*的签名σ^*.如果满足以下条件, 则A赢得游戏.

➢ $ Verify({\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \mathit{\Psi} \cup \bar l}},params,{m^*},{\sigma ^*}) = {\text{true}}{\kern 1pt} .$

➢ 任何属性集合ω, 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}(\omega ) = 1$, 未进行密钥解析询问.

➢ (ω, m^*)未进行签名询问.

3 分布式无中心授权的基于属性可变门限环签名方案

本方案包括初始化、密钥分发、签名、验证这4个阶段, 各阶段具体执行过程如下.

3.1 初始化Setup(d)

随机选取两个阶为大素数q的循环群G₁, G₂, 满足双线性映射e:G₁×G₁→G₂, 生成元g∈G₁.属性集合为ω={ω₁, ω₂, …, ω_l}, ${\omega _k} = \{ {j_{1,k}},{j_{2,k}},...,{j_{|{\omega _k}|,k}}\} $为ω的子集, ${j_{m,k}} \in {}_RZ_q^*$为ω_k中的属性元素, 其中, 1≤k≤l, 1≤m≤|ω_k|; 缺省属性集合为Ω={Ω₁, Ω₂, …, Ω_l}, ${\mathit{\Omega} _k} = \{ {\xi _{1,k}},{\xi _{2,k}},...,{\xi _{|{\mathit{\Omega} _k}|,k}}\} $为Ω的子集, ${\xi _{n,k}} \in {}_RZ_q^*$为Ω_k中的缺省属性元素, 其中, |Ω|= d−1, |Ω_k|=d_k−1, 1≤n≤|Ω_k|.散列函数${H_1}:{\{ 0,1\} ^*} \to Z_q^*,{H_2},{H_3}:{\{ 0,1\} ^*} \to {G_1}.$

本方案共包含n个属性授权机构AA_k, 1≤k≤n, 所有AA_k预共享一个伪随机函数PRF, 并拥有对任一属性子集ω_k和缺省属性子集Ω_k的密钥分发和管理权限.初始化阶段, 所有AA_k首先执行(n, l)门限的DKG协议, 生成系统主密钥a₀和b₀(执行过程中, 每个AA_k随机选取l−1次多项式f_k(x)), 计算${g_1} = {g^{{a_0}}},{g_2} = {g^{{b_0}}}$, Z=e(g₁, g₂), 各AA_k分别拥有系统主密钥a₀的部分秘密信息${a_{k,0}} = \sum\limits_{i = 1}^n {{f_i}(k)} $.然后, 随机选取秘密参数${x_k} \in Z_q^*$, 公布${P_k} = g_1^{{x_k}}$作为自己的公钥.最后, 随机选取${t_{j,k}} \in Z_q^*$, 计算属性j∈ω_k∪Ω_k的公钥${T_{j,k}} = {g^{{t_{j,k}}}}$.

● 公开参数:$params = \langle e,g,{g_1},{g_2},Z,{H_1},{H_2},{H_3},{\{ {P_k}\} _{k = 1,...,n}},{\{ {T_{j,k}}\} _{j \in {\omega _k} \cup {\mathit{\Omega} _k},k = 1,...,n}},q\rangle .$

● 秘密参数:$privates = \langle {\{ {t_{j,k}}\} _{j \in {\omega _k} \cup {\mathit{\Omega} _k},k = 1,...,n}},{\{ {a_{k,0}},{x_k}\} _{k = 1,...,n}}\rangle .$

3.2 密钥分发$KeyGen({\omega _{I{D_i}}})$

每个AA_k随机选择一个d_k−1次多项式q_k(·)(严格保密), 满足q_k(0)=a_{k, 0}.任意l个管理不同属性子集的AA_k即可组成集合Team, 负责系统中所有用户任意属性密钥的分发和管理, 从而可以避免因不可抗力因素导致部分AA_k无法正常工作, 使得整个系统崩溃的情况发生.当用户ID_i(拥有属性集合${\omega _{I{D_i}}} = {\{ {\omega _{I{D_i},k}}\} _{k \in Team}}$)向Team中各成员发出密钥分发请求时, Team中的各AA_k首先为其计算对应的身份标识${\{ {\lambda _{i,k}} = PR{F_{{x_k}}}(I{D_i})\} _{k \in Team}}$, 然后计算属性$j \in {\{ {\omega _{I{D_i},k}} \cup {\mathit{\Omega} _k}\} _{k \in Team}}$对应的密钥:

$ {\{ {S_{1,j,k}} = {H_2}{(j)^{{t_{j,k}}}}g_2^{{H_1}({\lambda _{i,k}}){q_k}(j)}\} _{j \in {\omega _{I{D_i},k}} \cup {\mathit{\Omega} _k},k \in Team}},{\{ {S_{2,k}} = g_1^{ - {x_k}}g_2^{{H_1}({\lambda _{i,k}}){a_{k,0}} + {a_{k,0}}}\} _{k \in Team}}. $

最后, 用户ID_i得到属性密钥集合$SK = \langle {\{ {S_{1,j,k}}\} _{j \in {\omega _{I{D_i},k}} \cup {\mathit{\Omega} _k},k \in Team}}{\{ {S_{2,k}}\} _{k \in Team}}\rangle .$

3.3 签名$Sign({\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}},params,m,SK)$

用户ID_i根据声明断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}}$对消息m进行签名, 首先选择签名属性集合${\{ {\omega '_{I{D_i},k}}\} _{k \in Team}}$, 其中, ${\omega '_{I{D_i},k}} \subseteq {\omega _{I{D_i},k}} \cap \omega _k^*$且$|{\omega '_{I{D_i},k}}| = {t_k}$; 然后, 从各缺省属性集合Ω_k中随机选择d_k−t_k个缺省属性构成集合${\{ {\mathit{\Omega} _{I{D_i},k}}\} _{k \in Team}}$; 其次, 选取$Z_q^*$上的随机数v, z(用户身份模糊因子)及随机数集合${\{ {r_{j,k}}\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}},k \in Team}}$, 计算m相应的签名:

$ \begin{gathered} {\sigma _1} = g_2^z{H_3}{(m)^v}\prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}} {{S_{1,j,k}}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}(0) \cdot {\mathit{\Delta} _{k,Team}}(0)}\prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}}} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} , \\ {\sigma _2} = g_2^z\prod\limits_{k \in Team} {{{({P_k}{S_{2,k}})}^{{\mathit{\Delta} _{k,Team}}(0)}}} , \\ {\sigma _3} = {g^v}. \\ \end{gathered} $

● 对于任意属性$j \in {\{ {\omega '_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}\} _{k \in Team}}$, 计算${\sigma _{4,j,k}} = {T_{j,k}}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}{\text{(0)}} \cdot {\mathit{\Delta} _{k,Team}}(0)}{g^{{r_{j,k}}}}.$

● 对于任意属性$j \in {\{ \omega _k^*\backslash {\omega '_{I{D_i},k}}\} _{k \in Team}}$, 计算${\sigma _{4,j,k}} = {g^{{r_{k,j}}}}.$

最后, 将消息m、签名$\sigma = \langle {\sigma _1},{\sigma _2},{\sigma _3},{\{ {\sigma _{4,j,k}}\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}},k \in Team}}\rangle $和集合${\{ {\mathit{\Omega} _{I{D_i},k}}\} _{k \in Team}}$公开.

3.4 验证$Verify({\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}},params,m,\sigma )$

验证者通过以下步骤判定签名$\sigma = \langle {\sigma _1},{\sigma _2},{\sigma _3},{\{ {\sigma _{4,j,k}}\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}},k \in Team}}\rangle $是否为消息m的合法签名.

1) 判断不等式${\{ {d_k} - |{\mathit{\Omega} _{I{D_i},k}}| \geqslant {t_k}\} _{k \in Team}}$是否成立(验证签名是否满足声明断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}}$).

2) 若不等式成立, 判断等式$\frac{{e(g,{\sigma _2})e({H_3}(m),{\sigma _3})\prod\limits_{k \in Team} {\prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}}} {e({H_2}(j),{\sigma _{4,j,k}})} } }}{{e(g,{\sigma _1})}} = Z$是否成立:若等式成立, 则

接受σ作为m的合法签名; 否则拒绝.

3.5 正确性分析

方案正确性验证如下:

$ \begin{array}{1} \frac{{e(g,{\sigma _2})e\left( {{H_3}(m),{\sigma _3}} \right)\prod\limits_{k \in Team} {\prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}}} {e\left( {{H_2}(j),{\sigma _{4,j,k}}} \right)} } }}{{e(g,{\sigma _1})}} = \hfill \\ \frac{{e\left( {g,g_2^z\prod\limits_{k \in Team} {{{({P_k}{S_{2,k}})}^{{\mathit{\Delta} _{k,Team}}(0)}}} } \right)e\left( {{H_3}(m),{g^v}} \right)\prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}} {e\left( {{H_2}(j),{T_{j,k}}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}{\text{(0)}} \cdot {\mathit{\Delta} _{k,Team}}(0)}} \right)\prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}}} {e\left( {{H_2}(j),{g^{{r_{j,k}}}}} \right)} } } \right)} }}{{e\left( {g,g_2^z{H_3}{{(m)}^v}\prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}} {{S_{1,j,k}}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}{\text{(0)}} \cdot {\mathit{\Delta} _{k,Team}}(0)}} \prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_i},k}}} {{H_2}{{(j)}^{{r_{j,k}}}}} } \right)} } \right)}} = \hfill \\ \frac{{e\left( {g,\prod\limits_{k \in Team} {{{(g_2^{{H_1}({\lambda _{i,k}}){a_{k,0}} + {a_{k,0}}})}^{{\mathit{\Delta} _{k,Team}}(0)}}} } \right)\prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}} {e({H_2}(j),{g^{{t_{j,k}} \cdot {\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}(0) \cdot {\mathit{\Delta} _{k,Team}}(0)}})} } \right)} }}{{e\left( {g,\prod\limits_{k \in Team} {\left( {{{\prod\limits_{j \in {{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}} {({H_2}{{(j)}^{{t_{j,k}}}}g_2^{{H_1}({\lambda _{i,k}}){q_k}(j)})} }^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_i},k}} \cup {\mathit{\Omega} _{I{D_i},k}}}}(0) \cdot {\mathit{\Delta} _{k,Team}}(0)}}} \right)} } \right)}} = \hfill \\ \frac{{e(g,g_2^{{a_0}})e\left( {g,\prod\limits_{k \in Team} {g_2^{{H_1}({\lambda _{i,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)}} } \right)}}{{e\left( {g,\prod\limits_{k \in Team} {g_2^{{H_1}({\lambda _{i,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)}} } \right)}} = e({g_1},{g_2}) = Z. \hfill \\ \end{array} $

3.6 批验证

很多情况下, 验证者需要同时验证大量签名.然而, 基于属性的环签名体制需要进行计算代价较高的双线性对运算, 因此极大地限制了该体制的应用.本文借鉴文献[26]的批验证思想, 基于定义3, 提出了一种适用于本方案的批验证算法, 该算法能够将验证计算量由由nO(·)降为O(·)+n, 有效地提高了验证效率.

对于大量消息-签名对${\{ {m_i},{\sigma _i} = \langle {\sigma _{1,i}},{\sigma _{2,i}},{\sigma _{3,i}},{\{ {\sigma _{4,j,k,i}}\} _{j \in \omega _{i,k}^* \cup {\mathit{\Omega} _{i,k}},k \in Tea{m_i}}}\rangle \} _{1 \leqslant i \leqslant n}}$, 其中, n为消息-签名对的数量, μ= (μ₁, …, μ_n)为$Z_q^*$上的随机向量.具体验证过程如下:

$ \frac{{e(g,\sigma _{2,1}^{{\mu _1}}...\sigma _{2,n}^{{\mu _n}})\prod\limits_{1 \leqslant i \leqslant n} {e({H_3}({m_i}),\sigma _{3,i}^{{\mu _i}})\prod\limits_{k \in \mathop \cup \limits_{1 \leqslant i \leqslant n} \{ Tea{m_i}\} } {\prod\limits_{j \in \mathop \cup \limits_{1 \leqslant i \leqslant n} \{ \omega _{i,k}^* \cup {\mathit{\Omega} _{i,k}}\} } {e({H_2}(j),{\sigma _{4,j,k,1}}^{{\mu _1}}...{\sigma _{4,j,k,\kappa }}^{{\mu _\kappa }})} } } }}{{e(g,\sigma _{1,1}^{{\mu _1}}...\sigma _{1,n}^{{\mu _n}})}} = {Z^{\sum\nolimits_{i = 1}^n {{\mu _i}} }}, $

其中, κ为任意属性对应子签名的数量, 满足1≤κ≤n.若等式成立, 说明{σ₁, σ₂, …, σ_n}是消息{m₁, m₂, …, m_n}对应的合法签名; 否则, 说明{σ₁, σ₂, …, σ_n}中存在σ_i不是对应消息m_i的合法签名.针对这种情况, 可以通过二分法快速查找非法消息-签名对, 算法具体细节请参考文献[26], 在此不再赘述.

4 安全性分析

定理1(无条件强匿名性). 本文所提出的分布式无中心授权的属性基可变门限环签名方案具备无条件强匿名性.

证明:因为从签名属性集合${\{ \omega _k^*\} _{k \in Team}}$中任意选取满足断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}}$的属性子集${\{ {\omega '_{I{D_i},k}}\} _{k \in Team}}$作为实际签名属性集合均可产生合法的签名, 且验证签名无需使用${\{ {\omega '_{I{D_i},k}}\} _{k \in Team}}$, 所以任何敌手均无法获得${\{ {\omega '_{I{D_i},k}}\} _{k \in Team}}$的任何信息.接下来只需证明通过签名无法揭露签名者的实际身份ID_i, 即可证明该方案具备无条件强匿名性.

1) 初始化

A声明挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in Team}}$.挑战者C运行初始化算法, 并将生成的系统公开参数params和系统秘密参数privates全部发送给A, 因此, A可以生成系统中所有用户的任意属性密钥.

2) 挑战阶段

A随机选择消息m^*和用户ID₁(属性集合为${\omega _{I{D_1}}}$), ID₂(属性集合为${\omega _{I{D_2}}}$), 满足${\mathit{\Upsilon} _{{t_k},\omega _k^*}}({\omega _{I{D_1}}}) = {\mathit{\Upsilon} _{{t_k},\omega _k^*}}({\omega _{I{D_2}}}) = 1$, 并将m^*, $(I{D_1},{\omega _{I{D_1}}}),(I{D_2},{\omega _{I{D_2}}})$发送给C.

● C首先运行密钥生成算法生成相应的密钥集合:

$ S{K_1} = \langle {\{ S_{1,j,k}^1\} _{j \in {\omega _{I{D_1},k}} \cup {\mathit{\Omega} _{I{D_1},k}},k \in Team}}{\{ S_{2,k}^1\} _{k \in Team}}\rangle ,\\ S{K_2} = \langle {\{ S_{1,j,k}^2\} _{j \in {\omega _{I{D_2},k}} \cup {\mathit{\Omega} _{I{D_2},k}},k \in Team}}{\{ S_{2,k}^2\} _{k \in Team}}\rangle . $

● 然后抛掷一枚公平硬币b∈{1, 2}, 调用签名算法使用SK_b生成m^*相应的签名:

$ \sigma _b^* = \langle \sigma _1^{b*},\sigma _2^{b*},\sigma _3^{b*},{\{ \sigma _{4,j,k}^{b*}\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_b},k}},k \in Team}}\rangle . $

● 最后, 将$\sigma _b^*$发送给A进行猜测.其中,

$\begin{align} & \sigma _{1}^{b*}=g_{2}^{{{z}_{b}}+\sum\limits_{k\in Team}{{{H}_{1}}({{\lambda }_{b,k}}){{a}_{k,0}}\cdot {{\mathit{\Delta}}_{k,Team}}(0)}}{{H}_{3}}{{({{m}^{*}})}^{{{v}_{b}}}} \\ & \ \ \ \prod\limits_{k\in Team}{\left( \prod\limits_{j\in {{{{\omega }'}}_{I{{D}_{b}},k}}\cup {{\mathit{\Omega }}_{I{{D}_{b}},k}}}{{{({{H}_{2}}{{(j)}^{{{t}_{j,k}}}})}^{{{\mathit{\Delta}}_{j\in {{{{\omega }'}}_{I{{D}_{b}},k}}\cup {{\mathit{\Omega }}_{I{{D}_{b}},k}}}}(0)\cdot {{\mathit{\Delta}}_{k,Team}}(0)}}}\prod\limits_{j\in \omega _{k}^{*}\cup {{\mathit{\Omega }}_{I{{D}_{b}},k}}}{{{H}_{2}}{{(j)}^{r_{j,k}^{b}}}} \right)}, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sigma _{2}^{b*}=g_{2}^{{{z}_{b}}+{{a}_{0}}+\sum\limits_{k\in Team}{{{H}_{1}}({{\lambda }_{b,k}}){{a}_{k,0}}\cdot {{\mathit{\Delta}}_{k,Team}}(0)}}, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sigma _{3}^{b*}={{g}^{{{v}_{b}}}}, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{\left\{ \sigma _{4,j,k}^{b*}=T{{_{j,k}^{b}}^{{{\mathit{\Delta}}_{j,{{{{\omega }'}}_{I{{D}_{b}},k}}\cup {{\Omega }_{I{{D}_{b}},k}}}}(0)\cdot {{\mathit{\Delta}}_{k,Team}}(0)}}{{g}^{r_{j,k}^{b}}} \right\}}_{j\in {{{{\omega }'}}_{I{{D}_{b}},k}}\cup {{\mathit{\Omega }}_{I{{D}_{b}},k}},k\in Team}}, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{\left\{ \sigma _{4,j,k}^{b*}={{g}^{r_{j,k}^{b}}} \right\}}_{j\in \omega _{k}^{*}\backslash {{{{\omega }'}}_{I{{D}_{b}},k}},k\in Team}}. \\ \end{align} $

3) 猜测阶段

A输出对b的猜测b', 若b=b', 则A赢得游戏, 说明本方案不具备无条件强匿名性.

下面分析A不可能赢得游戏的原因.

假设C在b=1的条件下选取$Z_q^*$上的随机数v₁, z₁及随机数集合${\{ r_{j,k}^1\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_1},k}},k \in Team}}$, 使用SK₁生成m^*相应的签名$\sigma _1^*$, 但该签名与C选取${\{ {\omega '_{I{D_2},k}} \cup {\mathit{\Omega} _{I{D_2},k}}\} _{k \in Team}} = {\{ {\omega '_{I{D_1},k}} \cup {\mathit{\Omega} _{I{D_1},k}}\} _{k \in Team}},{z_2} = {z_1} + \sum\limits_{k \in Team} {{H_1}({\lambda _{1,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} - $ $\sum\limits_{k \in Team} {{H_1}({\lambda _{2,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} $, v₂=v₁, ${\{ r_{j,k}^2\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_1},k}},k \in Team}} = {\{ r_{j,k}^1\} _{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_2},k}},k \in Team}}$, 使用SK₂为m^*生成的相应签名$\sigma _2^*$相等, 因此, C也可以声明该签名是在b=2的条件下生成的.同理可证:C在b=2的条件下生成签名$\sigma _2^*$, 其同样可以声明该签名是在b=1条件下产生的.

因为$\sigma _b^*$中仅有$\sigma _1^{b*},\sigma _2^{b*}$中包含用户的身份信息, 所以, 这里仅对的正确性进行验证.

$ \begin{array}{1} \sigma _1^{1*} = g_2^{{z_1} + \sum\limits_{k \in Team} {{H_1}({\lambda _{1,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} }{H_3}{({m^*})^{{v_1}}}\\ \ \ \ \ \ \prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_1},k}} \cup {\mathit{\Omega} _{I{D_1},k}}} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j \in {{\omega '}_{I{D_1},k}} \cup {\mathit{\Omega} _{I{D_1},k}}}}(0) \cdot {\mathit{\Delta} _{k,Team}}(0)}}} \prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_1},k}}} {{H_2}{{(j)}^{r_{j,k}^1}}} } \right)} \hfill \\ \ \ \ \ \ = g_2^{{z_2} + \sum\limits_{k \in Team} {{H_1}({\lambda _{2,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} }{H_3}{({m^*})^{{v_2}}}\\ \ \ \ \ \ \prod\limits_{k \in Team} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_2},k}} \cup {\mathit{\Omega} _{I{D_2},k}}} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j \in {{\omega '}_{I{D_2},k}} \cup {\mathit{\Omega} _{I{D_2},k}}}}(0) \cdot {\mathit{\Delta} _{k,Team}}(0)}}} \prod\limits_{j \in \omega _k^* \cup {\mathit{\Omega} _{I{D_2},k}}} {{H_2}{{(j)}^{r_{j,k}^2}}} } \right)} \hfill \\ \ \ \ \ \ = \sigma _1^{2*}, \hfill \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sigma _2^{1*} = g_2^{{z_1} + {a_0} + \sum\limits_{k \in Team} {{H_1}({\lambda _{1,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} } = g_2^{{z_2} + {a_0} + \sum\limits_{k \in Team} {{H_1}({\lambda _{2,k}}){a_{k,0}} \cdot {\mathit{\Delta} _{k,Team}}(0)} } = \sigma _2^{2*} \end{array} $

成立.证毕.

定理2(适应性选择消息和断言攻击下存在性不可伪造). 本文所提出的分布式无中心授权的属性基可变门限环签名方案在适应性选择消息和断言攻击下是存在性不可伪造的.

证明:在随机预言机模型及适应性选择消息和断言攻击条件下, 若攻击者A能够以一个不可忽略的优势ε在多项式时间内攻破本方案, 则存在算法C, 能够以不可忽略的优势ε'在多项式时间内解决CDH困难问题, 其中,

$ \varepsilon ' \approx \frac{\varepsilon }{{{q_{{H_2}}}{q_{{H_3}}}\prod\limits_{k \in \psi \cup \bar l} {\left( {\begin{array}{*{20}{c}} {{d_k} - {t_k}} \\ {{d_k} - 1} \end{array}} \right)} }}. $

1) 系统建立:假设攻击者A已经攻破l−1个属性授权机构, 不失一般性, 假设这些已被攻破的属性授权机构组成集合Ψ={AA₁, AA₂, …, AA_l−1}, 其余未被攻破的属性授权机构组成集合T={AA_l, AA_l+1, …, AA_n}.因此, 攻击者A只需再攻破集合T中任何一个成员$A{A_{\bar l}}$, 就可以成功地伪造任意消息的合法签名.

A声明挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \psi \cup \bar l}}$, 其中, 1≤t_k≤d_k, d_k为AA_k预设门限值.挑战者C运行初始化算法Setup(d), 生成系统的公开参数$params = \langle e,g,{g_1},{g_2},Z,{H_1},{H_2},{H_3}{\kern 1pt} {\kern 1pt} ,{\{ {P_k}\} _{k = 1,...,n}},{\kern 1pt} {\kern 1pt} {\{ {T_{j,k}}\} _{j \in {\omega _k} \cup {\mathit{\Omega} _k},k = 1,...,n}},q\rangle $以及秘密参数privates= $\langle {\{ {t_{j,k}}\} _{j \in {\omega _k} \cup {\mathit{\Omega} _k},k = 1,...,n}},{\{ {a_{k,0}},{x_k}\} _{k = 1,...,n}}\rangle $, 并将params和集合Ψ中成员的秘密参数$\langle {\{ {t_{j,k}}\} _{j \in {\omega _k} \cup {\mathit{\Omega} _k},k \in \psi }},{\{ {a_{k,0}},{x_k}\} _{k \in \psi }}\rangle $发送给攻击者A.

2) 预言仿真阶段:假设攻击者A分别可以进行${q_{{H_1}}},{q_{{H_2}}},{q_{{H_3}}},{q_k},{q_s}$次H_i(i=1, 2, 3)预言仿真、密钥解析预言仿真和签名预言仿真.挑战者C将H_i(i=1, 2, 3)预言仿真和密钥解析预言仿真的结果分别存储于列表List_i(i=1, 2, 3)和List_key中.

a) H₁-询问:C维护一个包含数组(ID_i, AA_k, H_{1, j, k})的列表List₁.当A对$(I{D_\varsigma },A{A_{\bar l}})$进行H₁询问时, C进行如下操作.

● C首先检查列表List₁, 若List₁中存在数组$(I{D_\varsigma },A{A_{\bar l}},{H_{1,\varsigma ,\bar l}})$, 则将${H_{1,\varsigma ,\bar l}}$作为对$(I{D_\varsigma },A{A_{\bar l}})$进行H₁询问的应答发送给A.

● 否则, C随机选取${\alpha _{\varsigma ,\bar l}} \in Z_q^*$, 把${H_{1,\varsigma ,\bar l}} = {\alpha _{\varsigma ,\bar l}}$作为对$(I{D_\varsigma },A{A_{\bar l}})$进行H₁询问的应答发送给A, 并将数组$(I{D_\varsigma },A{A_{\bar l}},{H_{1,\varsigma ,\bar l}})$存入列表List₁.

b) H₂-询问:C维护一个包含数组(j_k, H_{2, j, k})的列表List₂.当A对属性${j_{\bar l}}$进行H₂询问时, C随机选取缺省属性集合$\mathit{\Omega} _{\bar l}^*$, 满足$|\mathit{\Omega} _{\bar l}^*| = {d_{\bar l}} - {t_{\bar l}}$, 进行如下操作.

● C首先检查列表List₂:如果List₂中存在数组$({j_{\bar l}},{H_{2,j,\bar l}})$, 则将${H_{2,j,\bar l}}$作为对${j_{\bar l}}$进行H₂询问的应答发送给A.

● 否则, 若${j_{\bar l}} \in \omega _{\bar l}^* \cup \mathit{\Omega} _{\bar l}^*$, C随机选取${\beta _{\bar l,j}} \in Z_q^*$, 把${H_{2,j,\bar l}} = {g^{{\beta _{\bar l,j}}}}$作为对${j_{\bar l}}$进行H₂询问的应答发送给A, 并将数组$({j_{\bar l}},{H_{2,j,\bar l}})$存入列表List₂.

● 否则, ${j_{\bar l}} \notin \omega _{\bar l}^* \cup \mathit{\Omega} _{\bar l}^*$, C随机选取${\beta _{\bar l,j}},{\gamma _{\bar l,j}} \in Z_q^*$, 把${H_{2,j,\bar l}} = g_1^{ - {\beta _{\bar l,j}}}{g^{{\gamma _{\bar l,j}}}}$作为对${j_{\bar l}}$进行H₂询问的应答发送给A, 并将数组$({j_{\bar l}},{H_{2,j,\bar l}})$存入列表List₂.

c) H₃-询问:C维护一个包含数组(m_i, H_{3, i})的列表List₃, 并选取一个随机数$\delta \in [1,{q_{{H_3}}}]$.当A对m_ζ进行H₃询问时, C进行如下操作.

● C首先检查列表List₃:若List₃中存在数组(m_ζ, H_{3, ζ}), 则将H_{3, ζ}作为对m_ζ进行H₃询问的应答发送给A.

● 否则, 若ζ=δ, C随机选取${\eta _\delta } \in Z_q^*$, 把${H_{3,\varsigma }} = {g^{{\eta _\delta }}}$作为对m_ζ进行H₃询问的应答发送给A, 并将数组(m_ζ, H_{3, ζ})存入列表List₃.

● 否则, ζ≠δ, C随机选取${\theta _\varsigma },{\eta _\varsigma } \in Z_q^*$, 把${H_{3,\varsigma }} = g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}}$作为对m_ζ进行H₃询问的应答发送给A, 并将数组(m_ζ, H_{3, ζ})存入列表List₃.

d) 密钥解析询问:C维护一个包含数组${({\omega _{I{D_i},k}},I{D_i},{\{ {T_{k,j}},{S_{k,j}}\} _{j \in {\omega _{I{D_i},k}} \cup \mathit{\Omega} _k^*}},P)_k}$的列表List_key.当A输入$({\omega _{I{D_\varsigma },\bar l}},$ $I{D_\varsigma })$进行密钥解析询问时, C进行如下操作.

● C检查列表List_key:若List_key中存在数组$\left( {{\omega _{I{D_\varsigma },\bar l}},I{D_\varsigma },{{\{ {T_{\bar l,j}},{S_{\bar l,j}}\} }_{j \in {\omega _{I{D_\varsigma },\bar l}} \cup \mathit{\Omega} _{\bar l}^*}},{P_{\bar l}}} \right)$, 则将${\{ {T_{\bar l,j}},{S_{\bar l,j}}\} _{j \in {\omega _{I{D_\varsigma },\bar l}} \cup \mathit{\Omega} _{\bar l}^*}}$和${P_{\bar l}}$作为对$({\omega _{I{D_\varsigma },\bar l}},I{D_\varsigma })$进行密钥解析询问的应答发送给A.

● 否则, 若$|{\omega _{I{D_\varsigma },\bar l}} \cap \omega _{\bar l}^*| < {t_{\overline l }}$, C随机选取缺省属性集合$\mathit{\Omega} _{\bar l}^*$, 满足$|\mathit{\Omega} _{\bar l}^*| = {d_{\bar l}} - {t_{\bar l}}.$定义3个属性集合${\mathit{\Gamma } _{\bar l}},{\mathit{\Gamma } '_{\bar l}},{S_{\bar l}}$, 其中, ${\mathit{\Gamma } _{\bar l}} \subseteq {\mathit{\Gamma } '_{\bar l}} \subset {S_{\bar l}},{\mathit{\Gamma } _{\bar l}} = {\omega _{I{D_\varsigma },\bar l}} \cap \omega _{\bar l}^* \cup \mathit{\Omega} _{\bar l}^*,|{\mathit{\Gamma } '_{\bar l}}| = {d_{\bar l}} - 1,{S_{\bar l}} = {\mathit{\Gamma } '_{\bar l}} \cup \{ 0\} $.由拉格朗日插值公式可知, ${a_0} = $ $\sum\limits_{k \in \mathit{\Psi} \cup \bar l} {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} ,$由于A已经攻破集合Ψ中所有属性授权机构, 因此, $A{A_{\bar l}}$的部分密钥满足等式${a_{\bar l,0}} = $ $\frac{{{a_0} - \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}.$

对于属性${j_{\bar l}} \in {\mathit{\Gamma } '_{\bar l}}$, C首先随机选取${x'_{\bar l}},{\tau _{j,\bar l}},{t_{j,\bar l}} \in Z_q^*$, 等价于隐性地令${q_{\bar l}}(j) = {\tau _{j,\bar l}}$; 然后分别对ID_ζ和${j_{\bar l}}$进行预言机询问得到H₁(λ_ζ)和${H_2}({j_{\bar l}})$的仿真结果, 最后C生成相应属性的密钥.

$ {\{ {S_{1,j,\bar l}} = {H_2}{(j)^{{t_{j,\bar l}}}}g_2^{{H_1}({\lambda _{\varsigma ,\bar l}}){\tau _{j,\bar l}}}\} _{j \in \mathit{\Gamma } '}},{S_{2,\bar l}} = g_1^{ - {{x'}_{\bar l}}}g_2^{\frac{{ - ({H_1}({\lambda _{\varsigma ,\bar l}}) + 1) \cdot \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}},\\ {\{ {T_{1,j,\bar l}} = {g^{{t_{j,\bar l}}}}\} _{\xi \in \mathit{\Gamma } '}},{P_{\bar l}} = g_1^{{{x'}_{\bar l}}}. $

正确性验证:令${x_{\bar l}} = \frac{{({H_1}({\lambda _{\varsigma ,\bar l}}) + 1) \cdot {b_0}}}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} + {x'_{\bar l}}$, 则下列等式成立.

$ {S_{2,\bar l}} = g_1^{ - {{x'}_{\bar l}}}g_2^{\frac{{ - ({H_1}({\lambda _{\varsigma ,\bar l}}) + 1) \cdot \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}} = g_1^{ - \left( {{x_{\bar l}} - \frac{{({H_1}({\lambda _{\varsigma ,\bar l}}) + 1) \cdot {b_0}}}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}} \right)}g_2^{\frac{{ - ({H_1}({\lambda _{\varsigma ,\bar l}}) + 1) \cdot \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}} \\ = g_1^{ - {x_{\bar l}}}g_2^{{H_1}({\lambda _{\varsigma ,\bar l}}){a_{\bar l,0}} + {a_{\bar l,0}}}. $

对于属性${\xi _{\bar l}} \notin \mathit{\Gamma } '$, 为了确保等式${q_{\bar l}}(0) = {a_{\bar l,0}}$成立, C随机选取${t'_{\xi ,\bar l}} \in Z_p^*$, 计算相应的属性密钥:

$ {S_{1,\xi ,\bar l}} = {(g_1^{ - {\beta _{\bar l,\xi }}}{g^{{\gamma _{\bar l,\xi }}}})^{{{t'}_{\xi ,\bar l}}}}g_2^{{\gamma _{\bar l,\xi }} \cdot \frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} + {H_1}({\lambda _{\varsigma ,\bar l}})\left( {\sum\limits_{j \in {{\mathit{\Gamma } '}_{\bar l}}} {{q_{\bar l}}(j)} {\mathit{\Delta} _{j,{S_{\bar l}}}}(\xi ) - \frac{{\sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}{\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )} \right)},\\ {T_{1,\xi ,\bar l}} = g_2^{\frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}}{g^{{{t'}_{\xi ,\bar l}}}}. $

正确性验证:令${t_{\xi ,\bar l}} = \frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} \cdot {b_0} + {t'_{\xi ,\bar l}}$, 由于${q_{\bar l}}(\xi ) = \sum\limits_{j \in {{\mathit{\Gamma } '}_{\bar l}}} {{q_{\bar l}}(j)} {\mathit{\Delta} _{j,{S_{\bar l}}}}(\xi ) + {q_{\bar l}}(0){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )$, 故下列等式成立.

$ {S_{1,\xi ,\bar l}} = {(g_1^{ - {\beta _{\bar l,\xi }}}{g^{{\gamma _{\bar l,\xi }}}})^{{{t'}_{\xi ,\bar l}}}}g_2^{{\gamma _{\bar l,\xi }} \cdot \frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} + {H_1}({\lambda _{\varsigma ,\bar l}})\left( {\sum\limits_{j \in {{\mathit{\Gamma } '}_{\bar l}}} {{q_{\bar l}}(j)} {\mathit{\Delta} _{j,{S_{\bar l}}}}(\xi ) - \frac{{\sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}{\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )} \right)} \\ \ \ \ \ \ = {(g_1^{ - {\beta _{\bar l,\xi }}}{g^{{\gamma _{\bar l,\xi }}}})^{{t_{\xi ,\bar l}} - \frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} \cdot {b_0}}}\\ \ \ \ \ \ g_2^{{\gamma _{\bar l,\xi }} \cdot \frac{{{H_1}({\lambda _{\varsigma ,\bar l}}){\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )}}{{{\beta _{\bar l,\xi }}{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}} + {H_1}({\lambda _{\varsigma ,\bar l}})\left( {\sum\limits_{j \in {{\mathit{\Gamma } '}_{\bar l}}} {{q_{\bar l}}(j)} {\mathit{\Delta} _{j,{S_{\bar l}}}}(\xi ) - \frac{{\sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }}{{{\mathit{\Delta} _{\bar l,\mathit{\Psi} \cup \bar l}}(0)}}{\mathit{\Delta} _{0,{S_{\bar l}}}}(\xi )} \right)} \\ \ \ \ \ \ = {(g_1^{ - {\beta _{\bar l,\xi }}}{g^{{\gamma _{\bar l,\xi }}}})^{{t_{\xi ,\bar l}}}}g_2^{{H_1}({\lambda _{\varsigma ,\bar l}}){q_{\bar l}}(\xi )}. $

把相应密钥集合发送给A, 并将数组$\left( {{\omega _{I{D_\varsigma },\bar l}},I{D_\varsigma },{{\{ {T_{j,\bar l}},{S_{j,\bar l}}\} }_{j \in {\omega _{I{D_{\varsigma ,\bar l}}}} \cup \mathit{\Omega} _{\bar l}^*}},{P_{\bar l}}} \right)$存入列表List_key.

● 否则, $|{\omega _{I{D_\varsigma },\bar l}} \cap \omega _{\bar l}^*| \geqslant {t_{\overline l }}$, C停止仿真, 将该事件记为E₁.

e) 签名询问:A输入$({\omega _{I{D_\varsigma }}},I{D_\varsigma },{m_\varsigma })$进行签名询问, C进行如下操作.

● 若$|{\omega _{I{D_\varsigma },\bar l}} \cap \omega _{\bar l}^*| < {t_{\overline l }}$, C通过对${({\omega _{I{D_\varsigma },k}},I{D_\varsigma })_{k \in \psi \cup \bar l}}$进行密钥解析询问, 获得相应属性的密钥, 对m_ζ进行H₃询问得到H₃(m_ζ)的仿真结果, 直接利用签名算法得到m_ζ相应的签名, 并发送给A.

● 否则, $|{\omega _{I{D_\varsigma },\bar l}} \cap \omega _{\bar l}^*| \geqslant {t_{\overline l }},$若${H_3}({m_\varsigma }) \ne {g^{{\eta _\delta }}},$C首先随机选取属性集合${\{ {\omega '_{I{D_\varsigma },k}}\} _{k \in \psi \cup \bar l}}$和缺省属性集合${\{ \mathit{\Omega} _k^*\} _{k \in \psi \cup \bar l}},$其中, ${\omega '_{I{D_\varsigma },k}} \subseteq \{ {\omega _{I{D_\varsigma },k}} \cap \omega _k^*\} $且$|{\omega '_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*| = $d_k; 然后, 选随机数$z,v' \in Z_q^*$和随机数集合$\{ {r_{j,k}} \in $ $Z_q^*{\} _{k \in \mathit{\Psi} \cup \bar l,j \in \omega _k^* \cup \mathit{\Omega} _k^*}};$最后, 通过下述方法生成m_ζ对应的签名${\sigma _\varsigma } = \langle \sigma _1^\varsigma ,\sigma _2^\varsigma ,\sigma _3^\varsigma ,{\{ \sigma _{4,j,k}^\varsigma \} _{j \in \omega _k^* \cup \mathit{\Omega} _k^*,k \in \psi \cup \bar l}}\rangle ,$其中,

$ \begin{array}{1} {\sigma _1} = g_2^{z - \frac{{{\eta _\varsigma } \cdot {H_1}({\lambda _{i,\bar l}})}}{{{\theta _\varsigma }}} + \sum\limits_{k \in \mathit{\Psi} } {({H_1}({\lambda _{i,k}}) - {H_1}({\lambda _{i,\bar l}})){a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\\ {(g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}})^{v'}}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} , \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\sigma _2} = g_2^{z - ({H_1}({\lambda _\varsigma }) + 1) \cdot \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\prod\limits_{k \in \mathit{\Psi} } {{{(g_2^{{H_1}({\lambda _i}){a_{k,0}}{\text{ + }}{a_{k,0}}})}^{{\mathit{\Delta} _{_{k,\mathit{\Psi} \cup \bar l}}}(0)}}} , \\ \ \ \ \ \ {\sigma _3} = g_2^{ - \frac{{{H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}}}{g^{v'}}{\left\{ {{\sigma _{4,j,k}} = {{({T_{j,k}})}^{{\mathit{\Delta} _{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0){\mathit{\Delta} _{k \in \mathit{\Psi} \cup \bar l}}(0)}}g_2^{{r_{j,k}}}} \right\}_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*,k \in \psi \cup \bar l}}\\ {\{ {\sigma _{4,j,k}} = g_2^{{r_{j,k}}}\} _{j \in \omega _k^*\backslash {{\omega '}_{I{D_\varsigma },k}},k \in \psi \cap \bar l}}. \end{array} $

正确性验证:令$v = - \frac{{{H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}} \cdot {b_0} + v'$, 则下列等式成立.

$ \begin{array}{1} {\sigma _1}{\kern 1pt} = g_2^{z - \frac{{{\eta _\varsigma } \cdot {H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}} + \sum\limits_{k \in \mathit{\Psi} } {({H_1}({\lambda _{\varsigma ,k}}) - {H_1}({\lambda _{\varsigma ,\bar l}})){a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\\ {(g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}})^{v'}}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = g_2^{z - \frac{{{\eta _\varsigma } \cdot {H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}} + \sum\limits_{k \in \mathit{\Psi} } {({H_1}({\lambda _{\varsigma ,k}}) - {H_1}({\lambda _{\varsigma ,\bar l}})){a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }{(g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}})^{{\kern 1pt} v + \frac{{{H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}} \cdot {b_0}}} \hfill \\ {\text{ }}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = g_2^{z + \sum\limits_{k \in \mathit{\Psi} } {({H_1}({\lambda _{\varsigma ,k}}) - {H_1}({\lambda _{\varsigma ,\bar l}})){a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} } {(g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}})^{{\kern 1pt} v}}g_2^{{H_1}({\lambda _{\varsigma ,\bar l}}) \cdot \sum\limits_{k \in \mathit{\Psi} \cup \bar l} {{a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\ \ \ \ \ \ \ ; \hfill \\ {\text{ }}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = g_2^{z + \sum\limits_{k \in \mathit{\Psi} \cup \bar l} {{H_1}({\lambda _{\varsigma ,k}}) \cdot {a_{k,0}} \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\\ {(g_1^{{\theta _\varsigma }}{g^{{\eta _\varsigma }}})^{{\kern 1pt} v}}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {{{({H_2}{{(j)}^{{t_{j,k}}}})}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = g_2^z{H_3}{(m)^v}\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\left( {\prod\limits_{j \in {{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*} {S_{1,j,k}^{{\mathit{\Delta} _{j,{{\omega '}_{I{D_\varsigma },k}} \cup \mathit{\Omega} _k^*}}(0) \cdot {\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)}\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {{H_2}{{(j)}^{{r_{j,k}}}}} } } \right)} {\kern 1pt} {\kern 1pt} , \hfill \\ {\sigma _2} = g_2^{z - ({H_1}({\lambda _\varsigma }) + 1) \cdot \sum\limits_{k \in \mathit{\Psi} } {{a_{k,0}}{\mathit{\Delta} _{k,\mathit{\Psi} \cup \bar l}}(0)} }\prod\limits_{k \in \mathit{\Psi} } {{{(g_2^{{H_1}({\lambda _i}){a_{k,0}} + {a_{k,0}}})}^{{\mathit{\Delta} _{_{k,\mathit{\Psi} \cup \bar l}}}(0)}}} {\kern 1pt} \\ = g_2^z{({P_{\bar l}}{S_{2,\bar l}})^{{\mathit{\Delta} _{_{\bar l,\mathit{\Psi} \cup \bar l}}}(0)}}\prod\limits_{k \in \mathit{\Psi} } {{{({P_k}{S_{2,k}})}^{{\mathit{\Delta} _{_{k,\mathit{\Psi} \cup \bar l}}}(0)}}} {\kern 1pt} = g_2^z\prod\limits_{k \in \mathit{\Psi} \cup \bar l} {{{({P_k}{S_{2,k}})}^{{\mathit{\Delta} _{_{k,\mathit{\Psi} \cup \bar l}}}(0)}}} ,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\sigma _3} = g_2^{ - \frac{{{H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}}}{g^{v'}} = {g^{ - \frac{{{H_1}({\lambda _{\varsigma ,\bar l}})}}{{{\theta _\varsigma }}} \cdot {b_0} + v'}} = g_2^v. \end{array} $

● 否则, C停止仿真, 将该事件记为E₂.

3) 伪造阶段:攻击者A在挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \psi \cup \bar l}}$和缺省属性集合${\{ {\overline{\mathit{\Omega }} _k}\} _{k \in \psi \cup \bar l}}$的条件下, 成功地伪造了消息$m_\varsigma ^*$的签名$\sigma _\varsigma ^* = \langle \sigma _{1,\varsigma }^*,\sigma _{2,\varsigma }^*,\sigma _{3,\varsigma }^*,{\{ \sigma _{4,j,k}^*\} _{k \in \mathit{\Psi} \cup \bar l,j \in \omega _k^* \cup {{\overline{\mathit{\Omega }} }_k}}}\rangle .$如果${H_3}(m_\varsigma ^*) = {g^{{\eta _\delta }}}$且${\{ {\overline{\mathit{\Omega }} _k} = \mathit{\Omega} _k^*\} _{k \in \psi \cup \bar l}}$, 则下列等式成立.

$ \frac{{e(g,\sigma _{2,\varsigma }^*)e({g^{{\eta _\delta }}},\sigma _{3,\varsigma }^*)\prod\limits_{k \in \psi \cup \bar l} {\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {e({g^{\beta _{k,j}^*}},\sigma _{4,j,k}^*)} } }}{{e(g,\sigma _{1,\varsigma }^*)}} = Z = e(g,{g^{{a_0} \cdot {b_0}}}). $

因此, C可以成功地解决CDH困难问题, 其中, ${g^{{a_0} \cdot {b_0}}} = \frac{{\sigma _{2,\varsigma }^* \cdot \sigma _{3,\varsigma }^{*{\eta _\delta }} \cdot \prod\limits_{k \in \mathit{\Psi} \cup \bar l} {\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {\sigma _{4,j,k}^{*\beta _{k,j}^*}} } }}{{\sigma _{1,\varsigma }^*}}.$

下面分析C成功解决CDH困难问题的优势.

在伪造过程中要求${H_3}(m_\varsigma ^*) = {g^{\eta _\delta ^*}},{\{ {\overline{\mathit{\Omega }} _k} = \mathit{\Omega} _k^*\} _{k \in \psi \cup \bar l}}$且H₂(j)已知, 因为|Ω_k|=d_k−1, 进行H₂, H₃预言仿真的次数分别为${q_{{H_2}}},{q_{{H_3}}},$所以C成功解决CDH困难问题的优势为$\varepsilon ' \approx \frac{\varepsilon }{{{q_{{H_2}}}{q_{{H_3}}}\prod\limits_{k \in \psi \cup \bar l} {\left( {\begin{array}{*{20}{c}} {{d_k} - {t_k}} \\ {{d_k} - 1} \end{array}} \right)} }}.$证毕.

定理3(适应性选择消息和断言攻击下抗合谋攻击). 本文所提出的分布式无中心授权的属性基可变门限环签名方案在适应性选择消息和断言攻击下可以抵抗合谋攻击.

证明:假设存在攻击者A分别可以进行${q_{{H_1}}},{q_{{H_2}}},{q_{{H_3}}},{q_k},{q_s}$次H_i(i=1, 2, 3)预言仿真、密钥解析预言仿真和签名预言仿真.若该攻击者A能够在适应性选择消息和断言攻击的条件下, 以一个不可忽略的优势ε在多项式时间内攻破本方案, 则存在算法C可以在多项式时间内以不可忽略的优势ε'解决CDH困难问题, 其中,

$ \varepsilon ' \approx \frac{\varepsilon }{{{q_{{H_2}}}{q_{{H_3}}}\prod\limits_{k \in \psi \cup \bar l} {\left( {\begin{array}{*{20}{c}} {{d_k} - {t_k}} \\ {{d_k} - 1} \end{array}} \right)} }}. $

1) 系统建立

同定理2的系统建立过程.

2) 预言仿真阶段

同定理2的预言仿真阶段.

3) 挑战阶段

攻击者A在挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \psi \cup \bar l}}$和缺省属性集合${\{ {\overline{\mathit{\Omega }} _k}\} _{k \in \psi \cup \bar l}}$的条件下, 挑战该方案的抗合谋攻击性.

A首先随机选取用户ID₁(属性集合为ω₁), ID₂(属性集合为ω₂), 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega _1}) \ne 1,{\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega _2}) \ne 1$, 且存在属性集合${\omega '_{1,\bar l}} \subseteq {\omega _{1,\bar l}},{\omega '_{2,\bar l}} \subseteq {\omega _{2,\bar l}}$, 满足${\mathit{\Upsilon} _{{t_{\bar l}},\omega _{\bar l}^*}}({\omega '_{1,\bar l}} \cup {\omega '_{2,\bar l}}) = 1$;

然后, 分别对$(I{D_1},A{A_{\bar l}}),(I{D_2},A{A_{\bar l}})$进行H₁询问, 得到${H_1}({\lambda _{1,\bar l}}),{H_1}({\lambda _{2,\bar l}})$的仿真结果${\alpha _{1,\bar l}}$和${\alpha _{2,\bar l}};$

对$({\omega '_{1,\bar l}},I{D_1}),({\omega '_{2,\bar l}},I{D_2})$进行密钥解析询问得到密钥集合:

$ \begin{gathered} {\{ S_{1,j,\bar l}^1 = {H_2}{(j)^{{t_{j,\bar l}}}}g_2^{{\alpha _{1,\bar l}} \cdot {q_{\bar l}}(j)},S_{2,\bar l}^1 = g_1^{ - {x_{\bar l}}}g_2^{{\alpha _{1,\bar l}} \cdot {a_{\bar l,0}} + {a_{\bar l,0}}},{T_{j,\bar l}} = {g^{{t_{j,\bar l}}}},{P_{\bar l}} = g_1^{{x_{\bar l}}}\} _{j \in {{\omega '}_{1,\bar l}} \cup {{\overline{\mathit{\Omega }} }_{1,\bar l}}}}, \hfill \\ {\{ S_{1,j,\bar l}^2 = {H_2}{(j)^{{t_{j,\bar l}}}}g_2^{{\alpha _{2,\bar l}} \cdot {q_{\bar l}}(j)},S_{2,\bar l}^2 = g_1^{ - {x_{\bar l}}}g_2^{{\alpha _{2,\bar l}} \cdot {a_{\bar l,0}} + {a_{\bar l,0}}},{T_{j,\bar l}} = {g^{{t_{j,\bar l}}}},{P_{\bar l}} = g_1^{{x_{\bar l}}}\} _{j \in {{\omega '}_{2,\bar l}} \cup {{\overline{\mathit{\Omega }} }_{2,\bar l}}}}; \hfill \\ \end{gathered} $

其次, 为用户ID₂生成新的属性密钥集合:

$ \{ {S_{1,j,\bar l}^{2'} = S{{_{1,j,\bar l}^2}^{\frac{{{\alpha _{1,\bar l}}}}{{{\alpha _{2,\bar l}}}}}} = {H_2}{{(j)}^{{t_{j,\bar l}} \cdot \frac{{{\alpha _{1,\bar l}}}}{{{\alpha _{2,\bar l}}}}}}g_2^{{\alpha _{1,\bar l}} \cdot {q_{\bar l}}(j)},\\ S_{2,\bar l}^{2'} = S_{2,\bar l}^1 = g_1^{ - {x_{\bar l}}}g_2^{{\alpha _{1,\bar l}} \cdot {a_{\bar l,0}} + {a_{\bar l,0}}},{{T'}_{j,\bar l}} = T_{j,\bar l}^{\frac{{{\alpha _{1,\bar l}}}}{{{\alpha _{2,\bar l}}}}} = {g^{{t_{j,\bar l}} \cdot \frac{{{\alpha _{1,\bar l}}}}{{{\alpha _{2,\bar l}}}}}},{P_{\bar l}} = g_1^{{x_{\bar l}}}} \}_{j \in {{\omega '}_{2,\bar l}} \cup {{\overline{\mathit{\Omega }} }_{2,\bar l}}}; $

最终, A可以获得签名密钥集合${\{ S_{1,j,k}^1 \cup S_{1,j,\bar l}^{2'},S_{2,k}^1,{T_{j,k}} \cup {T'_{j,\bar l}},{P_k}\} _{j \in {{\omega '}_{1,k}} \cup {{\omega '}_{2,\bar l}} \cup {{\overline{\mathit{\Omega }} }_k},k \in \psi \cup \bar l}}.$

4) 伪造阶段

攻击者A在挑战断言${\{ {\mathit{\Upsilon} _{{t_k},\omega _k^*}}( \cdot )\} _{k \in \psi \cup \bar l}}$和缺省属性集合${\{ {\overline{\mathit{\Omega }} _k}\} _{k \in \psi \cup \bar l}}$的条件下, 成功地伪造消息m^*的签名σ^*= $\langle \sigma _1^*,\sigma _2^*,\sigma _3^*,{\{ \sigma _{4,j,k}^*\} _{j \in \omega _k^* \cup {{\overline{\mathit{\Omega }} }_k},k \in \psi \cup \bar l}}\rangle $, 并将σ^*发送给C进行验证.如果${H_3}({m^*}) = {g^{{\eta _\delta }}}$且${\{ {\overline{\mathit{\Omega }} _k} = \mathit{\Omega} _k^*\} _{k \in \psi \cup \bar l}}$, 则下列等式成立:

$ \frac{{e(g,\sigma _2^*)e({g^{{\eta _\delta }}},\sigma _3^*)\prod\limits_{k \in \psi \cup \bar l} {\prod\limits_{j \in \omega _k^* \cup \mathit{\Omega} _k^*} {e({g^{{\beta _{k,j}}}},\sigma _{4,j,k}^*)} } }}{{e(g,\sigma _1^*)}} = Z = e(g,{g^{{a_0} \cdot {b_0}}}). $

因此, C可以成功地解决CDH困难问题, 其中, ${g^{{a_0} \cdot {b_0}}} = \frac{{\sigma _2^* \cdot \sigma _3^{*{\eta _\delta }} \cdot \prod\limits_{k \in \psi \cup \bar l} {\prod\limits_{\xi \in \omega _k^* \cup \mathit{\Omega} _k^*} {\sigma _{4,j,k}^{*{\beta _{k,j}}}} } }}{{\sigma _1^*}}.$

正确性验证如下:

下面分析C成功解决CDH困难问题的优势.

在合谋攻击过程中, 要求${H_3}({m^*}) = {g^{{\eta _\delta }}},{\{ {\overline{\mathit{\Omega }} _k} = \mathit{\Omega} _k^*\} _{k \in \psi \cup \bar l}}$, H₂(j)${H_{\text{2}}}(j)$, 由于|Ω_k|=d_k−1, 进行H₂, H₃预言仿真的次数分别为${q_{{H_2}}},{q_{{H_3}}}$, 因此, C成功解决CDH困难问题的优势为$\varepsilon ' \approx \frac{\varepsilon }{{{q_{{H_2}}}{q_{{H_3}}}\prod\limits_{k \in \psi \cup \bar l} {\left( {\begin{array}{*{20}{c}} {{d_k} - {t_k}} \\ {{d_k} - 1} \end{array}} \right)} }}.$证毕.

5 效率比较与性能分析

本节将从效率和性能两方面与现有方案进行对比, 进而得出本方案的综合评估结果.评估过程所用符号及其定义见表 1, 效率比较见表 2, 性能比较见表 3.

综合表 2和表 3的结果可知, 虽然文献[20, 21]中的方案和本文方案的形式化安全证明均基于随机预言机模型, 但是目前仅有这3个方案可以抵抗合谋攻击, 因此下面主要针对这3个方案进行分析.当|T|=1时, 即本文所提出的方案与文献[20]中的方案均使用单属性授权机构为相应属性分发密钥, 此时, 本方案密钥长度与文献[20]中的方案相等, 签名长度仅比文献[20]中的方案多1|G₁|bit, 虽然就签名效率而言本方案不占优势, 但是由于本文提出了一种高效地批验证方法, 因此验证效率很高, 且即便仅对单个签名进行验证, 本方案的计算量也比文献[20]中的方案少(|B|+d−t)T_e−1T_p; 同时, 本方案匿名性明显优于文献[20]中的方案, 且当|T|≠1时, 本方案可以解决文献[20]中的方案存在的属性密钥托管问题.

若不考虑动态门限的实现, 本方案签名长度和验证计算量与文献[21]中的方案相差不大, 比文献[21]中的方案分别多1|G₁|bit和1T_p, 虽然签名计算量比文献[21]中的方案高(2+|T|)T_e, 但是文献[21]中的方案引入了密钥匿名分发协议, 因此就密钥长度而言, 比本方案长(|A|−|T|+|T|²)|G₁|bit, 导致其AA与用户之间的通信代价很大.此外, 该方案只能在单属性授权机构, 即存在的属性密钥托管问题的安全模型下, 被证明具备匿名性和不可伪造性, 并未给出抗合谋攻击的形式化安全证明.而本文方案可以在克服密钥长度过长这一前提下, 在假设存在l−1个不可信授权属性机构的安全模型下, 被证明同时具备无条件强匿名性、不可伪造性和抗合谋攻击性.

上述分析表明, 综合考虑安全性和效率两方面性能, 本文方案较现有方案具有更大优势.

6 总结

本文针对现有基于属性的门限环签名方案无法同时具备无条件强匿名性和抗合谋攻击性, 并且存在属性密钥托管、验证效率低、签名门限固定等问题, 通过采用分布式密钥生成协议以及在属性密钥和签名中分别嵌入用户身份标识和用户身份模糊因子的方式, 提出了一个分布式无中心授权的属性基可变门限环签名方案.该方案同时具备无条件强匿名性和抗合谋攻击性.在假设存在l−1个不可信属性授权机构的前提下, 该方案被证明在适应性选择消息和断言攻击下是存在性不可伪造的, 并且能够抵抗由拥有互补属性集合的恶意用户发动合谋攻击.另外, 还提出了一种适用于本方案的批验证算法, 有效地提高了验证效率.