可证明安全的可变门限代理重签名方案

杨小东，张 磊， 王彩芬

(西北师范大学计算机科学与工程学院,甘肃 兰州 730070)

1 引言

门限代理重签名利用秘密共享技术，将重签名密钥分割成n个子密钥分发给n个代理者管理，能有效减少重签名密钥泄露所带来的损失。文献[1]提出了两个门限代理重签名方案，但双向门限代理重签名方案所基于的代理重签名方案存在安全缺陷。为了弥补该方案存在的安全缺陷，文献[2]提出了一个改进的双向门限代理重签名方案。在现有的门限代理重签名方案中，门限值几乎是固定的[1,2]。然而，在许多实际应用场合中，参加重签名的代理者数目往往取决于签名消息的重要性，这就要求签名方案的门限值k是可变的。例如,专家团E去审查某公司的项目M时，如果M是一个大型项目，则需要k1(≤k)个专家成员参与生成项目M的重签名；如果M是个中型项目，则需要k2(≤k1)个专家成员参与生成项目M的重签名；如果M是一个小型项目，则需要k3(≤k2)个专家成员参与生成项目M的重签名。

虽然代理重签名的研究已取得了一定的进展[3～7]，但门限代理重签名和可变门限代理重签名的研究才刚刚起步，关于可变门限代理重签名的公开文献非常少。文献[8]提出了可变门限代理重签名的思想，并构造了一个可证明安全的可变门限代理重签名方案，但该方案对存储空间的要求比较高。本文提出一个具有较短公开参数和签名长度的可变门限代理重签名方案，并给出了新方案的安全性证明。在门限重签名密钥生成算法中，分发者和每个代理者之间仅通信一次。根据可变的门限值，每个代理者都能非交互地生成相应的重签名子密钥和验证公钥。

2 准备知识

设p是一个大素数，G是一个阶为p的循环群，g是G的一个生成元，群G上的CDH(Computational Diffie-Hellman)问题是：已知(g,ga,gb)∈G3，计算gab，这里a、b∈Zp。

定义1(CDH假设)如果没有一个概率多项式时间算法在时间t内以至少ε的概率解决群G上的CDH问题，则称群G上的(t,ε)-CDH假设成立。

定理1(中国剩余定理)设q1、q2、…、qk是两两彼此互素的k个正整数，Q=q1q2…qk，则一次同余方程组x=ai(modqi)(i=1,2,…,k)，对模Q有唯一解。

x=(Q1e1a1+Q2e2a2+…+Qkekak)(modQ)

这里Qi=Q/qi，Qiei=1(modqi)(i=1,2,…,k)。

定义2一个可变门限代理重签名方案是一个由概率多项式时间算法构成的七元组(Setup,KeyGen,RekeyShare,Sign,ResignShare,Combine,Ver)。

(1)Setup是系统参数生成算法：输入一个安全参数1λ，输出系统参数cp。

(2)KeyGen、Sign和Ver算法与标准数字签名体制中的密钥生成算法、签名算法和签名验证算法相同。

(5)Combine是门限重签名生成算法：给定k个诚实代理者对消息m的部分重签名σB,i1,…,σB,ik，输出一个对应于公钥pkB的消息m的门限重签名σB。

3 一个新的可变门限代理重签名方案

在Ateniese G等人[3]提出的代理重签名方案Sbi的基础上，提出了一个新的可变门限代理重签名方案。该方案是双向的、透明的、多用的和密钥最优的。新方案由受托者、委托者和n个半可信的代理者(P1,…,Pn)组成。新方案具体描述如下：

(1)Setup：给定一个安全参数1λ，选择一个大素数p和两个阶为p的循环群G1和G2，定义一个双线性映射e:G1×G1→G2。选择G1的一个生成元g和一个安全的密码学哈希函数H:{0,1}*→G1。随机选取n个两两互素的正整数q0

(3)RekeyShare：给定一个受托者的私钥skA=α和一个委托者的私钥skB=β，该算法执行如下操作：

②根据中国剩余定理求解同余式组:

可得a0=y(modQ)。

④广播Aj=gaj/α和Bj=gaj，j=0,…,n-1，其中A0=gβ/α，B0=pkB。

⑤根据中国剩余定理求解同余式组:

(4)Sign：给定一个私钥sk=α和一个签名消息m，输出m的签名σ=H(m)α。

(7)Ver：输入一个消息m、一个公钥pk和一个待验证的签名σ，如果e(σ,g)=e(pk,H(m))，输出1；否则，输出0。

4 安全性分析与证明

4.1 正确性分析

本方案的正确性可以通过以下方程得到验证。

(1)门限值为k时的重签名子密钥的正确性验证。

(2)门限值为k时的部分重签名的正确性验证。

e((H(m)α)fk(i)/α,g)=e(H(m)fk(i),g)=

e(H(m),gfk(i))=e(vkk,i,H(m))

(3)门限值为k时的门限重签名的正确性验证。

e(H(m)β,g)=e(pkB,H(m))

4.2 安全性分析

利用文献[8]可模拟性的安全性证明方法，证明本文提出的新方案的安全性。

定理2门限重签名密钥生成算法RekeyShare是可模拟的。

□

定理3门限重签名生成算法ResignShare是可模拟的。

□

定理4本文提出的新方案是强壮的。

证明对于任意的门限值k，在RekeyShare算法中至少需要k个代理者才能重构出重签名密钥，而最多可容许k-1个代理者被攻陷。在ResignShare算法中，一旦有恶意的代理者提供了非法的部分重签名，重签名合成者便能发现并确认出代理者的身份。即使攻击者攻陷了k-1个代理者，只要有k个诚实的代理者就能产生一个正确的重签名。当代理者的数目n≥2k-1时，恶意的攻击者无法影响方案的正确执行，所以我们提出的可变门限代理重签名方案满足强壮性。

□

定理5如果一个可变门限代理重签名方案是可模拟的，且关联于该门限方案的代理重签名方案是安全的，则可变门限代理重签名方案也是安全的[8]。

定理6在随机预言模型下，代理重签名方案Sbi在适应性选择消息攻击下是安全的，其安全性可归约到CDH假设[3]。

结合定理2～定理6，可得如下定理：

定理7在随机预言模型下，本文所提出的可变门限代理重签名方案在CDH假设下是安全的；对于某个门限值k，如果n≥2k-1，则新方案也是强壮的。

4.3 性能比较

将本文提出的新方案与文献[1,2,8]的双向门限代理重签名方案进行计算开销和带宽效率方面的比较，结果如表1所示。但是，文献[1,2]所提出的双向门限代理重签名方案的门限值是固定的，仅有文献[8]提出的双向门限代理重签名方案的门限值是可变的。为了便于描述，令E表示G上的指数运算，P表示双线性对运算，|G|表示G中一个元素的长度，n表示代理者的总数，nm表示文献[1,2,8]方案中待签名消息的长度。

Table 1 Comparison of bidirectional threshold proxy re-signature schemes表1 双向门限代理重方案的比较

从表1可知，在本文提出的新方案中签名算法Sign需要一次指数运算，部分重签名生成算法ResignShare需要一次指数运算和两次双线性对运算，签名和重签名仅为G中的一个元素。因此，新方案的计算开销和带宽效率高于文献[8]的双向可变门限代理重签名方案。

5 结束语

本文基于代理重签名方案Sbi，提出了一个可变门限代理重签名方案，并给出了该方案的安全性证明。根据消息的重要性，能灵活地选择不同的门限值进行相应的门限重签名。在该方案中，分发者和代理者之间仅通信一次；代理者得到初始重签名子密钥后，根据可变的门限值能灵活地生成相应的重签名子密钥和验证公钥。与已有的同类方案相比，具有更短的公开参数和签名长度。如何在标准模型[9]下构造安全高效的可变门限代理重签名方案，将是我们下一步研究的工作方向。

[1] Yang Pi-yi,Cao Zhen-fu,Dong Xiao-lei.Threshold proxy re-signature[C]∥Proc of IPCCC’08, 2008:450-455.

[2] Yang Xiao-dong, Wang Cai-fen. Threshold proxy re-signature schemes in the standard model[J]. Chinese Journal of Electronics, 2010, 19(2E):345-350.

[3] Ateniese G, Hohenberger S. Proxy re-signatures:New definitions, algorithms, and applications[C]∥Proc of the 12th ACM CCS, 2005:310-319.

[4] Shao Jun, Wei Gui-yi, Ling Yun, et al. Unidirectional identity-based proxy re-signature[C]∥Proc of 2011 IEEE ICC, 2011:1-5.

[5] Guo Dun-tao, Wei Ping, Yu Dan, et al. A certificateless proxy re-signature scheme[C]∥Proc of IEEE ICCSIT’10, 2010:157-161.

[6] Yang Xiao-dong,Wang Cai-fen.Efficient on-line/off-line proxy re-signature schemes[J]. Journal of Electronics & Information Technology, 2011, 33(12):2916-2921.(in Chinese)

[7] Hong Xuan, Chen Ke-fei, Wan Zhong-mei. Simplified universally composable proxy re-signature[J]. Journal of Software, 2010, 21(8):2079-2088. (in Chinese)

[8] Yang Xiao-dong, Wang Cai-fen, Lan Cai-hui, et al. Flexible threshold proxy re-signature schemes[J]. Chinese Journal of Electronics, 2011, 20(4E):691-696.

[9] Sun Hua, Zhong Luo, Wang Ai-min. Provably secure identity-based threshold ring signature in the standard model[J]. Computer Engineering & Science, 2013, 35(3):92-96.(in Chinese)

附中文参考文献：

[6] 杨小东，王彩芬.高效的在线/离线代理重签名方案[J].电子与信息学报，2011,33(12):2916-2921.

[7] 洪璇，陈克非，万中美.简单的通用可组合代理重签名方案[J].软件学报，2010,21(8):2079-2088.

[9] 孙华, 钟珞, 王爱民. 标准模型下可证安全的基于身份门限环签名[J]. 计算机工程与科学, 2013, 35(3):92-96.