一类无证书签名方案的构造方法

第32卷 第5期2009年5月计 算 机 学 报CH INESE JOURNA L OF COMPU TERSVol.32No.5May 2009收稿日期:2008201220;最终修改稿收到日期:2008212222.本课题得到国家自然科学基金(60673070)和江苏省自然基金(B K2006217)资助.张 磊,男,1982年生,博士研究生,主要研究方向为密码学与信息安全.张福泰,男,1965年生,教授,博士生导师,研究领域包括信息安全、网络安全、密码学.E 2mail:zhan gfutai@.一类无证书签名方案的构造方法张 磊 张福泰(南京师范大学数学与计算机科学学院 南京 210097)摘 要 无证书密码体制(CL 2PKC)是一类新型公钥密码体制.它保持了基于身份的密码体制(ID 2PKC)不需要使用公钥证书的优点,又较好地解决了基于身份的公钥体制所固有的密钥托管问题.对无证书体制下安全高效的签名方案的设计方法的研究是受到高度关注的研究课题.文中给出了一类无证书签名方案的构造方法,并在一个很强的安全模型下对用该方法所构造的方案的安全性进行了证明.文中对新构造的方案与已有的一些同类方案的性能进行了比较.结果显示新方案在整体性能上有一定的优势.关键词 无证书密码系统;计算Diffie 2Hellman 问题;双线性对;无证书签名;随机预言模型中图法分类号TP 309 DOI 号:10.3724/SP.J.1016.2009.00940A Method to Construct a Class of Certificateless Signature SchemesZH ANG Lei ZH ANG Fu 2Tai(Colleg e of Mathematics and Comp uter Science,N anjing N ormal University ,N anjing 210097)Abstr act Certificateless public key cryptogr aphy (CL 2PKC)is a new paradigm in public key cryptography.It effectively solves the inherent key escr ow problem in identity based public key cryptography (ID 2PKC)while keeps its certificate free property.Designing efficient and secure signature schemes in cer tificateless public key setting is an interesting research topic that attracts the attentions of many resear cher s.T his paper proposes a new method to construct a class of cer 2tificateless signature schemes.The schemes constructed using the new method can be proven se 2cur e in a very str ong security model.The overall performances of the authors .newly constructed schemes are better than that of the other certificateless signature schemes available in the literature.Keywor dscertificateless public key cryptography;computational Diffie 2H ellman pr oblem;bilinear pairing;certificateless signature;random oracle model1 引 言在基于证书的传统公钥密码系统下,为了保证系统的安全性,用户的公钥由CA 颁发的证书进行认证.然而在实际应用中证书的产生、管理、传输、验证等过程不仅复杂而且代价很高.为了简化证书管理过程,降低运行代价,Shamir [1]在1984年首次提出了基于身份的密码系统.在基于身份的密码系统中不再使用证书来认证用户的公钥,因为用户的公钥就是能唯一代表他身份的一个公开信息,比如说他的电话号码或者email 地址.在该系统中,用户的私钥需要由一个可信中心(PKG)产生.正是由于这一点,基于身份的密码系统有一个与生俱来的缺陷,那就是密钥托管问题,即PKG 知道任何用户的私钥.为了解决基于身份的密码系统中的密钥托管问题,Al2Riyami和Paterson[2]在2003年提出了无证书的密码系统.在无证书密码系统中用到一个第三方KGC,其作用是帮助用户生成自己的私钥.但是KGC并不是生成用户的完整私钥,而只是生成用户的部分私钥.用户的完整私钥由用户自己随机选取的一个秘密值以及KGC帮他生成的部分私钥结合起来产生.而用户的公钥由用户自己根据系统参数以及自己的秘密值进行一定运算生成.数字签名是信息安全中的一个重要工具,它提供真实性、不可否认性、数据完整性等安全服务.相对于传统公钥体制和基于身份的公钥体制下的数字签名而言,无证书签名优势在于:(1)签名验证者在验证签名时无需像在传统公钥密码系统下那样验证签名者公钥的有效性;(2)没有基于身份的密码系统中的密钥托管问题.最早的无证书签名由Al2Riyami和Paterson[2]提出,然而他们对该方案没有给出形式化的安全性证明.在A CISP2005会议上,H uang等人[3]指出了其中的缺陷,那就是第1类攻击者可以任意伪造签名.另外,H uang等人提出了一个修改方案并定义了无证书签名的安全模型.但该模型并不能完全捕获到第1类攻击者的行为,一个典型的例子就是Yap等人的方案[4].该方案在文献[3]中的模型下被证明是安全的,但事实上,对它的各种各样的攻击陆续被提出[526].同时我们看到,现有文献中有不少无证书签名方案[729]的安全性是在这个模型下证明的,因而这些方案的真正安全性还有待于探讨.在文献[10]中Zhang等人给出了一个改进的安全模型,并给出了一个高效的签名方案.文献[11]进一步提出了无证书签名的一个更强的安全模型.本文研究在目前提出的最强的安全模型下,高效无证书签名方案的设计.我们提出了一类无证书签名方案的构造方法.在这种构造方法下,所得的签名方案结构简捷运行高效,并在一定意义下性能优于现有的其它无证书签名方案.我们的构造基于双线性映射.其安全性基于一个经典的困难问题)))计算Diffie2H ellman问题.同时,我们在随机预言模型下[12],利用文献[11]中的安全模型对所构造的签名方案的安全性进行了证明.2预备2.1双线性映射及数学困难问题假设G1是一个阶为素数q的加法群,P是它的一个生成元;G2是一个阶为q的乘法群.若一个映射e:G1@G1y G2满足以下3条性质,则我们称这个映射为双线性映射.(1)双线性性.对于任何U,V I G1;a,b I Z*q, e(a U,bV)=e(U,V)ab.(2)非退化性.存在U,V I G1使得e(U,V)X1.(3)可计算性.对于任何的U,V I G1,存在一个高效的算法来计算e(U,V)的值.定义1.离散对数问题:给定一个阶为q的循环群G,它的一个生成元g以及h I G*,找到一个值a I Z*q使得h=g a.定义2.计算Diffie2H ellman(CDH)问题.给定一个阶为q的循环群G,它的一个生成元g以及g a,g b I G*1(其中a,b I Z*q且其值未知),计算g ab.2.2无证书签名方案一个无证书签名方案由系统参数生成、部分密钥生成、设置秘密值、设置私钥、设置公钥、签名以及验证7个算法组成.通常,前两个算法由KGC执行,而其它算法由签名或验证用户执行.以下是各个算法的描述.系统参数生成:输入安全参数k,输出系统主密钥ma ster2key和系统公开参数p ar ams.其中系统公开参数pa ra ms向系统中的全体用户公开,而主密钥master2key则由KGC秘密保存.部分密钥生成:输入系统参数p ar ams、一个用户的身份I D和系统主密钥ma ster2key,KGC为用户输出部分私钥D I D.设置秘密值:输入系统参数par ams和用户身份I D、输出该用户的秘密值x ID.设置私钥:输入系统参数pa ra ms、一个用户的身份I D、该用户的秘密值x I D和部分私钥D ID,输出该用户的私钥S I D.设置公钥:输入系统参数pa ra ms、一个用户的身份I D、秘密值x I D和部分私钥D I D,输出该用户的公钥P I D.签名:输入系统参数p ar ams、消息M、一个用户的身份I D、其公钥P ID及私钥S I D,输出该用户对消息M的签名R.验证:输入系统参数p ar ams、一个消息M、一个签名R、签名者的身份I D及公钥P I D,当检验签名有效时,输出1;否则,输出0.2.3安全模型在无证书系统中有两类攻击者,即第1类攻击者A I与第2类攻击者A II.第1类攻击者不知道系统主密钥,但是可以任意替换用户的公钥.第2类攻击者知道系统的主密钥,但是不能替换目标用户的9415期张磊等:一类无证书签名方案的构造方法公钥.无证书签名方案的安全性可用下面的挑战者C和攻击者A I或A I I间的两个游戏[11]来定义.游戏1(适用于第1类攻击者):初始化:C运行系统参数生成算法,输入安全参数k,输出系统主密钥ma ster2key和系统参数pa ra ms.C将pa2 r ams发送给A I,而对主密钥ma ster2key严格保密.攻击:A I可以适应性地进行公钥询问、部份私钥询问、秘密值询问、公钥替换询问以及签名询问,C模拟签名方案中的相应算法分别做出回答.伪造:最后A I输出一个四元组(M*,R*,I D*,P*).我们说A I赢得了这个游戏,当且仅当:1.R*是公钥为P*、身份为I D*的用户对消息M*的一个有效签名.2.A I没有询问过身份为I D*的用户的部分私钥.3.A I没有询问过身份为I D*、公钥为P*的用户对M*的签名.游戏2(适用于第2类攻击者).初始化:C运行系统参数生成算法,输出系统主密钥ma ster2key和系统参数p ar a ms.C将ma ster2key和pa r ams 发送给A I I.攻击:A II可以适应性地进行公钥询问、秘密值询问、公钥替换询问以及签名询问,C模拟签名方案中的相应算法分别做出回答.伪造:最后A II输出一个四元组(M*,R*,I D*,P*).我们说A I I赢得了这个游戏,当且仅当:1.R*是公钥为P*,身份为I D*的用户对消息M*的一个有效签名.2.A II没有询问过身份为I D*的用户的秘密值且A II没有替换用户I D*的公钥.3.A II没有询问过身份为I D*、公钥为P*的用户对M*的签名.定义3.一个无证书签名方案在适应性选择消息攻击下是存在不可伪造的,当且仅当,任何计算能力多项式受限的攻击者赢得以上两个游戏的概率是可忽略的.在下文中,我们说一个签名方案是安全的,即指它在适应性选择消息攻击下是存在不可伪造的.3一类无证书签名方案的构造方法系统参数生成:输入一个安全参数k,KGC选定满足211节所述性质的e,G1,G2,P,并在Z*q中随机选取系统主密钥master2key=s,记P0=sP,选择H ash函数H1,H2:{0,1}*y G1,H3:{0,1}*y Z*q,设置系统参数par ams={e,G1,G2,P,P0,H1, H2,H3}.部分私钥生成:KGC利用系统主密钥帮用户生成部分私钥.当输入一个用户的身份ID,KGC 计算并输出该用户的部分私钥D I D=sH1(I D).设置秘密值:用户(其身份为I D)在Z*q中随机选取一个值x作为其秘密值.设置公钥:秘密值为x的用户(其身份为I D)设置其公钥为P I D=xP.设置私钥:身份为I D的用户设置其私钥为S ID=x U+D I D,其中U=H2(I D,P I D),x为该用户的秘密值,D I D为其部分私钥,P I D为其公钥.签名:假设签名者的身份为ID,公钥为P I D= xP,私钥为S ID=x U+D I D.当输入一个消息M,该签名者按以下方式对消息M进行签名:1.选取r I Z*q,计算R=e(X,P)r.其中X I G1是一个可以公开计算的值(我们可以令X=P,P0,H1(I D)等).2.计算h=H3(M,I D,R,P ID),V=r X+hS ID.3.输出签名R=(h,V).验证:验证者按如下方式验证身份为I D,公钥为P I D的用户对消息M的签名R的有效性:1.计算U=H2(I D,P I D),Q ID=H1(I D),R=e(V,P) (e(U,P ID)e(Q I D,P0))-h.2.检验等式h=?H3(M,I D,R,P I D)是否成立.若成立,则输出1;否则输出0.4安全性证明定理1.在随机预言模型下,若群G1中的CDH问题是困难的,那么用上述方法构造的无证书签名方案对于第1类攻击者是安全的.证明.假设C想解决G1中的CDH问题,其输入为(aP,bP),他需要计算出a bP.假设A I是第1类攻击者,他能以不可忽略的概率攻破我们的签名方案.我们看C如何利用A I来解决CDH问题.首先,C设置P0=aP,选择系统参数p ar ams= {e,G1,G2,P,P0,H1,H2,H3}.然后C将系统参数给A I.这里我们将H ash函数H1,H2,H3看成随机预言机.并且为了简单起见,我们假设以下A I的询问都是不同的.H1询问:C维护一个列表H list1,开始时,该列表被初始化为一个空表,其每一项的格式为(I D,A, Q I D,D ID).假设A I最多能做q H1次H1询问,C在[1,q H1]中随机选取一个值J.当C收到A I对H1(I D i)的询问时,若这不是第J次询问,C随机选择A i I Z*q,计算Q i=A i P,D i=A i P0,将(I D i,A i,Q i, D i)加入到H list1并将Q i返回给A I;否则,C设置A J= D J=L,Q J=bP,将(I D J,A J,Q J,D J)加入到H list1942计算机学报2009年并将Q J返回给A I.H2询问:C维护一个列表H list2,其每一项的格式为(I D,P I D,B,U).最初,该列表是空的.当A I询问H2(I D i,P i)时,C随机选择B i I Z*q,计算U i= B i P,将(I D i,P i,B i,U i)加入到H list2并将U i返回给A I.H3询问:C维护一个列表H list3,其格式为(M, I D,R,P I D,h).最初,这个列表被初始化为一个空表.当A I询问H3(M i,I D i,R i,P i)时,C随机选择h i I Z*q,将(M i,I D i,R i,P i,h i)加入到H list3并将h i返回给A I.部分私钥询问:若I D i=I D J,C终止;否则检索H list1找到(I D i,A i,Q i,D i)这一项,将D i返回给A I,当H1(I D i)没有询问过时,C首先做H1(I D i)操作.公钥询问:C维护一个列表K list,其每一项的格式为(I D,x,P I D).这个列表起初是空的.当C接收到A I对身份I D i的公钥询问时,C首先检索K list.若K list中有一项(I D i,x i,P i),则C返回P i作为回答;否则,C随机选择x i I Z*q,计算P i=x i P,返回P i作为回答并将(I D i,x i,P i)加入到K list.公钥替换询问:当C接收到A I的一个关于身份为I D i的用户的公钥替换询问(I D i,P c i)时,C检索K list找到(I D i,x i,P i)并设置x i=L,P i=P c i.秘密值询问:当C接收到A I对身份为I D i的用户的秘密值询问时,C检索K list找到(I D i,x i,P i).若x i=L,表明关于身份I D i的公钥已经被替换,因此C无法正确回答A I的秘密值询问,C只能返回L;否则C返回x i.签名询问:当A I向C请求身份为I D i,公钥为P i的用户对一个消息M i的签名时,C按照如下步骤回答:1.随机选择h i I Z*q,V i I G1.2.计算R i=e(V i,P)(e(U i,P i)e(Q i,P0))-h i,其中U i=H2(I D i,P i),Q i=H1(I D i).3.设置H3(M i,I D i,R i,P i)=h i.4.返回(h i,V i).最后,A I输出一个伪造(M*,R*=(h,V),I D*, P*).若I D*X I D J,C终止;否则,根据For king Lemma[13],C选择不同的H ash函数H c3并再次利用A I的能力,它可以得到另一个伪造(M*,R*c= (h c,V c),ID*,P*).从而C得到了两个有效的伪造,并且它们满足R=e(V,P)(e(U,P*)e(Q,P0))-h与R=e(V c,P)(e(U,P*)e(Q,P0))-h c.其中U= H2(I D*,P*)=B P,并以(I D*,P*,B,U)的形式存在于H list2中,Q=H1(I D*)=bP.这样就有e(V,P)(e(U,P*)e(Q,P0))-h= e(V c,P)(e(U,P*)e(Q,P0))-h c.因此,C可以计算出CDH问题的解abP=(h-h c)-1(V-V c)-B P*.证毕.定理2.在随机预言模型下,若群G1中的CDH问题是困难的,那么我们的无证书签名方案对于第2类攻击者是安全的.证明.假设C是一个CDH困难问题的解决者,其困难问题的输入为(a P,bP),他的目标是计算a bP.假设A I I是第2类攻击者,他能攻破我们的签名方案.以下我们看C如何利用A II来解决CDH 问题.首先,C选择系统主密钥s I Z*q,计算P0=sP,选择系统参数pa ra ms={e,G1,G2,P,P0,H1,H2, H3}.然后C将系统参数与主密钥给A I I.这里我们将H ash函数H2,H3看成随机预言机.并且为了简单起见,我们假设以下A I I的询问都是不同的.公钥询问:C维护一个列表K list,其每一项的格式为(I D,x,P ID).这个列表被初始化为一个空表.假设A II最多能做q K次公钥询问,C在[1,q K]中随机选取一个值J.当C接收到A I I的一个关于身份为I D i的用户的公钥询问时,C首先检索K list.若K list 中有一项(I D i,x i,P i),则C返回P i作为回答;否则,若I D i X I D J,C随机选择x i I Z*q,设置P i= x i P;而当I D i=I D J时,设置x i=L,P i=aP.最后, C返回P i作为回答并将(I D i,x i,P i)加入到K list.H2询问:C维护一个列表H list2,其格式为(I D, P ID,B,U).该列表起初是空的.当C收到A II对H2(I D i,P i)的询问时,C首先判定I D i是否等于I D J.若I D i X I D J,C随机选择B i I Z*q,计算U i= B i P;否则设置B i=L,U i=bP.最后C将(I D i,P i, B i,U i)加入到H list2并将U i返回给A I I.H3询问:C维护一个列表H list3,其格式为(M, I D,R,P I D,h).这个列表被初始化为一个空表.当A I I询问H3(M i,I D i,R i,P i)时,C随机选择h i I Z*q,将(M i,I D i,R i,P i,h i)加入到H list3并将h i返回给A I I.秘密值询问:当C接收到A II的关于身份为I D i 的用户的秘密值询问时,若I D i=I D J,C终止;否则,C首先生成该用户的公钥,然后检索K list找到(I D i,x i,P i).若x i=L,表明关于身份I D i的公钥已经被替换,因此C无法正确回答A I I的秘密值询问,C返回L;否则C返回x i.公钥替换询问:当C接收到A I I的一个关于身份为I D i的用户的公钥替换询问(I D i,P c i)时,若I D i=I D J,C终止;否则,C检索K list找到(I D i,x i,9435期张磊等:一类无证书签名方案的构造方法P i)并设置x i=L,P i=P c i.签名询问:当A I I向C请求身份为I D i,公钥为P i的用户对消息M i在的签名时,C按照如下步骤回答该询问:1.随机选择h i I Z*q,V i I G1.2.计算R i=e(V i,P)(e(U i,P i)e(Q i,P0))-h i,其中U i=H2(I D i,P i),Q i=H1(I D i).3.设置H3(M i,I D i,R i,P i)=h i.4.返回(h i,V i).最后,A II输出一个伪造(M*,R*=(h,V),I D*, P*).若I D*X I D J,C终止;否则,根据For king Lemma,C选择不同的H ash函数H c3并再次利用A I I的能力,它可以得到另一个伪造(M*,R*c= (h c,V c),ID*,P*).从而C得到了两个有效的伪造,并且它们满足R=e(V,P)(e(U,P*)e(Q,P0))-h与R=e(V c,P)(e(U,P*)e(Q,P0))-h c.其中P*=aP, U=H2(I D*,P*)=bP,并以(I D*,P*,L,bP)的形式存在于H list2中.于是就有等式e(V,P)(e(U,P*)e(Q,P0))-h= e(V c,P)(e(U,P*)e(Q,P0))-h c.由我们设置可知, e(V-V c,P)(e(bP,aP)e(Q,sP))-h=(e(bP,aP)e(Q,sP))-h c,因此,C可以计算出CDH问题的解abP=(h-h c)-1(V-V c)-sQ.证毕.5效率分析及应用下面,我们将在计算和通信效率方面,把用本文的方法所构造的方案与一些目前能在文献[11]中模型下证明是安全的方案以及几个效率比较高,但是安全性未能有效证明的方案进行比较.我们用P表示一个双线性对运算,S表示群G1中的标量乘运算,E表示群G2中的幂运算,H表示一个H ash到群G1的运算.用P1表示G1中的一个点的长度,用P2表示G2中的一个点的长度,用Z1表示Z*q中的一个点的长度.比较结果如表1所示.表1与其它方案的比较方案签名验证(预计算)签名长度公钥长度安全性文献[7]中方案12S2P,2S,1H(2P,2S)2P11P1未知文献[7]中方案21S,1E1P,2S,1E(1P,1E)1P1,1P21P1未知文献[10]中方案3S,2H4P,3H(3P,2H)2P11P1安全文献[14]中方案11S,1H3P,1H(2P,1H)1P11P1未知文献[14]中方案23S,1E2P,2S,1E,1H(1P,2S,1E)2Z1,1P11P1安全文献[15]中方案1S,2E1P,1S,2E(1P,2E)2Z1,1P11P2安全本文的方案2S,1E3P,1H(1P,1E)1Z1,1P11P1安全从表1中可以看出,在签名阶段我们的方案未涉及到双线性对计算,并且在效率上与其它方案相差无几.在验证阶段,当不考虑预计算时我们的方案比文献[10]中方案效率高一点,而与文献[14]中方案1效率基本相同.与文献[7,15]中方案及文献[14]中方案2相比虽然效率略低,但我们方案的签名长度是文献[14]中方案2及文献[15]中方案的2/3,与文献[7]中方案比我们的签名方案有较高的安全级别.当考虑预计算时,本文签名方案的验证算法比文献[10,14215]中方案及文献[7]中方案1效率更高,而与文献[7]中方案2相比效率基本相同,但签名长度则相对较短.在有些情况下,我们的方案可以进行预计算.比如验证者若经常接收某个签名者的签名并进行验证,那么他可以预计算Q I D,U,e(U,P I D)e(Q ID,P0)并储存这些值,从而大大减少实际计算代价.此外在安全要求较高,签名长度要求较短的环境中我们的方案也有相对优势.因此,我们的方案可用于带宽受限的Ad H oc网络以及需要频繁传递和验证签名的电子商务和电子政务等领域以提供完整性、真实性和不可否认性等安全服务.6总结我们提出了一类无证书签名方案的构造方法,用这种方法构造的方案的安全性基于计算Diffie2 H ellman问题的困难性.在考虑预计算的情况下,我们的方案效率很高,总共只需计算1个双线性对,明显优于其它现有方案.我们方案的安全性证明是基于文献[11]中的安全模型,它是无证书签名方案的一个很强的安全模型.因此,我们的方案可在适合使用无证书密码体制的场合用以提供真实性、完整性和不可否认性等安全服务.参考文献[1]Sh amir A.Identity based cry ptosy stems and sign atureschem es//Proceedin gs of the Crypto.84.California,U SA,1984:47253944计算机学报2009年[2]Al2Riyami S,Paterson K.Certificateless public key cry ptog2raphy//Proceedin gs of th e Asiacrypt2003.Taipei,China, 2003:4522473[3]Huang X,Susilo W,Mu Y,Zhang F.On the s ecu rity of acertificateless sign ature scheme//Proceedings of the CANS 2005.Xiam en,China,2005:13225[4]Yap W,Heng S,Goi B.An efficient certificateless signaturesch eme//Pr oceedings of the EU C Works hops2006.Seoul, Kor ea,2006:3222331[5]Park J.An attack on the certificateles s sign ature s chemefrom EUC Works hops2006.Cryptology ePrin t Archive,Re2 p ort2006/442,2006[6]Zhang Z,Feng D.Key replacemen t attack on a certificatelesssignatu re sch eme.Cryptology ePrint Archive,Report2006/ 453,2006[7]Choi K,Park J,Hwang J,Lee D.Efficient certificatelesssignatu re schem es//Proceeding s of the ACNS2007.Zhuh ai, China,2007:4432458[8]Castr o R,Dahab R.T wo notes on the s ecu rity of certificate2less s ignatur es//Proceedings of th e ProvSec2007.Wollon2 gong,Australia,2007:852102[9]Zhang J,Mao J.Security analysis of two signature schem esand their improved s chem es//Proceedin gs of th e ICCSA2007.Kuala Lumpur,Malaysia,2007:5892602[10]Zhan g Z,Wong D,Xu J,Feng D.Certificateless public2keysign ature:security model and efficient cons truction//Pro2ceedings of th e ACNS2006.Sin gapore,2006:2932308 [11]H u B,Won g D,Zhang Z,Deng X.Key replacement attackagain st a generic construction of certificateles s sign ature//Proceedings of the ACISP2006.Melbourne,Australia,2006:2352346[12]Bellare M,Rogaway P.Ran dom oracles are practical:A par2adigm for des igning efficient protocols//Proceedings of theCCCS.93.Virginia,USA,1993:62273[13]Pointcheval D,Stern J.Security proofs for sign atureschem es//Proceedin gs of the EU ROCRYPT.96.Saragossa,Spain,1996:3872398[14]H uang X,Mu Y,Susilo W,Wong D,Wu W.Certificateles ssign ature revisited//Proceedin gs of the ACISP2007.T owns2ville,Au stralia,2007:3082322[15]Zhan g L,Zhang F,Zh ang F.New efficient certificateles ssign ature sch eme//Proceedings of the EU C Worksh ops2007.Taipei,Chin a,2007:6922703ZHANG Lei,bor n in1982,Ph.D.candidate.H is r esear ch interests includecrypt ography and information security.ZHANG Fu2Ta i,born in1965,professor,Ph.D.super2visor.His r esear ch interests include infor mat ion security,network secur ity and cryptogr aphy.Backgr oundThis paper invest igat es efficient const ruct ions of signa2tur e schemes in Cer tificateless public key setting.Digital sig2nature is one of the most important pr imit ives in public keycr yptogr aphy.It provides authenticity,integrity and non2re2pudiat ion to many kinds of applications.In tr aditional publickey cryptosystems,the management of certificates is usuallycomplex and costly.Shamir introduced I dentity2based publickey cr yptogra phy to r emove this requirement.H owever,keyescr ow pr oblem is inherent in Identity2based public key cr yp2togr aphy.Certif icateless public key cryptogr aphy is a newpar adigm which was fir st intr oduced by Al2R iyami and P ater2son in2003.Their ma in pur pose is to solve t he key escr owpr oblem in Ident ity2based public key cryptogr aphy,whilekeeping the implicit cer tification proper ty of Identity2basedpublic key cr yptography.Recently,a number of cert ificateless signature schemeshave been pr esented.The first one was presented by Al2Riy2ami and P aterson without formal secur ity ter,Huang et al.pointed out a secur ity dr awback of this schemeand proposed a secure one.They also defined the secur itymodel of certif icateless signat ur e schemes.An impr oved se2curity model was presented by Zhang et al.and an evenst ronger one was put forward by H u et al.With respect tothe efficiency,most of the previous secur e CLS schemes in2volve a relatively large amount of paring computation and ex2ponentiation in t he process of signing and verification.In t his paper,the author s show a new method to con2str uct a class of cer tificateless signature schemes.This kindof schemes can be proven secur e in a ver y strong secur itymodel.In addition,the constructed schemes have a betterover all perfor mance when compar ed with some other prov2ably secur e cer tificateless signat ur e schemes ava ilable.Theresearch is support ed by the National Natural Science Foun2dation of China(No160673070)and the Natural ScienceFoundat ion of Jiangsu P rovince(No1BK2006217).The pr o2ject s focus on the study of secure and efficient encryptionschemes,signatur e schemes and key agreement pr otocols incer tificateless setting.945 5期张磊等:一类无证书签名方案的构造方法。