标准模型下可撤销的基于身份的代理重签名方案

杨小东，李雨潼，王晋利，麻婷春，王彩芬

（1. 西北师范大学计算机科学与工程学院，甘肃 兰州 730070；2. 密码科学技术国家重点实验室，北京 100878）

基于身份的代理重签名是一种具有转换签名功能的密码体制，一个半可信的代理者能将 Alice的签名转换为Bob对同一个消息的签名，但代理者无法获得Alice或Bob的签名密钥的任何信息。在一种基于身份的代理重签名方案中，用户选择如E-mail地址、手机号码等身份标识作为公钥，而私钥由可信的密钥生成中心（PKG, private key generator）生成并通过安全的信道发送给用户。基于身份的代理重签名体制避免了复杂的公钥证书，简化了密钥管理，在云计算、大数据隐私保护等方面有广泛的应用[1-2]。

基于文献[3]的加密方案，Shao等[4]构造了第一种标准模型下安全的基于身份的代理重签名方案；Feng等[5]利用抗碰撞的散列函数设计了一种基于身份的代理重签名方案，但该方案不满足多用性；Hu等[6]提出了一种紧规约的基于身份的代理重签名方案，但该方案的安全性依赖于较强的困难问题假设；Shao等[7]又设计了一种随机预言模型下安全的单向基于身份的代理重签名方案，但该方案的验证重签名的计算开销与重签名级数呈线性增长关系；Huang等[8]提出了一种无双线性对的基于身份的代理重签名方案，并在随机预言模型中证明了该方案的安全性可归约到离散对数问题。文献[9-10]分别构造了格上基于身份的代理重签名方案，但这2种方案的参数尺寸、密钥长度和签名长度都比较大，并且安全性依赖于理想的随机预言机。然而，在随机模型中被证明安全的密码方案，当利用具体的散列函数实例化随机预言机时，随机预言模型并不能确保方案的实际安全性[11]。因此，研究标准模型下安全的基于身份的代理重签名方案具有一定的现实意义。

在实际应用中，任何实用的密码系统都面临用户撤销的问题，比如用户权限到期或用户密钥泄露，这就需要从密码系统中撤销用户。为了实现基于身份的用户撤销机制，文献[12]提出了PKG定期更新未撤销用户密钥的撤销方法，但 PKG与未撤销用户之间需要建立一个安全信道来传输更新密钥。Boldyreva等[13]提出了PKG通过公开信道实现用户撤销的方法，随后一些基于Boldyreva所提方法的可撤销加密方案相继被提出[14-15]。为了解决签名方案中的用户撤销问题，Tsai等[16]提出了第一种可撤销的基于身份签名方案，但Liu等[17]发现该方案存在签名密钥泄露的安全风险。近年来，一些具有特殊性质的可撤销签名方案[18-20]也相继被提出，如可撤销的属性基签名[21]、可撤销的无证书签名[22-23]、可撤销的代理签名[24]、可撤销的前向安全签名[25]等。

现有的基于身份的代理重签名方案均未考虑用户撤销问题，而用户撤销功能对一种实用的基于身份的代理重签名方案是非常重要的。例如 Alice是某公司的总经理，负责该公司所有文件的签名。如果Alice因公出差，由该公司的副总经理Bob生成公司文件的签名，利用Alice和Bob之间的重签名密钥，将Bob的签名转换为Alice对同一文件的签名。由于工作调动或身体健康的原因，Bob离开了公司。为了公司的利益，需要撤销Bob的签名权限。因此，基于身份代理重签名体制在实现签名转换的同时，还必须支持高效的用户撤销机制。

鉴于此，本文提出了可撤销的基于身份代理重签名方案，并给出了相应的形式化定义与安全模型。基于Shao等[4]提出的代理重签名方案和二叉树结构，本文构造了一种可撤销的双向基于身份的代理重签名方案，在标准模型下证明了所构造方案的安全性可规约到计算性Diffie-Hellman Diffie-Hellman（CDH, computational Diffie-Hellman）困难问题。本文所提方案实现了用户的撤销与密钥的更新，能抵抗签名密钥泄露攻击，并且 PKG的工作量与用户的数量呈对数增长关系，具有良好的延展性。

2 准备知识

2.1 符号说明

本文所使用的符号及其说明如表1所示。

2.2 双线性映射

令p是一个大素数，G和GT是2个阶为p的乘法循环群，g是G的一个生成元。如果一个可计算的映射e:G×G→GT满足以下条件，则称e是一个双线性映射[4]。

1) 双线性：对任意的a,b∈Zp，有

2.3 KUNode算法

选择基于二叉树的 KUNode算法[26]来提高未撤销用户的密钥更新效率。令BT表示一棵具有N个叶子节点的二叉树，root表示树的根节点。对于每个非叶子节点θ，用θl和θr表示θ的左孩子节点和右孩子节点。每个用户将分配至BT上的一个叶子节点η，用path(η)表示从叶子节点η到根节点root的路径上的所有节点集合。RL表示一个由叶子节点ηi和时间周期ti组成的撤销列表，Y表示BT中需要更新的最小节点集合。如果η∈RL，则path(η) ∩Y=∅。KUNode算法的输入是BT、RL和时间周期t，输出是Y。KUNode算法的具体描述如算法1所示。

表1 符号列表及其说明

算法1KUNode算法

输入BT、RL和时间周期t

输出需要更新的最小节点集合Y

1) 设置集合X=∅,Y=∅

2) ∀ (ηi,ti)∈ RL

3) 如果ti≤t，在X中添加 path(ηi)

4) ∀θ∈X

5) 如果θl∉X，在Y中添加θl

6) 如果θr∉X，在Y中添加θr

7) 如果Y=∅，在Y中添加root

8) 返回Y

2.4 困难问题假设

定义1CDH假设。如果所有多项式时间算法无法解决G上CDH问题，则称G上的CDH问题是困难的[4]。

3 可撤销的基于身份代理重签名的安全性定义

3.1 形式化定义

一种撤销的双向基于身份的代理重签名方案由下面9种算法构成。

1) setup (1λ,N,T)→ (pp,msk,RL,st)是系统参数建立算法：输入安全参数λ、最大用户数N和用户签名密钥有效期的最大时间周期T，输出公开参数pp、PKG的主密钥msk、初始化为空集的用户撤销列表RL和状态st。

2) extract (pp,msk,ID)→skID是秘密密钥生成算法：输入pp、msk和用户身份ID，输出秘密密钥skID。

3) KeyUp (pp,msk,t,RL,st)→ ukt是密钥更新算法：输入pp、msk、更新的时间周期t、当前的用户撤销列表RL和状态st，如果t＞T，输出一个错误符号“⊥”；否则，输出一个更新密钥ukt。

4) SKGen (pp,skID,ukt)→ dkID,t是签名密钥生成算法：输入pp、skID和ukt，如果用户身份ID在时间周期t已被撤销，输出⊥；否则，输出对应于ID和t的签名密钥dkID,t。

6) sign (pp,dkID,t,t,M)→σ是签名生成算法：输入pp、dkID,t、当前时间周期t(t≤T)和消息M，输出关于M的签名σ，其中dkID,t是用户身份ID在时间周期t的签名密钥。

8) verify (pp,ID,t,M,σ)→{0,1}是签名验证算法：输入pp、身份ID、时间周期t(t≤T)、消息M和签名σ，如果σ是合法的，输出1；否则，输出0。

9) revoke (ID,t,RL,st)→ RL′是用户撤销算法：输入时间周期t(t≤T)内，撤销的用户身份ID、用户撤销列表RL和状态st，输出更新后的用户撤销列表RL′。

3.2 安全模型

借鉴基于身份的代理重签名方案的安全模型[4,7]和可撤销的基于身份签名方案的安全性定义[17-19]，本文通过攻击者A和挑战者C之间的安全游戏，给出可撤销的双向基于身份的代理重签名方案的安全模型。

初始化C运行setup(1λ,N,T)算法，将生成的系统参数pp发送给A，自己秘密保存主密钥msk。

询问A自适应地向C发起有限次的如下询问。

1) extract-query：对于A请求的关于身份ID的秘密密钥询问，C运行算法extract(pp,msk,ID)，将输出的秘密密钥skID发送给A。

2) KeyUp-query：对于A请求的关于时间周期t(t≤T)的更新密钥询问，其中t不能小于以前所有询问过的时间周期，C运行算法 KeyUp (pp,msk,t,RL,st)，将生成的更新密钥ukt发送给A。

3) SKGen-query：收到A发送的关于(ID,t)的签名密钥询问后，C首先询问关于ID的 extractquery和关于t≤T的KeyUp-query，分别获得相应的秘密密钥skID与更新密钥ukt；然后运行算法SKGen(pp,skID,ukt)生成签名密钥dkID,t，并将dkID,t发送给A。为了不失一般性，这里要求A未进行关于t的 KeyUp-query询问前，不能发起关于t的SKGen-query询问。

4) ReKey-query：收到A发送的关于 2个身份(IDA,IDB)和时间周期t的重签名密钥询问后，C首先询问关于(IDA,t)和(IDB,t)的 SKGen-query，获得对应的签名密钥dkA,t与dkB,t；然后将算法 ReKey(pp,dkA,t,dkB,t)生成的重签名密钥rkA→B,t发送给A。

5) sign-query：收到A发送的关于身份ID、时间周期t(t≤T)与消息M的签名询问后，C询问关于(ID,t)的SKGen-query获得签名密钥dkID,t，并运行算法sign (pp,dkID,t,t,M)，将生成的M的签名σ返回给A。

6) revoke-query：如果A在时间周期t(t≤T)发起过关于身份ID的KeyUp-query，则A在时间周期t不能发起关于ID的revoke-query。收到A发送的(ID,t)后，其中t不能小于以前所有询问过的时间周期，C运行算法revoke(ID,t,RL,st)，并将输出的用户撤销列表RL′返回给A。

伪造攻击者A最后输出身份ID*、时间周期t*(t≤T)、消息M*和签名σ*。如果以下5个条件均成立，则称A在以上游戏中获胜。

1) verify (pp,ID*,t*,M*,σ*)=1。

2) (ID*,t*)未进行过SKGen-query询问。

3) ID*未进行过 extract-query询问，并且t*≤T未进行过KeyUp-query询问。

4) ID*未进行过ReKey-query询问。

5) (ID*,t*,M*)未进行过sign-query询问。

定义2若任何一个多项式时间攻击者A在上述游戏中获胜的概率是可忽略的，则称可撤销的双向基于身份的代理重签名方案在适应性选择身份和消息攻击下是存在不可伪造的。

定义 3如果攻击者无法从当前时间周期t泄露的签名密钥dkID,t中获取秘密密钥skID或威胁其他时间周期签名密钥的安全性，则称可撤销的基于身份的代理重签名方案满足抗签名密钥泄露攻击性。

4 可撤销的双向基于身份的代理重签名方案

在Shao方案[4]基础上，本文2.3节的KUNode算法构造了一种可撤销的双向基于身份的代理重签名方案。假设用户身份的长度和签名消息的长度分别为mbit和nbit，可通过 2个散列函数H1:{0,1}*→ {0,1}m和H2:{0,1}*→{0,1}n，将用户身份和签名消息的固定长度延伸为可变长度，即对于任意长度的身份ID′和签名消息M′，计算从而将身份ID′和消息M′分别映射为长度为m和n的比特串。为了简化表述，假设方案中的用户身份和消息都进行了散列函数H1和H2的预处理，即用符号ID和M分别表示长度为mbit的用户身份和长度为nbit的签名消息。

4.1 方案描述

1) setup算法

输入安全参数λ、最大用户数N和最大时间周期T，PKG执行如下操作。

① 选择一个大素数p，2个阶为p的乘法循环群G和GT，一个G的生成元g和一个双线性映射

② 在G中随机选取

④ 选择一棵具有N个叶子节点的二叉树BT，设置用户撤销列表RL=∅和状态st=BT。

⑤ 秘密保存主密钥msk=α，公开参数pp=

为了表述方便，对于长度为mbit的用户身份和长度为nbit的签名消息和

2) extract算法

为了生成用户身份ID的秘密密钥，PKG执行如下操作。

① 在BT上随机选择一个空的叶子节点η，并在η中保存ID。

② 对于每个节点θ∈path(η)，随机选择gθ∈G，并在θ中保存；选择一个随机数，计算

3) KeyUp算法

对于时间周期t、撤销列表RL和状态st，如果t＞T，输出⊥；否则，PKG通过如下步骤生成更新密钥ukt。

① 对于每个节点θ∈KUNode (BT, RL,t)，首先在θ中提取，然后随机选取，计算 ukθ=

如果在时间周期t的撤销列表 RL中包含了被撤销的用户身份ID，则PKG调用KUNode算法[26]生成需要更新的最小节点集合Y=KUNode (BT, RL,t)，但被撤销的用户无法获得PKG生成的更新密钥ukt。下面通过一个实例来说明撤销用户的方法。

如图1所示，假设4个用户u1,u2,u3和u4被分配至 4 个叶子节点η3,η4,η5和η6。假设用户u3被撤销，则X=path(η5)={η5,η2, root}，Y={η1,η6}，path(η5)∩Y=∅。除了u3外，从每个用户对应的叶子节点到根节点的路径上至少包含Y中的一个节点。用户u1和u2的路径上包含Y中的节点η1，用户u4的路径上包含Y中的节点η6。在时间周期t，PKG只需更新Y={η1,η6}中每个节点的密钥，便可完成未撤销用户u1,u2和u4的密钥更新，从而实现对用户u3的撤销。

图1 KUNode算法的一个实例

4) SKGen算法

如果用户身份ID在时间周期t≤T已被撤销，输出⊥；否则，一定存在一个节点θ∈KUNode (BT,RL,t)∩path(η)；用户随机选取，利用自己的秘密密钥和公开的更新密钥计算签名密钥为

5) ReKey算法

给定 2个用户身份IDA和IDB的签名密钥和，采用类似文献[4]的安全协议，生成代理者的一个重签名密钥为

6) sign算法

对于当前时间周期t≤T和一个消息M，身份为IDA的签名者随机选取，利用签名密钥计算，输出一个关于M的签名

7) resign算法

8) verify算法

给定身份ID、消息M、时间周期t≤T和签名，验证者检查以下等式是否成立。

如果等式成立，说明σ是一个合法的签名，输出1；否则，输出0。

9) revoke算法

给定 BT上存储被撤销用户身份ID的叶子节点η，当前时间周期t≤T、用户撤销列表RL和状态 st，PKG 在 RL 中添加 (η,t)，即 RL′=，并输出更新后的用户撤销列表RL′。

4.2 正确性分析

假设身份IDB的签名密钥对于消息M的重签名，其中

则Bσ的正确性验证如下

上述推导过程证明了本文方案的正确性。

通过IDA与IDB间的重签名密钥rkA→B,t，很容易计算出IDB与IDA间的重签名密钥，所以本文方案具有双向性。

4.3 安全性分析

定理1 如果CDH假设成立，则本文方案满足标准模型下自适应性选择身份和消息攻击的存在不可伪造性。

证明 假设攻击者A进行了最多qsk次秘密密钥询问、quk次更新密钥询问、qdk次签名密钥询问、qrk次重签名密钥询问、qs次签名询问和qr次撤销询问后，以不可忽略的概率ε攻破了本文方案的存在不可伪造性，则存在一个挑战者C将利用攻击者A的伪造，以不可忽略的概率'ε解决G上的CDH问题。对于一个CDH问题实例的目标是计算gab。

初始化C设置参数和，满足lu(m+1)＜p和lm(n+1)＜p。随机选取2个整数和km(0≤km≤n)，并随机选择。选择一棵具有N个叶子节点的二叉树BT，设置最大时间周期T、用户撤销列表RL=∅和状态st=BT，参数并发送系统参数给A。

询问C回答A发起的一系列如下询问。

1) extract-query：为了响应A请求的关于身份ID的秘密密钥询问，C维持一个初始化为空的列表tsk。如果F(ID)=0 modp，C退出模拟；否则，C执行如下操作。

① 在BT上随机选择一个空的叶子节点η，并在η中保存ID。

② 对于每个节点θ∈path(η)，随机选择gθ∈G，并在θ中保存gθ。如果tsk中不存在(θ,rθ,ID)，随机选取rθ∈Zp，将(θ,rθ,ID)添加到tsk中。然后提取rθ，计算

2) KeyUp-query：为了响应A请求的关于时间周期t的更新密钥询问，C维持一个初始化为空的列表Tuk，如果t＞T，输出⊥；否则，C执行如下操作。

① 对于每个节点θ∈KUNode (BT, RL,t)，首先在θ中提取gθ，然后在Tuk中提取sθ。如果Tuk中不存在，则选择一个随机数，将添加到Tuk中，并计算

3) SKGen-query：为了响应A请求的关于(ID,t)的签名密钥询问，C维持一个初始化为空的列表Tdk。C首先询问关于ID的extract-query和关于t的KeyUp-query，分别获得相应的秘密密钥skID与更新密钥ukt；然后在Tdk中提取(rID,sID)。如果Tdk中不存在(rID,sID,ID,t)，则选择2个随机数rID、sID∈Zp，将(rID,sID,ID,t)添加到Tdk中；最后运行算法SKGen(pp,skID,ukt)，将生成的签名密钥dkID,t返回给A。

4) ReKey-query：对于A请求的关于2个身份(IDA,IDB)和时间周期t的重签名密钥询问，C首先询问关于(IDA,t)和(IDB,t)的 SKGen-query，分别获得对应的签名密钥dkA,t与dkB,t；然后运行算法ReKey(pp,dkA,t,dkB,t)，将生成的重签名密钥rkA→B,t发送给A。

5) sign-query：对于A请求的关于身份ID、时间周期t(t≤T)与消息M的签名询问，如果F(ID)≠0 modp，C询问关于(ID,t)的 SKGen-query获得签名密钥dkID,t，然后运行算法sign(pp,dkID,t,t,M)，并将输出的关于M的签名σ返回给A。如果F(ID)=0 modp，则考虑以下2种情况。

① 如果K(M)=0 modp，则C退出模拟。

② 如果K(M)≠0 modp，则C在Tsk、Tuk、Tdk中提取rθ、sθ和(rID,sID)，并随机选择rm∈Zp，计算，然后将关于M的签名发送给A。

6) revoke-query：对于A请求的关于(ID,t)的撤销询问，C运行算法revoke(ID,t,RL,st)，并将运行结果返回给A。

伪造攻击者A最后输出一个对应于身份*ID和时间周期t*≤T的关于消息M*的签名。如果F(ID*)≠0 modp或退出模拟；否则，C计算CDH值gab过程如下

因此，C利用A的伪造(ID*,t*,M*,σ*)成功求解了CDH问题实例。与文献[3-4]的分析过程相似，C将以的概率成功解决G上的CDH问题。

定理2本文方案满足抗签名密钥泄露攻击性。

证明在 4.1节的方案中，分别用gθ和来构造秘密密钥和更新密钥，并且满足。只有未撤销的用户才能正确恢复出，进而生成合法的签名密钥。如果攻击者获得了未撤销用户ID的签名密钥dkID,t，则利用公开信道传输的更新密码ukt计算

由于在本文方案的SKGen算法中，用户随机选取rID,sID∈Zp对秘密密钥和更新密钥进行了随机化处理，因此攻击者即使获得了用户身份ID在时间周期t的更新密钥dkID,t，但仍然无法直接从dkID,t中计算出对应的秘密密钥skID。因为用户的签名密钥dkID,t通过固定的秘密密钥skID和定期变化的更新密钥ukt生成，所以攻击者在skID未知的情况下不能利用SKGen算法产生其他时间周期的合法签名密钥。

综上所述，即使攻击者获得当前时间段的签名密钥dkID,t，攻击者无法通过dkID,t和公开的更新密钥ukt计算出秘密密钥skID，也不会影响其他时间周期签名密钥的安全性。因此，本文方案能抵抗签名密钥泄露攻击，即满足抗签名密钥泄露攻击性。

4.4 性能分析

文献[4-6]分别提出了3个标准模型下安全的基于身份的代理重签名方案（分别将其命名为 Shao方案[4]、Feng方案[5]和Hu方案[6]），将本文方案与这些方案进行性能比较分析，如表2所示。令N表示用户总数，R表示撤销的用户数，则由KUNode算法的计算复杂度可知[25]，本文方案中 PKG更新密钥的开销为。假设所有方案选择阶为素数p的群G和GT，仅考虑计算开销比较大的双线性对和指数运算，不再讨论计算量较小的乘法运算等操作。在表2中，符号|G|表示群G中一个元素的平均长度，|p|表示有限域Zp中一个元素的平均长度，Pa表示一次双线对运算，exp表示一次指数运算。

从表2可知，与Shao方案[4]相比，本文方案的签名长度和重签名长度多了一个群G中的元素，并且签名验证算法多了一次双线性对运算和一次指数运算。与Feng方案[5]相比，本文方案与该方案有相同的重签名长度，但具有较高的签名验证效率，并满足多用性。与 Hu方案[6]相比，本文方案具有更短的签名长度和重签名长度，并且签名算法的计算效率优于该方案。然而，对比的3种方案均没有考虑用户撤销问题，本文方案实现了用户撤销功能，并且 PKG撤销用户的工作量随用户总数的增加呈对数增长，具有良好的延展性。

将本文方案、Feng方案[5]和 Hu方案[6]进行签名算法的计算时间开销实验对比分析，具体结果如图2所示。选取PBC库的a.param初始化pairing，实验的硬件环境为：2.5 GHz英特尔酷睿i7-6500处理器，8 GB的内存，512 GB的硬盘空间；软件环境为：64位 Windows 10操作系统，密码库PBC-0.4.7-VC。

图2 签名生成的时间开销与消息长度关系

表2 4种方案的计算开销与安全性能比较

由于本文方案是基于Shao方案[4]设计的，因此2种方案生成签名的计算开销相同，均需要2次指数运算。此外，Feng方案[5]需要3次指数运算，Hu方案[6]需要6次指数运算。对于长度相同的签名消息，图 2表明本文方案生成签名的时间开销低于Feng 方案[5]和 Hu 方案[6]。

本文方案利用 KUNode算法[26]来实现用户的撤销，而文献[16]通过PKG直接更新未撤销用户的密钥来实现用户的撤销。下面将2种方案进行密钥更新的性能比较，结果如图3所示。假设用户总数为32个，被撤销的用户数分别为1个、2个、4个、8个和16个。

图3 密钥更新的性能比较

本文方案和文献[16]方案生成每个用户的更新密钥均需要执行2次指数运算，所需的时间开销约为15 ms。由图3可知，当被撤销的用户数小于用户总数的一半时，本文方案需要更新密钥的用户个数小于文献[16]方案。因此，本文方案具有更低的用户撤销开销。

5 结束语

本文基于 Shao方案[4]和 KUNode算法[26]，构造了一种可撤销的基于身份的代理重签名方案，并在标准模型下证明了其安全性依赖于 CDH假设。本文方案支持用户撤销功能，满足双向性和多用性，可有效抵抗签名密钥泄露攻击，具有良好的延展性。但本文方案无法抵抗量子计算攻击，下一步的任务是设计格上可撤销的基于身份的代理重签名方案。