一种强不可伪造代理重签名方案

杨小东,李春梅,周思安,王彩芬

一种强不可伪造代理重签名方案

杨小东,李春梅,周思安,王彩芬

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

已有的代理重签名方案大多是存在性不可伪造的,攻击者能对已经签名过的消息重新伪造一个有效的签名,但强不可伪造性能阻止攻击者对已经签名过的消息签名对进行重新伪造。为此,利用目标抗碰撞(TCR)杂凑函数,提出一种双向代理重签名方案。基于TCR杂凑函数的抗碰撞性和计算性Diffie-Hellman假设,证明方案在适应性选择消息攻击下是强不可伪造的。分析结果表明,该方案在计算效率上优于现有的强不可伪造代理重签名方案,系统公开参数长度、签名长度和重签名长度更短,且满足更多的安全属性。

双向代理重签名;强不可伪造性;可证明安全;计算性Diffie-Hellman假设;标准模型

1 概述

代理重签名具有签名转换的功能,允许一个拥有重签名密钥的代理者将受托者的签名转换为委托者对同一个消息的签名(也称重签名),在跨域身份认证、车联网隐私保护等方面有广泛的应用前景。文献［1］对代理重签名进行了形式化定义。文献［2］提出一个在标准模型下可证明安全的双向代理重签名方案(下文简称Smd方案)。文献［3］发现Smd方案存在安全缺陷,提出了一个改进的签名方案。然而,已有的代理重签名方案［1-8］几乎都是存在性不可伪造的,这种安全性仅要求攻击者不能对一个新消息产生一个有效的签名,但不能阻止对已经签过的消息重新伪造一个有效的签名。强不可伪造性具有更强的安全性,不允许这种伪造［9-10］。强不可伪造性能保证攻击者无法伪造新消息和已经签名过的消息的合法签名,能有效防止电子投票、电子现金和数字版权等的篡改。

现有的在标准模型下可证明安全的代理重签名方案［2-5］都是基于Waters签名方案［11］,但Waters签名方案是可延展的,这就意味着这些代理重签名方案不满足强不可伪造性。然而,具有强不可伪造性的代理重签名的研究才刚刚起步,公开的相关文献较少。文献［12］提出了2个具有强不可伪造性的双向代理重签名方案(下文简称Vivek1方案和Vivek2方案),但这2个方案具有大量的系统公开参数,对存储空间的要求比较高。文献［10］提出了一个标准模型下高效的强不可伪造短签名方案,具有较短的公私钥长度和签名长度。

本文在文献［10］方案的基础上,利用基于密钥的目标抗碰撞(Target Collision Resistant,TCR)杂凑函数［13］,提出一个具有强不可伪造性的双向代理重签名方案。

2 预备知识

2.1 计算性Diffie-Hellman问题

设G1是阶为素数p的循环群,g是G1的生成元,计算性 Diffie-Hellman(Computational Diffie-Hellman,CDH)问题为:已知(g,ga,gb)∈G31,计算gab∈G1,其中,a,b∈RZp。

定义1 CDH假设

若没有一个概率多项式时间算法能在时间t内以至少ε的概率解决群G1上的CDH问题,则称群G1上的(t,ε)-CDH假设成立［2］。

2.2 TCR杂凑函数

假设K为TCR杂凑函数的密钥空间,M1和M2分别为输入和输出消息空间,一个TCR杂凑函数Hk:K×M1→M2实际上是一个通用的基于密钥单向杂凑函数,其中,k∈K。通过下面的游戏来定义一个TCR杂凑函数的安全性:

(1)攻击者输出消息m1∈M1;

(2)挑战者随机选取k∈K,并将k发送给攻击者;

(3)攻击者输出消息m2∈M1,若Hk(m1)= Hk(m2)且m1≠m2,则攻击者赢得游戏。

定义2 如果攻击者在多项式时间t内赢得上述游戏的概率ε是可忽略的,则称TCR杂凑函数Hk是(t,ε)安全的［10］。

3 本文签名方案

3.1 方案描述

利用TCR杂凑函数,构造一个双向代理重签名方案,具体描述如下:

(1)Setup:输入一个安全参数τ,选择2个阶为大素数p的循环群G1和G2,g是G1的一个生成元,并选择一个双线性映射e:G1×G1→G2;在G1中随机选取4个元素g2,v,m0和m1;随机选取一个TCR杂凑函数的密钥k和TCR杂凑函数Hk:{0,1}*→Zp,其中,k∈K,K为TCR杂凑函数的密钥空间;最后输出系统公开参数cp=(G1,G2,p,e,g,g2,v,m0, m1,k,Hk)。

(3)ReKey:输入一个受托者的私钥skA=α和一个委托者的私钥skB=β,生成代理者的重签名密钥rkA→B的过程如下:

1)代理者选取一个随机数r0∈,将r0发送给受托者;

2)受托者收到r0后,计算r1=r0α(mod p),将r1发送给委托者;

3)委托者收到r1后,计算r2=β/r1(mod p),将r2发送给代理者;

4)代理者收到r2后,计算自己的重签名密钥rkA→B=r0r2=r0(β/r1)=r0(β/(r0α))=β/α(modp)。

(4)Sign:输入一个私钥sk=α和一个消息M,生成消息M的签名过程如下:

2)检查 h最右边比特值 u∈{0,1},计算σ2=(muvh)s;

3)输出消息 M 的签名 σ =(σ1,σ2)= (gs,(muvh)s)。

(5)ReSign:输入一个重签名密钥rkA→B,一个消息M,一个公钥pkA和一个签名σA=(σA1,σA2,),如果Verify(pkA,M,σA)=0,输出⊥;否则,选取一个随机数r∈,计算σB3=gr和h2=Hk(M||σB3),检查h2的最右边比特值u2,然后计算σB1=(σA1)rkA→B和σB2=(σA2)rkA→B(mu2vh2)r,最后输出对应于公钥 pkB的消息M的签名σB=(σB1,σB2,σB3)。

(6)Verify:输入一个公钥pk,一个消息M和一个待验证的签名σ,如果σ=(σ1,σ2),则签名验证过程如下:

1)计算h=Hk(M||σ1),检查h的最右边比特值u∈{0,1};

2)验证e(σ2,g)=e(σ1,muvh)e(pk,g2)是否成立,如果成立,那么σ是消息M的有效签名,输出1;否则,输出0。

如果σ=(σ1,σ2,σ3),则签名验证过程如下:

1)计算h=Hk(M||σ1)和h2=Hk(M||σ3),检查h和h2的最右边比特值u,u2∈{0,1};

2)验证e(σ2,g)=e(σ1,muvh)e(pk,g2)e(σ3, mu2vh2)是否成立,如果成立,那么σ是消息M的有效签名,输出1;否则,输出0。

3.2 正确性分析

令受托者的公私钥对(pkA,skA)=(gα,α),委托者的公私钥(pkB,skB)=(gβ,β),消息 M 的签名σA=(σA1,σA2)=(gs,(muvh)s)和重签名密钥rkA→B=β/α,则重签名σB=(σB1,σB2,σB3)的正确性验证过程如下:

因为rkA→B=β/α=1/(α/β)=1/rkB→A,所以新方案满足双向性;由于每个用户保存的私钥仅是Zp中的一个元素,因此新方案也满足密钥最优性。

对于消息M的签名:

3.3 安全性分析

定理 若TCR杂凑函数Hk是(t,ε/2)安全的或G1上的(t,ε/8)-CDH假设成立,则本文提出的代理重签名方案是(t,ε)强不可伪造的。

证明:如果存在一个攻击者A在多项式时间t内最多查询了qE次(未)攻陷用户密钥产生预言机、qs次签名预言机、qRK次重签名密钥生成预言机和qRS次重签名预言机,能以一个不可忽略的概率ε攻破新方案的强不可伪造性,下面证明将存在一个攻击者F能解决G1上的CDH问题或找到Hk的一个碰撞。

类型Ⅰ:对任意i∈{1,2,…,q},总有h*≠hi;

类型Ⅱ:存在某个i∈{1,2,…,q},满足h*=hi。

如果攻击者A能成功伪造一个合法签名,则A的输出必然是类型Ⅰ或类型Ⅱ。下面证明类型Ⅰ的伪造可解决一个CDH问题实例,类型Ⅱ的伪造可找到Hk的一对碰撞。

类型Ⅰ:假设A是类型Ⅰ的攻击者,它能攻破新方案的(t,ε)强不可伪造性,将存在一个攻击者F能解决G1上的CDH问题。给定一个CDH问题实例(g,gα,gβ)∈,F的任务是计算gαβ∈G1。攻击者F执行如下的模拟操作:

(1)建立:设置g1=gα,g2=gβ,随机选取4个元素x,y,z,t∈,计算m0=gx,m1=gy和v=gz,运行Setup算法得到系统其他参数,并将(g,g1,g2,v, m0,m1,k)发送给攻击者A。

(2)查询:F建立如下的预言机。

1)OUKeyGen:F选取一个随机数xi∈,输出公钥pki=(g1)xi=gαxi。

2)OCKeyGen:F选取一个随机数xi∈,输出公私钥对(pki,ski)=(gxi,xi)。

3)OSign:攻击者A输入一个公钥pki和一个消息Mj,F回复如下:

如果pki已被攻陷,F选取一个随机数sj∈Zp,计算hj=Hk(Mj||gsj),然后检查hj的最右边比特值uj∈{0, 1},最后返回签名σj=(σj1,σj2)=(gsj,g2xj(mujvhj)sj);

当pki未被攻陷时,pki=gαxi隐含了对应的密钥为αxi,签名σj=(σj1,σj2)的正确性验证过程如下:

于是有:

4)OReKey:攻击者A输入2个公钥(pki,pkj),如果pki和pkj均已被攻陷或均未被攻陷,攻击者F返回一个重签名密钥rki→j=xj/xi(modp);否则,输出⊥。

5)OReSign:攻击者A输入2个公钥(pki,pkj),一个消息Mi和一个签名σi,如果Verify(pki,Mx,σi)= 0,攻击者F输出⊥;否则,F进行如下操作:

如果pki和pkj均已被攻陷或均未被攻陷,F运行重签名生成算法和查询重签名密钥生成预言机,然后返回一个签名σi=ReSign(OReKey(pki,pkj),pki,Mi,σi);

如果pki和pkj中有一个已被攻陷,F首先查询签名预言机,然后返回一个签名σj=OSign(pkj,Mi)。

如果h*和的最右边比特值是1,那么攻击者F退出,模拟失败;否则,此时m0=gx,该伪造必须满足:

为解决 CDH实例(g,gα,gβ)∈G31,攻击者F计算:

因此,如果攻击者A能攻破新方案的强不可造性,那么攻击者F能解决G1上的CDH问题。由于A成功伪造签名的概率是ε,模拟不中断的概率是1/4,选择类型Ⅰ的概率都是1/2,所以F成功计算出CDH困难问题实例的概率是ε/8。

(1)建立:设置k=k*,运行Setup算法得到系统其他参数,将(G1,G2,p,e,g,pk*,g2,v,m0,m1,k,Hk)发送给攻击者A,并秘密保存私钥sk*。

(2)询问:攻击者A可以自适应性地向F询问用户的公钥/私钥、重签名密钥、消息的签名和重签名,F通过运行相应的算法(KeyGen,ReKey,Sign和ReSign)响应攻击者A所发起的各种询问请求,并将询问结果返回给A。

3.4 有效性分析

文献［2］提出的Smd方案、文献［3］提出的Smd改进方案和文献［12］提出的2个代理重签名方案都是基于Waters签名方案［11］,需要将任意长度的待签名消息映射为一个固定长度n的比特串。下面将已有的几种双向代理重签名方案和本文方案进行效率和安全属性比较,如表1所示。假设所有方案选择相同长度的大素数p和循环群(G1,G2),其中,|·|表示元素长度;E表示指数运算;P表示双线性对运算;n表示Waters签名方案中的签名消息长度;Y表示具有此种属性;N表示不具有此种属性。

表1 效率和安全属性比较

从表1可以看出,本文所提出的双向代理重签名方案的重签名比Smd方案［2］、Smd改进方案［3］的重签名多一个元素,但这2个方案不满足强不可伪造性,并且具有较长的系统公开参数长度。文献［12］提出的2个方案(Vivek1方案、Vivek2方案)满足强不可伪造性,但与这2个方案相比,本文新方案具有更短的系统公开参数长度和重签名长度,并且重签名验证的计算量更小,同时满足密钥最优性。

4 结束语

本文提出一个双向代理重签名方案,并证明了该方案在适应性选择消息攻击下是强不可伪造的。与已有的强不可伪造双向代理重签名方案相比,该方案在系统公开参数长度、签名长度、安全属性等方面具有较大的性能优势。下一步工作将设计无双线性对的强不可伪造代理重签名方案。

［1］ Ateniese G,Hohenberger S.Proxy Re-signatures:New Definitions,Algorithms, and Applications［C］// Proceedings of ACM CCS'05.Alexandria,USA:ACM Press,2005:310-319.

［2］ Shao Jun,Cao Zhenfu,Wang Licheng,et al.Proxy ResignatureSchemesWithoutRandom Oracles［C］// Proceedings of INDO-CRYPT'07.Chennai,India:［s.n.］, 2007:197-209.

［3］ Kiate K,Ikkwon Y,Secogan L.Remark on Shao et al's Bidirectional Proxy Re-signature Scheme in Indocrypt'07［J］.International Journal of Network Security,2009,8(3): 308-311.

［4］ Benoit L,Damien V.Multi-use Unidirectional Proxy Resignatures［C］//Proceedings of the 15th ACM Conference on Computer and Communications Security.Alexandria, USA:ACM Press,2008:511-520.

［5］ 邓宇乔,杜明辉,尤再来,等.一种基于标准模型的盲代理重签名方案［J］.电子与信息学报,2010,32(5): 1119-1223.

［6］ 孙昌毅,李益发,斯雪明.基于多变量公钥密码体制的代理重签名方案［J］.计算机工程,2012,38(17): 116-118.

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

［8］ 杨小东,王彩芬.前向安全的单向门限代理重签名［J］.计算机应用,2011,31(3):801-804.

［9］ Buchmann J,Dahmen E,Ereth S,et al.On the Security of the Winternitz One-time Signature Scheme［J］.International Journal of Applied Cryptography,2013,3(1):84-96.

［10］ 刘振华,胡予濮,张襄松.标准模型下高效的强不可伪造短签名方案［J］.江苏大学学报:自然科学版,2013, 34(3):309-313.

［11］ Waters B.Efficient Identity-based Encryption Without Random Oracles［C］//Proceedings of EuroCrypt'05.Aarhus,Danmark:［s.n.］,2005:114-127.

［12］ Vivek S S,Selvi S S D,Rangan C P,et al.Strongly Unforgeable Proxy Re-signature Schemes in the Standard Model［EB/OL］.［2013-12-25］.http://eprint.iacr.org/ 2012/080.pdf.

［13］ Matsuda T,Attrapadung N,Hanaoka G,et al.A CDH-based Strongly Unforgeable Signature Without Collision Resistant Hash Function［C］//Proceedings of Prov Sec'07.Wollongong,Australia:［s.n.］,2007:68-84.

编辑 金胡考

A Strongly Unforgeable Proxy Re-signature Scheme

YANG Xiaodong,LI Chunmei,ZHOU Si'an,WANG Caifen
(College of Computer Science&Engineering,Northwest Normal University,Lanzhou 730070,China)

Most existing proxy re-signature schemes are existential unforgeability,where an adversary will be able to forge a signature on a new message rather than on a message that has already been signed.However,strong unforgeability can protect the existing message-signature pairs from being forged.By using TCR hash function,a bidirectional proxy resignature scheme is proposed.Based on collision-resistant Target Collision Resistant(TCR) hash function and computational Diffie-Hellman assumption,the proposed scheme is proved to be strongly unforgeable under adaptive chosen message attacks.The results show that the proposed scheme in computational efficiency is superior to the available proxy re-signature schemes with strong unforgeability.Compared with these schemes,the new scheme has short system parameters,short signature,short re-signature and more security properties.

bidirectional proxy re-signature;strong unforgeability;provable security;Computational Diffie-Hellman (CDH)assumption;standard model

1000-3428(2014)11-0130-05

A

TP309.7

10.3969/j.issn.1000-3428.2014.11.026

国家自然科学基金资助项目(61262057,61163038);甘肃省科技计划基金资助项目(145RJDA325);国家档案局科技计划基金资助项目(2014-X-33);甘肃省自然科学基金资助项目(1308RJYA039);兰州市科技计划基金资助项目(2013-4-22)。

杨小东(1981-),男,副教授、博士,主研方向:现代密码学,云计算安全;李春梅、周思安,硕士研究生;王彩芬,教授、博士生导师。

2013-12-16

2014-02-20E-mail:y200888@163.com

中文引用格式:杨小东,李春梅,周思安,等.一种强不可伪造代理重签名方案［J］.计算机工程,2014,40(11):130-134.

英文引用格式:Yang Xiaodong,Li Chunmei,Zhou Si'an,et al.A Strongly Unforgeable Proxy Re-signature Scheme［J］.Computer Engineering,2014,40(11):130-134.