高效的基于ID的无证书签名方案.doc

第2期刘景伟等：高效的基于ID的无证书签名方案93高效的基于ID的无证书签名方案刘景伟，孙蓉，马文平（西安电子科技大学 计算机网络与信息安全教育部重点实验室, 陕西 西安 710071）摘 要：通过利用gap diffie-hellman (GDH)群，提出了一种高效的基于ID的无证书签名方案，该方案通过将2个部分公钥绑定相同的一个ID，从而解决了密钥托管问题。在这个方案中，私钥生成中心 (PKG，private key generator)不能够伪造合法者的签名，因为只能生成一部分私钥，其安全性依赖于CDHP(computational diffie-hellman problem)。在随机预言机模型下，新方案被证明能够抵抗适应性选择消息攻击和ID攻击下的存在性伪造。该方案不仅解决了密钥托管问题而且与许多已有的方案相比具有较高的效率。关键词：基于身份的签名方案；无证书签名；双线性对；密钥托管问题；gap diffie-hellman群中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2008)02-0087-08Efficient ID-based certificateless signature schemeLIU Jing-wei, SUN Rong, MA Wen-ping（Key Laboratory of Computer Network and Information Security, Ministry of Education, Xidian University, Xian 710071, China）Abstract: Using gap diffie-hellman (GDH) groups, an efficient ID-based certificateless signature scheme was proposed, which could solve the key escrow problem through binding two partially public keys with a same identity. In this scheme, PKG was prevented from forging a legal users signature because he only generated the partially private key. The security relied on the hardness of the computation diffie-hellman problem (CDHP). Under the random oracle model, the new scheme was proved to be secure against existential forgery on adaptively chosen message and ID attack. This scheme not only eliminated the inherent key escrow problem but also had a higher efficiency than the existing schemes did.Key words: ID-based signature; certificateless signature; bilinear pairing; key escrow; gap diffie-hellman group1 引言1.1 研究现状收稿日期：2007-08-20；修回日期：2008-01-09基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z472）；国家自然科学基金资助项目（60773002, 90604009）Foundation Items: The National High Technology Research and Development Program of China (863 Program)(2007AA01Z472); The National Natural Science Foundation of China (60773002, 90604009)在传统的基于CA的密码系统中, 公钥与签名者身份之间的绑定是通过一个数字证书来实现的，但是系统在计算、存储和管理证书方面却需要付出大量的工作。为了简化证书的管理过程，Shamir在1984年首先提出了基于ID的密码系统（IBC, ID based cryptosystem）1。在这个系统中，用户可以使用自己的身份作为公钥。与传统密码系统相比，IBC系统简化了整个密钥管理过程，但是它却引入另外一个问题密钥托管问题，即私钥生成中心（PKG, private key generator）知道所有用户的私钥。在Shamir最初的工作1之后，许多基于ID的密码方案相继发表，但是其中的大部分方案由于效率低下而不实用。最近，双线性对（也就是代数曲线上的Weil对和Tate对）的出现给密码学开辟了一个全新的领域，它使得人们过去不知道的或者不实用的方案现在密码学实现方面成为可能2,3。更为幸运的是它们也是构造基于ID的签名方案（IBS, ID based signature）的重要工具。近些年来，由双线性对构造的基于ID的签名方案大量发表412。在2000年的SCIS00上，Sakai、Ohgishi和Kasahara 3人在文献4中首先提出了由对构造的基于ID的签名，然而他们并没有在自己的工作中给出安全性分析。Paterson在文献5中提出了一种基于对的IBS签名方案，并且给出了大概的安全性假设，但是仍然没有给出严格的安全性证明。2002年，Hess在文献6中提出了一种可证明安全的IBS签名方案，该方案能够抵抗适应性选择消息攻击和固定ID攻击下的存在性伪造。2003年，Cha-Cheon在文献7中提出了一种基于Gap Diffie-Hellman群的IBS签名方案。他们给出了一种针对于IBS方案的安全性定义：抗适应性选择消息攻击和ID攻击下的存在性伪造。在此定义下，他们给出了所提方案的安全性证明。在ASIACRYPT2003上，Al-Riyami等人在文献8中介绍了一种新的概念：无证书的公钥密码系统（CL-PKC, certificateless public key cryptosystem），利用这一模型构造出的公钥密码系统避免了过去基于ID的密码系统（IBC）中内在的密钥托管问题。同年，Chen等在文献9中提出了一种不需要可信的PKG的IBS方案，消除了固有的密钥托管问题。在文献10中，Gorantla和Saxena提出了一种有效的无证书签名方案，该方案比文献8中的IBS方案更为高效。在文献11中，Al-Riyami等人提出了另一个无证书的公钥加密方案（CL-PKE），其安全性是由CDHP（computational diffie-hellman problem）的困难性来保证，并且该方案也比文献8中的原始方案要更为高效。在文献12中，作者提出了一种新的CL-PKE方案，该方案不再依赖于双线性对，并且作者给出了随机预言机模型下的安全性证明。1.2 主要工作及本文内容安排本文首先给出了一种基于ID的无证书签名方案的详细定义，该定义通过将2个部分公钥绑定相同的一个ID，从而解决了密钥托管问题。在这个方案中，PKG不能够伪造合法者的签名，因为他只能生成一部分私钥。然后，利用GDHL（gap diffie-hellman）群构造了一种高效的无证书签名方案，其安全性依赖于CDHP。更准确地说，在随机预言机模型下，假设CDHP是困难的，新方案被证明能够抵抗适应性选择消息攻击和ID攻击下的存在性伪造。新方案不仅解决了密钥托管问题而且与许多已有的方案相比具有较高的效率。本文将在后面的部分讨论新方案的安全性和效率分析。本文的主要贡献如下：1) 提出了基于ID的无证书签名方案的一般定义和攻击模型；2) 构造了一种高效的基于ID的无证书签名方案；3) 给出了基于ID的无证书签名方案在随机预言机模型下的安全性证明。本文剩余部分组织如下：第2节，提出了基于ID的无证书签名方案的基本定义和基本攻击模型；第3节，详细地构造出了一种高效的基于ID的无证书签名方案；第4节，讨论了新方案的安全性分析并且给出了新方案与已有方案间的执行效率比较；最后，第5节是结束语。2 基于ID的无证书签名方案2.1 基本定义这一部分将介绍基于ID的无证书签名方案的一些基本定义。在新方案中涉及到的一些参数描述如下：1) 明文消息空间：一个字符串集合；2) 一个身份空间：可能的集合；3) 一个签名空间：一个可能的签名空间；4) 一个部分私钥空间：用来生成签名的可能部分私钥集合，它是由签名者自己生成的；5) 另一个部分私钥空间：用来生成签名的可能部分私钥集合，它是由PKG生成的；6) 一个部分公钥空间：用来验证签名的可能的部分公钥集合，它是由签名者自己生成的；7) 另一个部分公钥空间：用来验证签名的可能的部分公钥集合，它是由PKG通过签名者的身份和生成的。在一个基于ID的签名方案中，PKG有可能扮演以下3种角色。1) 可信的：跟传统的PKG一样，PKG是诚实的，不可能与他人合谋作弊；2) 消极不诚实：PKG有可能将签名者的部分私钥泄漏给一个敌手；3) 积极不诚实：PKG自己生成一个合法的公钥对以及一个合法的私钥对用来绑定一个签名者的，然后泄漏给一个敌手。定义1 一个完整的基于ID的无证书签名方案包括5个部分（Parameter Setup，Extract，Sign，Verify，Trace）：1) 一个有效的概率算法Parameter Setup：系统参数描述 这里是安全参数，是PKG公钥，由PKG的主密钥生成。2) 一个有效的概率算法Extract：Extract包含下面3个子算法： Y1Gen：X1Y1，定义为=Y1Gen； Y2Gen：IDY1Y2，定义为y2=Y2Gen (id,y1)； X2Gen：Y2X2，定义为x2=X2 Gen。其中，Y2Gen是一个单向函数，用来一次性绑定和。3) 一个有效的概率签名算法Sign：MX1X2S，对于任何消息和私钥，定义，其中，。4) 一个有效的签名验证算法Verify：，对于任何消息和公钥，都要满足(1)5) 一个有效的交互式“知识证明”算法Trace：诚实，不诚实，如果PKG是“积极不诚实”的，那么就存在2个三元组和，并且，于是下面的算法就是必要的(2)为了保护用户的部分私钥，算法Trace应该是一个由仲裁者和真正的合法用户共同执行的一个交互式的“知识证明”算法。这里需要注意的是基于ID的无证书签名方案能够确实能够阻止一个“积极不诚实”的PKG同时将两个或多个公钥绑定于一个相同的id，但是它看起来好像并不能避免一个“消极不诚实”的PKG泄漏一个用户的部分私钥。幸运的是，就算PKG泄漏了一个用户的部分私钥，另外一个部分私钥仍然能够保护用户的信息安全。在后面的部分将对这一点进行严格地安全证明。2.2 基于ID的无证书签名方案的攻击模型在基于CA的数字签名安全模型13,14中，假如一个敌手能够输出一个有效的消息和签名对就算赢得游戏，在这个过程中，他可以要求签名者签署除了输出签名外的任何消息。因此，一个好的签名方案首先应该能够在适应性选择消息攻击下抵抗存在性伪造。与文献7,14中介绍的很类似，这里将引入基于ID的无证书签名方案的一个攻击模型。一个基于ID的无证书签名方案包含5个算法：Parameter Setup，Extract，Sign，Verify和Trace。称一个基于ID的无证书签名方案是安全的（能够抵抗适应性选择消息攻击和ID攻击下的存在性伪造），如果在下面的游戏中不存在多项式时间算法A通过借助挑战者S而能够以一个不可忽略的概率优势赢得游戏：1) S首先运行Parameter Setup，然后把公共参数发送给A。2) A可以进行如下询问： Hash function query.S对输入的问题进行杂凑运算，并将计算的值发送给A。 Extract query. 给定身份信息id和公钥，S返回对应于id的部分私钥。其中是由算法生成的。 Sign query. 给定一个三元组和一条消息m，S返回一条签名。其中签名是由算法Sign生成的。3) A输出，其中m是一条消息，是签名。在下面3种情况中，称A赢得了游戏，如果是消息m的对应id的有效签名。 A输出，其中是一个合法身份，是与此身份相对应的公钥，和m分别不等于Extract和Sign先前的任何输入。 A输出，其中是一个合法身份，是与此身份相对应的公钥，是Extract先前的一个输入，但是m不是Sign先前的任何输入。 A输出，其中id一个合法身份，是伪造的公钥，是Extract先前的一个输入，而且m是Sign先前的一个输入。使用这个攻击模型，在后面的部分能够将基于ID的无证书签名方案的安全性归约到CDHP（和）和DLP（）的困难性。3 一种高效的基于ID的无证书签名方案设和表示阶为素数q的循环群，是的生成元，设是一个对，并且满足双线性和非退化2种性质。同时假设非常容易计算，但是对于任何随机给定的和，要想计算出满足，是非常困难的。这里需要指出的是对应该是对称的。进而，定义2个杂凑函数和，其中。同样定义。这种高效的基于ID的无证书签名方案包含5个算法：Setup，Extract，Sign，Verify和Trace。在系统中涉及到3个参与者：PKG、签名者和验证者。Setup：PKG随机选取一个整数，计算他的公钥，然后公布，但是将秘密保存。签名者同样随机选取一个整数作为他的部分私钥，然后计算作为自己的部分公钥。Extract：当一个签名者要求PKG为自己生成一个对应该签名者身份的部分私钥时，PKG执行该算法。假设签名者的身份是一个给定的字符串，那么这就是另一部分公钥。对应该身份的另一部分私钥由式子得到，其中，是由PKG计算并发送给签名者的。对于一个签名者来说，就是他的公钥，而就是他的私钥。对于每一个身份来说，Extract设置一般只需要运行一次，而且每次都使用相同的系统参数。Sign：为了对消息签名，签名者首先随机选取一个整数，然后计算(3)(4)(5)二元组为最后的签名。Verify：一旦收到消息m和签名，验证者计算(6)当且仅当和时，验证签名通过。验证者只需要验证上面等式是否成立来检测签名是否有效。Trace：假设PKG（或者与一个不诚实的用户合谋）想要假扮一个身份信息为id的合法用户。他（或者他们）可以做以下事情： PKG随机选取一个整数，使得，和； 然后他对消息m执行前面定义的签名协议； 最后输出伪造的签名对 。因为和，其中，PKG伪造了一个合法用户的“有效”签名。然而，这个合法用户可以提供证据来说明该“有效”签名是由PKG为造的，证明过程与基于CA的密码系统中的证明相似：他首先把发送给仲裁者，然后使用“知识证明”来证明他知道；仲裁者随机选择一个安全整数，并把它发送给用户；用户计算。如果等式成立，仲裁者则判定PKG是不诚实的，因为身份信息id同时对应着和2个公钥对，而主密钥只有PKG知道。4 新方案的安全性和执行效率分析4.1 安全性在这一部分，将给出在随机预言机模型15下基于ID的无证书签名方案的安全性分析。定理1（正确性）：新方案满足正确性。证明 如果(7)其中， (8) (9)(10)那么(11)本定理得证。定理2（不可伪造性）：新方案能够抵抗适应性选择消息和ID攻击下的存在性伪造，假设CDHP问题是困难的。证明 本证明方法参考了Pointcheval和Stern在文献13中对数字签名方案不可伪造性的证明方法，同样充分利用了分叉引理13,14。首先，需要注意的是在第3节给出的基于ID的数字签名在输入一条消息m时，会生成一个合法的三元签名组，其中k随机选取自，所以的值也随机取自，是的杂凑值，而U的值依赖于，和消息。因为前提假定PKG可能会不诚实，所以敌手A可以与一个不诚实的PKG共谋伪造一个数字签名。这里存在2种情况需要讨论： A在没有可信PKG的帮助下伪造一个合法签名； A在一个消极不诚实PKG的帮助下伪造一个合法签名。1）假定H和是随机预言机，A是一个概率多项式时间图灵机，它的输入只是一些公共参数。假设A它可以向随机预言机H询问个问题，向随机预言机h询问个问题，向签名预言机Sign询问R个问题。在时间界限T内，A以一个不可忽略的概率（这里q是一个安全参数）生成一个有效的签名。模拟仿真：S把公共参数，G2，P，H，和给A。S试图通过模拟所有的预言机来得到一个对应于固定k的私钥，其中是一个Sign算法中用到的上的随机整数，目的是能够像真正的签名者一样对任意的消息m进行签名。A可以进行下列询问。H-Queries：A在任何时候向随机预言机H询问问题。S通过将二元组保存到列表H-List来模拟随机预言机，其中是一个二元组。当预言机的输入问题为时，S作如下回答： 如果输入问题已经存在于列表H-List的二元组中，那么S就输出； 否则的话，S随机选取并输出一个，然后将添加到H-List。Extract-Queries：A可以要求回答对应于任意身份和公钥的部分私钥。如果，那么S返回无效。否则，它就通过运行Extract算法得到并输出对应于的部分私钥。h-Queries：A可以在任何时候向随机预言机h提问问题。S通过将二元组保存到-List来模拟随机预言机，其中是一个二元组。当预言机的输入问题为时，S作如下回答： 如果输入问题已经存在于列表-List的二元组中，那么S就输出；否则的话，S随机选取并输出一个，然后将添加到-List。Sign-Queries：S通过对要求签名的消息m进行签名来模拟签名预言机。S对提问作如下回答： 随机选取和，其中不等于h预言机先前的任何输出； 计算。如果是h预言机先前的一个输入，则返回； 将二元组添加到h-List； 输出作为消息m的签名。注意；这里必须检查一下真实的数字签名和伪造的数字签名在概率分布上是否相同。(12)首先计算一下通过密钥签署的真实数字签名的概率分布(13)下面是伪造的数字签名的概率分布(14)所以即使不知道密钥也可以以一个不可区分的概率分布模拟仿真出三元组。因此，由S所模拟出的签名预言机是高质量的，进而A对所模拟出的Sign-Queries的回答也会非常满意。它就能够充分施展他的伪造能力。输出：最后，A以一个不可忽略的概率对一个输入消息输出一个签名消息，而且满足。在这种情况下，A通过向h-Querie提问生成，但是却没有向Extract -Query提问，也没有向Sign -Query提问m。现在将上述过程模拟仿真2次，所以A将能够得到2个有效的签名和，其中。那么就能够得到以下的等式(15)利用，S就可以对任意消息m以一个固定的签署有效签名（注意：这里也是固定值，因为），其中，。这个过程就好像一个合法的签名者在使用自己的私钥进行签名。由上面的等式S在期望时间小于之内解决了CDHP困难问题(16)这与CDHP问题的困难性相矛盾。2）随机预言机的假设与情况1）相同。假定存在一个概率多项式时间图灵机A，它的输入只是一些公共参数，它可以向随机预言机H询问个问题，向随机预言机询问Qh个问题，向签名预言机Sign询问R个问题。但是这时，A可以从一个消极不诚实的PKG处得到一些额外的信息S2。模拟仿真：S把公共参数，P，H，和，给A。S试图通过模拟所有的预言机来得到，目的是能够像真正的签名者一样对任意的消息进行签名。A能够像1）中一样进行提问。输出：最后，A以一个不可忽略的概率对一个输入消息输出一个签名消息，而且满足。在这种情况下，A通过向-Querie提问生成，通过向Extract -Query提问来生成，但是没有向Sign -Query提问。现在将上述过程模拟仿真2次，所以A将能够得到两个有效的签名和，其中。那么就能够得到以下的等式(17)利用，S就可以对任意消息m签署有效签名，其中，k随机选择于。这个过程就好像一个合法的签名者在使用自己的私钥进行签名。由上面的等式在期望时间小于之内解决了CDHP困难问题(18)这与CDHP问题的困难性相矛盾。在定理3之前，首先给出基于ID的无证书签名方案中可追究性的定义。定义2 在基于ID的签名方案中，如果PKG伪造了对应一个合法用户的一对“有效”的公钥和私钥，而该用户真正的公钥是，私钥是，那么该用户通过一个Trace这样一个“知识证明”算法，可以给仲裁者提供一个证据，表明PKG是“积极不诚实”，我们就称这样的方案是满足可追究性的。定理3 (可追究性)：新方案满足可追究性。证明 假设H随机预言机，并且存在一个输入仅包含公共参数的概率多项式时间图灵机A。假设A能够作如下询问：H-Queries：同定理2中的定义一样。Extract-Queries：同定理2中的定义一样。输出：最后，以一个不可忽略的概率，A输出一个对应于的“有效”的部分私钥，而且满足(19)但是对应于身份的真正合法的部分私钥和公钥是和。这时候下面2种情况必定有一种情况发生：1）PKG确实是诚实可信的，这就意味着Extract -Query没有回答过和 2个问题，但是对手却能够为计算。然而，这与离散对数问题DLP的困难性相矛盾，于是可以确定第二种情况必然发生。2）PKG是“积极不诚实”，三元组一定作为Extract -Query的输入被提问过(20)通过使用交互式证明算法Trace，用户可以向仲裁者提供一个证据，证明他确实知道。因为主密钥只有PKG知道，但是身份却同时对应着两个公钥和，所以仲裁者可以断定PKG是不诚实的。4.2 执行效率由于在新的基于ID的无证书签名方案中设计了预计算（尤其是对运算），这使得新方案具有更高执行效率。在签署任何消息之前，用户可以预先给式(3)中的计算，为式(5)中的计算。同样地，在验证任何消息之前，验证者也可以预先给式(6)中的计算，以及预先计算。因为新的基于ID的无证书签名方案设计有许多预计算，所以它与现在已有的方案相比具有更高的执行效率。在表1中，给出了新方案与已有方案的执行效率比较。在表1中，“”对运算的数量，“”表示上指数运算的数量，“”表示上的乘法运算的数量，“”表示上的乘法运算的数量，“”表示上的加法运算的数量，“”表示H杂凑操作的数量，“h”表示h杂凑操作的数量，“”表示上的加法运算的数量。在表1中，只是对于签名过程，新方案的执行效率和文献8中的一样，但是要比文献9,10中的差一些，但是新方案的签名验证算法却因此简化了更多。由于从总体上看，对于一个签名方案来说，通常是一次签名，多次验证，所以新方案在整体上来说获得了更高的执行效率。表1基于ID的无证书签名方案与已有方案的执行效率比较算法预签名签名算法预验证验证算法文献8的方案/文献9的方案/文献10的方案/新的方案5 结束语本文详细地介绍了基于ID的无证书签名方案的定义，该方案通过将2个部分公钥绑定相同的一个ID，从而解决了IBS系统中固有的密钥托管问题。在这个方案中，PKG不能够伪造合法者的签名，因为他只能生成一部分私钥。通过利用GDH群，构造了一种高效的基于ID的无证书签名方案，其安全性依赖于CDHP。更准确地说，在随机预言机模型下，新方案被证明能够抵抗适应性选择消息攻击和ID攻击下的存在性伪造，假设CDHP是困难的。新方案不仅解决了密钥托管问题而且与许多已有的方案相比具有较高的效率。从前面的各种比较可以看出基于ID的无证书签名方案不仅克服了基于ID的签名系统（IBS）固有的密钥托管问题，而且与已有的方案相比具有更高的执行效率，这使得新方案具有更为广泛的应用空间。参考文献：1SHAMIR A. Identity-based cryptosystems and signature schemesA. Advances in Cryptology-Crypto84C. Springer- Verlag. 1984. 47-53.2BONEH D, FRANKLIN M. Identity-based encryption from the weil pairingA. Advances in Crptology-Crypto01C. Springer-Verlag, 2001. 213-229.3BONEH D, LYNN B, SHACHAM H. Short signatures from the weil PairingA. Advances in Crptology-Asiacrypt01C. Springer-Verlag, 2001. 514-532.4SAKAI R, Ohgishi K, Kasahara M. Cryptosysytems based on pairingA. Symposium on Cryptography and Information Security- SCIS00C. Okinawa, Japan, 2000. 26-28.5PATERSON K G. Id-based signatures from pairings on elliptic curvesJ. Electronics Letters, 2002, 38(18):1025-1026.6HESS F. Efficient identity based signature schemes based on pairingsA. Selected Areas in Cryptography-SAC02C. Springer-Verlag, 2003. 310-324.7CHA J C, CHEON J H. An identity-based signature from gap diffie-hellman groupsA. Public Key Cryptography-PKC03C. Springer-Verlag, 2003. 18-30.8AL-RIYAMI S S, PATERSON K G. Certificateless Public Key CryptographyA. ASIACRYPT 2003C. Springer- Verlag, 2003.