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

一类无证 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 签名 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的构造 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ：无证书密码体制(CL-PKC)是新近提出的一类新型公钥密码体制。它保持了基于身份的 密码体制(ID-PKC)不需要使用公钥证书的优点，又较好地解决了基于身份的公钥体制所固有 的密钥托管问题。对无证书体制下安全高效的签名方案的设计方法的研究是受到高度关注的 研究课题。本文给出了一类无证书签名方案的构造方法，并在一个很强的安全模型下对用该 方法所构造的方案的安全性进行了证明。文中对新构造的方案与已有的一些同类方案的性能 进行了比较。结果显示我们的方案在整体性能上有一定的优势。 ：无证书密码系统；计算Diffie-Hellman问题；双线性对；无证书签名；随机预言模 型 1 在基于证书的传统公钥密码系统下，为了保证系统的安全性，用户的公钥由CA颁发的证书进行认证。 然而在实际应用中证书的产生、管理、传输、验证等过程不仅复杂而且代价很高。为了简化证书管理过程， [1]降低运行代价，Shamir在1984年首次提出了基于身份的密码系统。在基于身份的密码系统中不再使用证 书来认证用户的公钥，因为用户的公钥就是能惟一代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 他身份的一个公开信息，比如说他的电话号码或者 email地址。在该系统中，用户的私钥需要由一个可信中心(PKG)产生。正是由于这一点，基于身份的密码 系统有一个与生俱来的缺陷，那就是密钥托管问题――即PKG知道任何用户的私钥。为了解决基于身份 [2]的密码系统中的密钥托管问题，Al-Riyami和Paterson在2003年提出了无证书的密码系统。在无证书密码系统中用到一个第三方KGC，其作用是帮助用户生成自己的私钥。但是KGC并不是生成用户的完整私钥，而只是生成用户的部分私钥。用户的完整私钥由用户自己随机选取的一个秘密值以及KGC帮他生成的部分私钥结合起来产生。而用户的公钥由用户自己根据系统参数以及自己的秘密值进行一定运算生成。 数字签名是信息安全中的一个重要工具，它提供真实性，不可否认性，数据完整性等安全服务。相对 于传统公钥体制和基于身份的公钥体制下的数字签名而言，无证书签名优势在于：其一，签名验证者在验 证签名时无需像在传统公钥密码系统下那样验证签名者公钥的有效性；其二，没有基于身份的密码系统中 的密钥托管问题。最早的无证书签名由Al-Riyami 和 Paterson[2]提出，然而他们对该方案没有给出形式化 [3]的安全性证明。在ACISP 2005会议上，Huang等人指出了其中的缺陷，那就是第一类攻击者可以任意伪 造签名。另外，Huang等人提出了一个修改方案并定义了无证书签名的安全模型。但该模型并不能完全捕 [4]获到第一类攻击者的行为，一个典型的例子就是Yap等人的方案。该方案在[3]中的模型下被证明是安全 [5,6]的，但事实上，对它的各种各样的攻击陆续被提出。同时我们看到，现有文献中有不少无证书签名方案 [7,8,9]的安全性是在这个模型下证明的，因而这些方案的真正安全性还有待于探讨。在[10]中Zhang等人给出了一个改进的安全模型，并给出了一个高效的签名方案。文献[11]进一步提出了无证书签名的一个更强的安全模型。 本文研究在目前提出的最强的安全模型下，高效无证书签名方案的设计。我们提出了一类无证书签名 方案的构造方法。在这种构造方法下，所得的签名方案结构简捷运行高效，并在一定意义下性能优于现有 的其它无证书签名方案。我们的构造基于双线性映射。其安全性基于一个经典的困难问题--计算Diffie-Hellman问题。同时, 我们在随机预言模型下[12]，利用[11]中的安全模型我们对所构造的签名方案的安全性进行了证明。 1 2 2.1 GG假设是一个阶为素数的加法群，是它的一个生成元；是一个阶为的乘法群。若一个映射Pqq21 eGGG:，,满足以下三条性质，则我们称这个映射为双线性映射。 112ab*1、双线性性：对于任何eaUbVeUV(,)(,),，。 UVGabZ,;,,,1q 2、非退化性：存在UVG,,使得 eUV(, )1,1 3、可计算性：对于任何的UVG,,，存在一个高效的算法来计算的值。 eUV(, )1** 1：离散对数问题：给定一个阶为的循环群，它的一个生成元，以及，找到一个值hG,qgaZ,Gqahg,使得。 ab* 2：计算Diffie-Hellman(CDH)问题：给定一个阶为ggG,,的循环群，它的一个生成元，以及qgG1 ab*g（其中且其值未知），计算。 abZ,,q 2.2 一个无证书签名方案由，，，，，以及 7个算法组成。通常，前两个算法由KGC执行，而其它算法由签名或验证用户执行。以下是各个算 法的描述： 输入安全参数k，输出系统主密钥master-key和系统公开参数params。其中系统公开参数params向系统中的全体用户公开，而主密钥master-key则由KGC秘密保存。 输入系统参数params, 一个用户的身份ID和系统主密钥master-key，KGC为用户输出部分私钥D。 ID 输入系统参数params和用户身份ID，输出该用户的秘密值x。 ID 输入系统参数params，一个用户的身份ID，该用户的秘密值xD和部分私钥，输出该用户IDID 的私钥S。 ID 输入系统参数params，一个用户的身份ID，秘密值xDP和部分私钥，输出该用户的公钥。 IDIDID 输入系统参数params，消息M，一个用户的身份ID，其公钥SP及私钥，输出该用户对消息MIDID 的签名,。 输入系统参数params，一个消息M，一个签名,P，签名者的身份ID及公钥，当检验签名有效ID 时，输出1，否则，输出0。 2.3 AA在无证书系统中有两类攻击者，即第一类攻击者与第二类攻击者。第一类攻击者不知道系统主III 密钥，但是可以任意替换用户的公钥。第二类攻击者知道系统的主密钥，但是不能替换目标用户的公钥。 无证书签名方案的安全性可用下面的挑战者C和攻击者AA或间的两个游戏来定义。 III 1 初始化：C运行算法，输入安全参数k，输出系统主密钥master-key和系统参数params。C将params发送给A，而对主密钥master-key严格保密。 I A攻击：可以适应性地进行询问，询问，询问，替换询问以及询问，C模I 拟签名方案中的相应算法分别做出回答。 2 ****AA (,,,)MIDP,伪造：最后输出一个四元组。我们说赢得了这个游戏，当且仅当： II****1、是公钥为，身份为的用户对消息的一个有效签名。 PIDM, *2、A没有询问过身份为的用户的部分私钥。 IDI***3、A没有询问过身份为，公钥为的用户对的签名。 IDPMI 2 初始化： C运行算法，输出系统主密钥master-key和系统参数params。C将master-key和 params发送给A。 II A攻击：可以适应性地进行询问，询问，询问以及询问，C模拟签名方案中的II 相应算法分别做出回答。 ****A (,,,)MIDP,A伪造：最后输出一个四元组。我们说赢得了这个游戏，当且仅当： IIII****1、是公钥为，身份为的用户对消息的一个有效签名。 PIDM, **2、AA没有询问过身份为的用户的秘密值且没有替换用户的公钥。 IDIDIIII***3、A没有询问过身份为，公钥为的用户对的签名。 IDPMII 3：一个无证书签名方案在适应性选择消息攻击下是存在不可伪造的，当且仅当，任何计算能力多项 式受限的攻击者赢得以上两个游戏的概率是可忽略的。 在下文中，我们说一个签名方案是安全的，即指它在适应性选择消息攻击下是存在不可伪造的。 3 *输入一个安全参数k，KGC选定满足2.1节所述性质的e，G，G，P，并在Z中随机选12q ***取系统主密钥master-key = s，记P= sP，选择哈希函数H, H: {0, 1} ? G，H: {0, 1} ? Z，设置系0 1213q 统参数params = { e, G, G, P, P, H, H, H}。 120123 KGC利用系统主密钥帮用户生成部分私钥。当输入一个用户的身份ID, KGC计算并输出 该用户的部分私钥D = sH (ID)。 ID1 *用户(其身份为ID)在Z中随机选取一个值x作为其秘密值。 q 秘密值为x的用户(其身份为ID)设置其公钥为PxP,。 ID 身份为ID的用户设置其私钥为UHIDP,(,)SxUD,，，其中，x为该用户的秘密值，2IDIDID DP为其部分私钥，为其公钥。 IDID 假设签名者的身份为ID，公钥为PxP,SxUD,，，私钥为。当输入一个消息M，该签名IDIDID 者按以下方式对消息M进行签名： r* 1、选取XG,ReXP,(,)，计算。其中是一个可以公开计算的值（我们可以令rZ,1q XPPHID,,,()等）。 01 2、计算hHMIDRP,(,,,)VrXhS,，，。 3IDID 3、输出签名,,(,)hV。 验证者按如下方式验证身份为ID，公钥为P,的用户对消息M的签名的有效性： ID,h 1、计算ReVPeUPeQP,(,)((,)(,))UHIDP,(,)QHID,()，，。 IDID02IDID1 2、检验等式hHMIDRP?(,,,)是否成立。若成立则输出1，否则输出0。 3ID 3 4. 1 在随机预言模型下，若群G中的CDH问题是困难的，那么用上述方法构造的无证书签名方案对于1 第一类攻击者是安全的。 证明：假设C想解决GA中的CDH问题，其输入为，他需要计算出。假设是第一类攻击(,)aPbPabP1I者，他能以不可忽略的概率攻破我们的签名方案。我们看C如何利用A来解决CDH问题。 I 首先，C设置PaP,A，选择系统参数 params = { e, G, G, P, P, H, H, H}。然后C将系统参数给。1201230I 这里我们将哈希函数HHH,,A看成随机预言机。并且为了简单起见，我们假设以下的询问都是不同123I的。 listH(,,,)IDQD,H询问：C维护一个列表，开始时，该列表被初始化为一个空表，其每一项的 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 为。1IDID1 假设qqAAHID()H最多能做次询问，C在[1,]中随机选取一个值。当C收到对的询问时，若JHHII1i111*list这不是第HQPDP,,,,,(,,,)IDQD,Q次询问，C随机选择，计算，将加入到并将J,,Z1iiii0iiiiiiq listHA(,,,)IDQD,A,,,,DQbP,Q返回给。否则，C设置，，将加入到并将返回给。 1IJJJJIJJJJ listHAH(,,,)IDPU,询问：C维护一个列表，其每一项的格式为。最初，该列表是空的。当询问2I2ID *listHHIDP(,)(,,,)IDPU,AUP,,U时，C随机选择，计算，将加入到并将返回给。 ,,Z22iiiiiiIiiiiq listH(,,,,)MIDRPhAH询问：C维护一个列表，其格式为。最初，这个列表被初始化为一个空表。当3IDI3*listHHMIDRP(,,,)(,,,,)MIDRPhhA询问时，C随机选择，将加入到并将返回给。 hZ,33iiiiiiiiiiIiq list询问：若HDAIDID,(,,,)IDQD,，C终止；否则检索找到这一项，将返回给，当1iIiJiiii HID()HID()没有询问过时，C首先做操作。 1i1i list询问：C维护一个列表(,,)IDxPAK，其每一项的格式为。这个列表起初是空的。当C接收到IDIlistlistID(,,)IDxPPKK对身份的公钥询问时，C首先检索。若中有一项，则C返回作为回答。否则，iiiiilist*C随机选择PxP,(,,)IDxPPK，计算，返回作为回答并将加入到。 xZ,iiiiiiiq 'list询问：当C接收到(,)IDPAIDK的一个关于身份为的用户的公钥替换询问时，C检索找iiIi'到xPP,,,,(,,)IDxP并设置。 iiiiii list询问：当C接收到AID(,,)IDxPx,,K对身份为的用户的秘密值询问时，C检索找到。若，Iiiiii 表明关于身份IDA的公钥已经被替换，因此C无法正确回答的秘密值询问，C只能返回；否则C返,iI 回x。 i 询问当AIDPM向C请求身份为，公钥为的用户对一个消息的签名时，C按照如下步骤回答： Iiii *1、随机选择。 hZVG,,,1iqi ,hi2、计算ReVPeUPeQP,(,)((,)(,))UHIDPQHID,,(,),()，其中。 iiiii0iiiii21 3、设置HMIDRP(,,,)h=。 3iiiii 4、返回(,)hV ii *****最后，IDID,A(,(,),,)MhVIDP,,输出一个伪造。若，C终止。否则，根据Forking JI [13]LemmaAH'，C选择不同的Hash函数并再次利用的能力，它可以得到另一个伪造I3 4 ****(,'(','),,)MhVIDP,,。从而C得到了两个有效的伪造，并且它们满足 *,h*',h**ReVPeUPeQP,(,)((,)(,))ReVPeUPeQP,(',)((,)(,))UHIDPP,,(,),与。其中，并002 ***list以HQHIDbP,,()(,,,)IDPU,的形式存在于中，。 12**',,hh 这样就有eVPeUPeQPeVPeUPeQP(,)((,)(,))(',)((,)(,)),。因此，C可以计算出CDH问00 -1*题的解abPhhVVP,(-')(-')-,。 2在随机预言模型下，若群G中的CDH问题是困难的，那么我们的无证书签名方案对于第二类攻1 击者是安全的。 证明：假设C是一个CDH困难问题的解决者，其困难问题的输入为，他的目标是计算。假(,)aPbPabP设AA是第二类攻击者，他能攻破我们的签名方案。以下我们看C如何利用来解决CDH问题。 IIII*首先，C选择系统主密钥PsP,，计算，选择系统参数 params = { e, G, G, P, P, H, H, H}。sZ,1201230q 然后C将系统参数与主密钥给HH,A。这里我们将哈希函数看成随机预言机。并且为了简单起见，我23II 们假设以下A的询问都是不同的。 II list询问：C维护一个列表(,,)IDxPAK，其每一项的格式为。这个列表被初始化为一个空表。假设IDII IDqqA最多能做次公钥询问，C在[1,]中随机选取一个值。当C接收到的一个关于身份为的用户JiKKIIlisttsil的公钥询问时，C首先检索(,,)IDxPPIDID,KK。若中有一项，则C返回作为回答。否则，若，iiiiiJ*C随机选择PxP,x,,IDID,PaP,P，设置；而当时，设置，。最后，C返回作为回xZ,iiiiJiiiqlist答并将(,,)IDxPK加入到。 iii listHHIDP(,)H(,,,)IDPU,A询问：C维护一个列表，其格式为。该列表起初是空的。当C收到对22ii2IDII *IDIDIDID,UP,,的询问时，C首先判定是否等于。若，C随机选择，计算；否则设置,,ZiJiJiiiq listHUbP,(,,,)IDPU,,,,UA，。最后C将加入到并将返回给。 2iiiiiiiII listH(,,,,)MIDRPhHA询问：C维护一个列表，其格式为。这个列表被初始化为一个空表。当询3ID3II*list问HHMIDRP(,,,)(,,,,)MIDRPhhA时，C随机选择，将加入到并将返回给。 hZ,33iiiiiiiiiiIIiq 询问：当C接收到IDAIDID,的关于身份为的用户的秘密值询问时，若，C终止。否则，CiIIiJlist首先生成该用户的公钥，然后检索(,,)IDxPx,,IDK找到。若，表明关于身份的公钥已经被替换，iiiii因此C无法正确回答Ax的秘密值询问，C返回；否则C返回。 ,IIi '询问：当C接收到(,)IDPIDAIDID,的一个关于身份为的用户的公钥替换询问时，若，iiiIIiJlist'C终止，否则，C检索xPP,,,,(,,)IDxPK找到并设置。 iiiiii 询问当IDAPM向C请求身份为，公钥为的用户对消息在的签名时，C按照如下步骤回答该询iIIii 问： *1、随机选择。 hZVG,,,1iqi ,hi2、计算ReVPeUPeQP,(,)((,)(,))UHIDPQHID,,(,),()，其中。 iiiii0iiiii21 3、设置HMIDRP(,,,)h=。 3iiiii 4、返回(,)hV ii *****最后，DIID,(,(,),,)MhVIDP,,A输出一个伪造。若，C终止。否则，根据Forking Lemma，JII****C选择不同的Hash函数H'A(,'(','),,)MhVIDP,,并再次利用的能力，它可以得到另一个伪造。3II 5 *,hReVPeUPeQP,(,)((,)(,))从而C得到了两个有效的伪造，并且它们满足与0 *',h*****ReVPeUPeQP,(',)((,)(,))UHIDPbP,,(,)(,,,)IDPbP,。其中，，并以的形式PaP,02 list存在于H中。 2**',,hh 于是就有等式eVPeUPeQPeVPeUPeQP(,)((,)(,))(',)((,)(,)),。由我们设置可知， 00 ,,hh'eVVPebPaPeQsPebPaPeQsP(',)((,)(,))((,)(,)),, -1因此，C可以计算出CDH问题的解abPhhVVsQ,(-')(-')-。 5. 在计算和通信效率方面，我们将用本文的方法所构造的方案与一些目前能在[11]中模型下证明是安全的方案，以及几个效率比较高，但是安全性未能有效证明的方案进行比较。我们用P表示一个双线性对运算，S表示群G中的标量乘运算，E表示群G中的幂运算，H表示一个哈希到群G的运算。用P表示1211 *G中的一个点的长度，用P表示G中的一个点的长度，用Z表示中的一个点的长度。比较结果如下Z1221q 表所示 1 方案 签名 验证（预计算） 签名长度 公钥长度 安全性 [7]中方案1 2S 2P,2S,1H(2P,2S) 2P 1P 未知 11 [7]中方案2 1S,1E 1P,2S,1E(1P,1E) 1P, 1P 1P 未知 121 [10]中方案 3S,2H 4P,3H(3P,2H) 2P 1P 安全 11 [14] 中方案1 1S,1H 3P,1H(2P,1H) 1P 1P 未知 11 [14] 中方案2 3S,1E 2P,2S,1E,1H(1P,2S,1E) 2Z,1P 1P 安全 111 [15]中方案 1S,2E 1P,1S,2E(1P,2E) 2Z,1P 1P 安全 112 我们的方案 2S，1E 3P，1H（1P，1E） 1Z,1P 1P 安全 111 从表1中可以看出，在签名阶段我们的方案未涉及到双线性对计算，并且在效率上与其它方案相差无 几。在验证阶段，当不考虑预计算时我们的方案比[10]中方案效率高一点，而与[14]中方案1效率基本相同。与[7,15] 中方案及[14]中方案2相比虽然效率略低，但我们方案的签名长度是 [14]中方案2及[15]中方案的2/3，与[7]中方案比我们的签名方案有较高的安全级别。当考虑预计算时，本文签名方案的验证算法比 [10,14,15] 中方案及[7]中方案1效率更高，而与[7]中方案2相比效率基本相同，但签名长度则相对较短。 在有些情况下，我们的方案可以进行预计算。比如验证者若经常接收某个签名者的签名并进行验证， 那么他可以预计算QUeUPeQP,,(,)(,)并储存这些值，从而大大减少实际计算代价。此外在安全要IDIDID0 求较高，签名长度要求较短的环境中我们的方案也有相对优势。 因此，我们的方案可用于带宽受限的Ad Hoc网络，以及需要频繁传递和验证签名的电子商务和电子政务等领域以提供完整性、真实性和不可否认 性等安全服务。 5. 我们提出了一类无证书签名方案的构造方法，用这种方法构造的方案的安全性基于计算Diffie-Hellman问题的困难性。在考虑预计算的情况下，我们的方案效率很高，总共只需计算1个双线性对，明显优于其它现有方案。我们方案的安全性证明是基于文献[11]中的安全模型，它是无证书签名方案的一个很强的安 全模型。因此，我们的方案可在适合使用无证书密码体制的场合用以提供真实性，完整性和不可否认性等 安全服务。 6 [1] Shamir A. Identity based cryptosystems and signature schemes// Proceedings of the Crypto'84, Lecture Notes in Computer Science 196. California, USA: Springer-Verlag, 1984: 47-53 [2] Al-Riyami S and Paterson K. Certificateless public key cryptography// Proceedings of the Asiacrypt 2003, Lecture Notes in Computer Science 2894. Taipei, Taiwan: Springer-Verlag, 2003: 452-473 [3] Huang X, Susilo W, Mu Y and Zhang F. On the security of a certificateless signature scheme// Proceedings of the CANS 2005, Lecture Notes in Computer Science 3810. Xiamen, China: Springer-Verlag, 2005: 13-25 [4] Yap W, Heng S, and Goi B. An efficient certificateless signature scheme// Proceedings of the EUC Workshops 2006, Lecture Notes in Computer Science 4097. Seoul, Korea: Springer-Verlag, 2006: 322-331 [5] Park J. An attack on the certificateless signature scheme from EUC Workshops 2006. Cryptology ePrint Archive, Report 2006/442, 2006 [6] Zhang Z, Feng D. Key replacement attack on a certificateless signature scheme. Cryptology ePrint Archive, Report 2006/453, 2006 [7] Choi K, Park J, Hwang J, and Lee D. Efficient certificateless signature schemes// Proceedings of the ACNS 2007, Lecture Notes in Computer Science 4521. Zhuhai, China: Springer-Verlag, 2007: 443-458 [8] Castro R and Dahab R. Two notes on the security of certificateless signatures// Proceedings of the ProvSec 2007, Lecture Notes in Computer Science 4784. Wollongong, Australia: Springer-Verlag, 2007: 85–102 [9] Zhang J, Mao J. Security analysis of two signature schemes and their improved schemes// Proceedings of the ICCSA 2007, Lecture Notes in Computer Science 4705. Kuala Lumpur, Malaysia: Springer-Verlag, 2007: 589-602 [10] Zhang Z, Wong D, Xu J and Feng D. Certificateless public-key signature: security model and efficient construction// Proceedings of the ACNS 2006, Lecture Notes in Computer Science 3989. Singapore: Springer-Verlag, 2006: 293-308 [11] Hu B, Wong D, Zhang Z, Deng X.. Key replacement attack against a generic construction of certificateless signature// Proceedings of the ACISP 2006, Lecture Notes in Computer Science 4058. Melbourne, Australia: Springer-Verlag, 2006: 235–346 [12] Bellare M and Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols// Proceedings of the CCCS '93. Virginia, USA: ACM Press, 1993: 62-73 [13] Pointcheval D and Stern J. Security proofs for signature schemes// Proceedings of the EUROCRYPT'96, Lecture Notes in Computer Science 1070. Saragossa, Spain: Springer-Verlag, 1996: 387-398 [14] Huang X, Mu Y, Susilo W, Wong D, and Wu W. Certificateless signature revisited// Proceedings of the ACISP 2007, Lecture Notes in Computer Science 4586. Townsville, Australia: Springer-Verlag, 2007: 308-322 [15] Zhang L, Zhang F, and Zhang F. New efficient certificateless signature scheme// Proceedings of the EUC Workshops 2007, Lecture Notes in Computer Science 4809. Taipei, Taiwan: Springer-Verlag, 2007: 692–703 7 A Method to Construct a Class of Certificateless Signature Schemes Abstract: Certificateless public key cryptography (CL-PKC) is a new paradigm in public key cryptography. It effectively solves the inherent key escrow problem in identity based public key cryptography (ID-PKC) while keeps its certificate free property. Designing efficient and secure signature schemes in certificateless public key setting is an interesting research topic that attracts the attentions of many researchers. In this paper, we propose a new method to construct a class of certificateless signature schemes. The schemes constructed using our method can be proven secure in a very strong security model. The overall performances of our newly constructed schemes are better than that of the other certificateless signature schemes available in the literature. Keywords: certificateless public key cryptography, computational Diffie-Hellman problem, bilinear pairing, certificateless signature, random oracle model. Background This paper investigates efficient constructions of signature schemes in Certificateless public key setting. Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. In traditional public key cryptosystems, the management of certificates is usually complex and costly. Shamir introduced Identity-based public key cryptography to remove this requirement. However, key escrow problem is inherent in Identity-based public key cryptography. Certificateless public key cryptography is a new paradigm which was first introduced by Al-Riyami and Paterson in 2003. Their main purpose is to solve the key escrow problem in Identity-based public key cryptography, while keeping the implicit certification property of Identity-based public key cryptography. Recently, a number of certificateless signature schemes have been presented. The first one was presented by Al-Riyami and Paterson without formal security analysis. Later, Huang et al. pointed out a security drawback of this scheme and proposed a secure one. They also defined the security model of certificateless signature schemes. An improved security model was presented by Zhang et al. and an even stronger one was put forward by Hu et al.. With respect to the efficiency, most of the previous secure CLS schemes involve a relatively large amount of paring computation and exponentiation in the process of signing and verification. In this paper, the authors show a new method to construct a class of certificateless signature schemes. This kind of schemes can be proven secure in a very strong security model. In addition, the constructed schemes have a better overall performance when compared with some other provably secure certificateless signature schemes available. Our research is supported by the National Natural Science Foundation of China (No. 60673070) and the Natural Science Foundation of Jiangsu Province (No. BK2006217). The projects focus on the study of secure and efficient encryption schemes, signature schemes and key agreement protocols in certificateless setting. 8