强不可伪造的双向代理重签名方案

冯 婕,蓝才会,,郏伯荣,杨小东

(1.兰州城市学院信息工程学院,兰州730070;2.西北师范大学计算机科学与工程学院,兰州730070)

强不可伪造的双向代理重签名方案

冯 婕1,蓝才会1,2,郏伯荣1,杨小东2

(1.兰州城市学院信息工程学院,兰州730070;2.西北师范大学计算机科学与工程学院,兰州730070)

在代理重签名中,一个拥有重签名密钥的半可信代理者可以把受托者的签名转换为委托者对同一消息的签名(即重签名),但该代理者不能单独生成受托者或委托者的签名。标准模型下的代理重签名方案多数是存在不可伪造性的,无法阻止敌手对已经签名过的消息重新伪造一个合法的签名。为此,利用基于密钥的目标抗碰撞杂凑函数,提出一种新的双向代理重签名方案。在计算Diffie-Hellman困难问题的假设下,证明该方案在适应性选择消息攻击下是强不可伪造的。分析结果表明,与已有强不可伪造的双向代理重签名方案相比,该方案的系统参数和重签名的长度短,且重签名的计算量小。

双向代理重签名;强不可伪造性;存在不可伪造性;标准模型;系统参数;目标抗碰撞杂凑函数

1 概述

代理重签名具有转换签名的功能,在跨域身份认证、验证网络路径和构造审查系统等方面有广泛的应用前景［1-3］。代理重签名是近年来密码学领域的一个热点研究方向,研究者先后提出了一系列代理重签名方案［4-7］。然而,在标准模型下的多数代理重签名方案［8-10］满足存在不可伪造性,即要求敌手不能对一个新的消息产生一个的合法签名。强不可伪造性具有更强的安全性［11-13］,保证敌手不仅无法伪造新的消息的签名,也不能伪造已经签名的消息的合法签名,可有效防止电子投票、电子现金和数字版权等的篡改。

具有强不可伪造性的代理重签名的研究刚刚起

步,公开的相关文献较少。2012年,Vivek等人［14］提出了2个具有强不可伪造性的双向代理重签名方案(下文简称Vivek1方案和Vivek2方案),但这2个方案具有大量的系统公开参数,对存储空间的要求比较高。本文利用较弱的基于密钥的目标抗碰撞(Target Collision Resistant,TCR)杂凑函数［15］,提出了一个强不可伪造的双向代理重签名方案。

2 预备知识

假设M1和M2分别为TCR杂凑函数的输入和输出消息空间,K为密钥空间,其中,k∈K,利用下面的游戏定义一个TCR杂凑函数Hk:K×M1→M2的安全性:敌手首先输出消息m1∈M1;挑战者然后随机选取k∈K,并将k发送给敌手;最后敌手输出消息m2∈M1。如果Hk(m1)=Hk(m2)且m1≠m2,则敌手赢得游戏。

定义如果敌手在多项式时间t内赢得上述游戏的概率ε是可忽略的,那么称TCR杂凑函数Hk是(t,ε)安全的［15］。

3 改进的强不可伪造双向代理重签名方案

3.1 方案描述

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

(1)系统参数生成算法(Setup):根据群(G1,G2)的定义,在G1中随机选取4个元素g2,v,m0和m1;K为TCR杂凑函数的密钥空间,选取一个TCR杂凑函数Hk:{0,1}∗→Zp,其中,k∈K;公开系统参数cp=(G1,G2,p,e,g,g2,v,m0,m1,k,Hk)。

(3)重签名密钥生成算法(ReKey):利用受托者的私钥skA=α和委托者的私钥skB=β,为代理者生成重签名密钥rkA→B的过程如下:

(4)签名生成算法(Sign):对于待签名的消息M,签名者首先随机选取,然后计算σ1=gs和h=Hk(M‖σ1),并检查h的最右边比特值u∈{0, 1};利用私钥sk=α计算,最后输出消息M的签名。

(5)重签名生成算法(ReKey):输入一个重签名密钥rkA→B,一个消息M,一个公钥pkA和一个签名σA=(σA1,σA2),首先验证σA的合法性,如果Verify (pkA,M,σA)=0,输出⊥;否则,输出对应于公钥pkB的消息M的签名σB=(σB1,σB2,σB3)=(σA1,rkA→B·σA2·(mu2vh2)r,gr),其中r∈Z∗p,h2=Hk(M‖σB3),u2是h2的最右边比特值。

(6)签名验证算法(Verify):该算法分签名和重签名2种情形:

1)对于公钥pk,消息M和签名σ=(σ1,σ2),首先计算h=Hk(M‖σ1),检查h的最右边比特值u∈{0,1};然后验证e(σ2,g)=e(σ1,muvh)e(pk,g2)是否成立,如果成立,输出1;否则,输出0。

2)对于公钥pk和消息M的重签名σ=(σ1,σ2,σ3),首先计算h=Hk(M‖σ1)和h2=Hk(M‖σ3),检查h和h2的最右边比特值u,u2∈{0,1};验证e(σ2,g)=e(σ1,muvh)e(pk,g2)e(σ3,mu2vh2)是否成立,如果成立,输出1;否则,输出0。

3.2 正确性分析

案中重签名的强不可伪造性。

3.3 安全性分析

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

假设Mi是第i次询问签名和重签名预言机的输入,预言机返回相应的签名(Mi,σi=(σi1,σi2))和重签名(Mi,σi=(σi1,σi2,σi3)),令q=qS+qRS,hi=Hk(Mi‖σi1),hi2=Hk(Mi‖σi3),i=1,2,…,q。A输出消息的伪造为(M∗,σ∗=,令。将的伪造分成2类:

类型1:h∗≠hi,i=1,2,…,q;

类型2:h∗=hi,存在i∈{1,2,…,q}。

建立:令g1=gα,g2=gβ,随机选取4个元素x,,计算m0=gx,m1=gt2gy和v=gz,运行Setup算法得到系统其他参数,并将(g,g1,g2,v,m0,m1,k)发送给敌手。

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

于是有:

(4)重签名预言机OReSign:敌手输入2个公钥(pki,pkj),一个消息Mi和一个签名σi,如果Verify (pki,Mx,σi)=0,敌手输出⊥;否则,进行如下操作:如果pki和pkj中有一个已被攻陷,返回一个重签名σj=OSign(pkj,Mi);如果pki和pkj均已被攻陷或均未被攻陷,运行重签名生成算法和查询重签名密钥生成预言机,然后返回一个重签名σj=ReSign (ReKey(pki,pkj),pki,Mi,σi);

建立:令k=k∗,运行Setup算法得到系统其他参数,将(G1,G2,p,e,g,pk∗,g2,v,m0,m1,k,Hk)发送给敌手。

3.4 有效性分析

下面将已有的一些双向代理重签名方案和本文提出的方案进行效率和安全属性比较,其结果见表1。假定所有方案选择相同长度的大素数p,其中,|·|表示元素长度;E表示指数运算;P表示双线性对运算;n表示Waters签名方案［16］中的签名消息长度;Y表示具有此种属性;N表示不具有此种属性。

表1 签名方案的效率和安全属性比较

从表1可以看出,Smd方案［5］和Smd改进方案［6］不满足强不可伪造性,并且具有较长的系统公开参数长度。文献［14］提出的2个方案满足强不可伪造性,但与这2个方案相比,本文方案具有更短的系统公开参数长度和重签名长度,并且重签名验证的计算量更小,同时满足密钥最优性。

4 结束语

为了提高代理重签名方案的安全性能,基于目标抗碰撞杂凑函数和CDH困难问题假设,本文提出一个强不可伪造的双向代理重签名方案,并在标准模型下给出了新方案的安全性证明。分析结果表明,与已有的强不可伪造双向代理重签名方案相比,新方案在系统公开参数长度、重签名长度、安全属性等方面具有较大的优势。

［1]Hao Shengang,Li Zhang,Muhammad M.A Union Authentication Protocol of Cross-domain Basedon Bilinear Pairing［J］.Journal of Software,2013,8(5): 1094-1100.

［2]Zhang Longjun,Zhang Jianhe,Xia Ang,et al.Domain AuthenticationProtocolBasedonCertificate Signcryption in Ipv6 Network［C］//Proceedings of International Conference on Information Engineering and Applications.London,UK:Springer,2013:213-220.

［3]Hong Xuan,Long Yu.A Novel Unidirectional Proxy Resignature Scheme and Its Application for MANETs［J］.Journal of Computers,2012,7(7):1796-1800.

［4]Ateniese G,Hohenberger S.Proxy Re-signatures:New Definitions,Algorithms,andApplications［C］// Proceedings of ACM CCS’05.Alexandria,USA:ACM Press,2005:310-319.

［5]Shao J,Cao Z,Wang L,et al.Proxy Re-signature Schemes Without Random Oracles［C］//Proceedings of INDOCRYPT’07.Chennai,India:［s.n.］,2007:197-209.

［6]Kiate K,Ikkwon Y,Secogan L.Remark on Shao et al Bidirectional Proxy Re-signature Scheme in Indocrypt’07［J］.International Journal of Network Security,2009, 8(3):308-311.［7]Benoit L,Damien V.Multi-use Unidirectional Proxy Resignatures［C］//Proceedingsofthe15thACM Conference on Computer and Communications Security.Alexandria,USA:ACM Press,2008:511-520.

［8]Deng Y,Du M,You Z,et al.A Blind Proxy Resignatures Scheme Based on Standard Model［J］.Journal of Electronics&Information Technology,2010,32(5): 1119-1223.

［9]He Defei.A Novel Blind Proxy Re-signature Scheme［J］.Computer Applications and Software,2012,29(3): 294-296.

［10]Rawat S S,Shrivastava G K.Improved Id-based Proxy Re-signcryption Scheme［C］//Proceedingsof 2012 IEEE CICN’12.Mathura,India:［s.n.］,2012:730-733.

［11]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.

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

［13]魏春艳,蔡晓秋.标准模型下的高调无证书短签名方案［J］.计算机工程,2012,38(13):119-121.

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

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

［16]Waters B.Efficient Identity-based Encryption Without Random Oracles［C］//Proceedings of EuroCrypt’05.Aarhus,Danish:［s.n.］,2005:114-127.

编辑 索书志

Bidirectional Proxy Re-signature Scheme with Strong Unforgeability

FENG Jie1,LAN Caihui1,2,JIA Borong1,YANG Xiaodong2
(1.School of Imformation Engineering,Lanzhou City University,Lanzhou 730070,China;
2.College of Computer Science&Engineering,Northwest Normal University,Lanzhou 730070,China)

In a proxy re-signature scheme,a semi-trusted proxy is allowed to transform a signature from a delegatee into a signature from a delegator on the same message using the re-signature key.But the proxy cannot generate signatures for either the delegatee or the delegator.Proxy re-signature schemes in the standard model are existentially unforgeable,which cannot prevent forgeries from forging valid signatures on new messages not previously re-signed.Based on target collision-resistant hash function,a bidirectional proxy re-signature scheme is proposed.Under computational Diffie-Hellman assumption,the proposed proxy re-signature scheme is provably secure against strong forgery under adaptive chosen message attacks.Moreover,the new scheme has some advantages over the available schemes,such as short system parameters,short re-signature and low re-signature computation cost.

bidirectional proxy re-signature;strong unforgeability;existential unforgeability;standard model;system parameter;Target Collision Resistant(TCR)hash function

冯 婕,蓝才会,郏伯荣,等.强不可伪造的双向代理重签名方案［J］.计算机工程,2015,41(3):116-119,124.

英文引用格式:Feng Jie,Lan Caihui,Jia Borong,et al.Bidirectional Proxy Re-signature Scheme with Strong Unforgeability［J］.Computer Engineering,2015,41(3):116-119,124.

1000-3428(2015)03-0116-04

:A

:TP309.7

10.3969/j.issn.1000-3428.2015.03.022

国家自然科学基金资助项目(61262057,61163038,61063041);国家档案局科技计划基金资助项目(2014-X-33);甘肃省自然科学基金资助项目(1308RJYA039);兰州市科技计划基金资助项目(2013-4-22);西北师范大学青年教师科研能力提升计划基金资助项目(NWNU-LKQN-10-22)。

冯 婕(1976-),女,讲师、硕士,主研方向:代理重签名,信息管理系统;蓝才会,副教授、博士;郏伯荣,副教授;杨小东,副教授、博士。

2014-05-13

:2014-07-08E-mail:lzfenjie@163.com