基于身份密码体制的高效门限群签名方案.doc

第5期刘宏伟等：基于身份密码体制的高效门限群签名方案127基于身份密码体制的高效门限群签名方案刘宏伟1,2，谢维信2，喻建平2，张鹏2（1. 西安电子科技大学 电子工程学院，陕西 西安 710071；2. 深圳大学 信息工程学院，广东 深圳 518060）摘 要：门限群签名用于保障集体决策的安全，针对其在实际应用中的效率问题，基于双线性映射和秘密共享思想，提出了一个新的基于身份密码体制的门限群签名方案。该方案将系统主密钥以自选份额秘密的模式分散到签名成员集合中，使各成员签名私钥均为门限存储，有利于保证系统整体安全性；采用基于身份的t-out-of-n秘密共享算法则使方案的效率更高。根据门限群签名性质对该方案进行了安全性分析和效率对比，结果表明该方案是一种安全高效的门限群签名方案。关键词：门限群签名；基于身份密码体制；双线性映射；秘密共享中图分类号：TP 309 文献标识码：A 文章编号：1000-436X(2009)05-0122-06Efficiency identity-based threshold group signature schemeLIU Hong-wei1,2, XIE Wei-xin2, YU Jian-ping2, ZHANG Peng2(1. School of Electronic Engineering, Xidian Univ., Xian 710071, China;2. School of Information Engineering, Shenzhen Univ., Shenzhen 518060, China)Abstract: Threshold group signature was used to guarantee the security of the collective decision. To improve the efficiency, a new identity-based cryptography threshold group signature scheme was proposed basing on bilinear pairing and secret sharing. In this scheme, the master key was distributed into the whole group and the users signature key was stored in a threshold way, these methods ensured the whole security of signature systems. The scheme with a identity-based t-out-of-n secret sharing algorithm was highly-efficient. The careful analysis and the comparison of computational efficiency show that this scheme is secure and efficient.Key words: threshold group signature; identity-based cryptography; bilinear pairing; secret sharing1 引言收稿日期：2008-06-21；修回日期：2009-03-20基金项目：广东省自然科学基金资助项目（04106250）Foundation Item: The Natural Science Foundation of Guangdong Province (04106250)门限群签名1是群体密码学的重要分支，是建立在门限秘密共享体制上的数字签名技术。门限群签名方案主要针对共同决策领域，研究如何有效保障集体决策的真实性、可用性及不可否认性。门限群签名方案可应用于电子投票系统、电子拍卖系统及电子合同签订系统等，因而自提出以来便受到了广泛关注2。基于身份的公钥密码体制最初由Shamir3提出，其中实体的公钥是直接从其身份（identity）信息得到，私钥由一个可作为可信中心（TA）的私钥生成中心生成。基于身份的公钥密码体制避免了对证书的管理，可减轻可信中心的负担。D.Boneh和M.Franklin4在2001年将双线性映射应用到基于身份的加密方案IBE（identity-based encryption）中，并于同年提出了基于双线性映射的短签名方案5，此签名方案具有签名长度短、安全高效等特点。Chen等6将双线性映射应用到基于身份的群签名方案中，提出了一种新的高效群签名方案。文献7基于Hess签名方案8提出了一个可验证的门限签名方案，并给出了详细证明，但该方案在签名过程中签名成员需要多次使用秘密共享技术协商参数和计算部分签名，因此该方案过程较复杂，效率较低。文献9基于文献7，首次在基于身份的门限群签名方案中引入了前向安全的概念，使得签名参与者集合的部分密钥能够进行动态更新，从而可有效防止移动攻击；但因方案的秘密共享及签名验证思想与文献7一致，且增强了安全性而令计算开销进一步增加。文献7与文献9的共同特点是基于Hess签名方案和Lagrange插值算法的秘密共享方案10，秘密为签名者私钥。而事实上，系统主密钥的安全级别远高于用户私钥，因此为系统整体安全性考虑，应首先对主密钥进行门限存储。另外，如果门限存储用户私钥，则该群组需要进行多次秘密共享过程；而对于主密钥来说，则在该群组中仅需一次秘密共享过程。本文基于文献5的Boneh短签名方案，采用t-out-of-n秘密共享思想11，提出了一种新的基于身份密码体制的门限群签名方案，分析表明该方案是安全的，且在运算效率方面具有一定优势，是一个高效的群签名方案。2 双线性映射双线性映射指2个循环群之间相对的线性映像关系。若有和是阶为大素数的加法群和乘法群，定义双线性映射：，且对于与，满足下列特性。1) 双线性：。2) 非退化性：如果是的生成元，则是的生成元。3) 可计算性：存在有效算法计算。在和中有以下困难数学问题定义。1) 离散对数问题（DLP）：给定，找到一个整数n，满足。2) 计算性Diffie-Hellman问题(CDHP)：设，给定,，计算。3) 双线性Diffie-Hellman问题(BDHP)：设，给定,计算。3 基于双线性映射的门限群签名方案本文门限群签名方案中，设为签名参与者群体，秘密管理者由TA承担。具体过程如下。3.1 系统初始化可信中心TA利用BDH参数生成器和安全参数生成大素数，2个阶群、，可容许的双线性映射。令为的生成元，随机选取数为系统主密钥，计算可信中心的公钥，选择密码Hash函数，明文空间为。系统公开参数为 ，且TA设立可供检索的公用数据库（PD, public database）。3.2 签名申请发方A随机选择，计算,其中，并发送、至TA，发出群签名申请。TA在数据库PD上公开，发方A要对公开信息负责,若信息不符则向TA发出申诉并拒绝下一步工作。3.3 秘密分发n个参与者随机选择作为其份额秘密，并发送至TA。TA验证身份信息，确定来自签名参与者群体；分发给唯一的身份信息，计算(1)并选择t个参与者分别计算(2)之后秘密保存。TA删除及，公开，其中参与者要对公开信息负责，若信息不符则向TA发出申诉并拒绝下一步工作。3.4 签名计算份额签名并发送至TA。TA确认的身份，并验证等式(3)若等式成立则说明份额签名正确。若签名正确，TA计算(4)并发送至A。A计算(5)(6)其中，为A的部分签名私钥。A发送对消息的签名至B。3.5 验证验证者B根据邮件明文计算，根据发方身份信息计算。验证等式(7)若等式成立，则说明的正确性得到了发方A的确认，发方不能对签名否认。收方B进一步验证等式(8)若等式成立则签名验证通过，否则拒绝。4 安全性分析本文门限群签名方案基于Boneh短签名方案，其共同特征为用户私钥是有限域上的数而不是椭圆曲线上的点，此外方案用于签名验证的唯一公开密钥是签名申请者的身份信息，因此，该门限群签名方案是基于身份密码体制的，能够满足一般数字签名的性质既保障消息的可用性、完整性及发方的不可否认性，门限思想的引入也使得方案具有门限群签名的特性12。4.1 群签名特性证明 秘密分发中，非群体成员选择随机数发送至TA时，TA将首先验证其身份，若属于某一群组之外，则不会公布其对应的，因此，非群体成员无法伪造有效份额密钥。而如果非群体成员没有有效的份额密钥，则在签名阶段，首先该成员无法通过TA的身份验证，其次也无法通过式(3)即份额密钥的验证，因而试图产生有效的份额签名是不可能的。因此，只有群体中成员才可以生成有效的部分签名，非群体成员无法伪造有效的部分签名，方案有群签名特性。4.2 门限特性证明 本群签名的秘密共享方案为门限访问结构，主密钥在n个参与者之间共享。若单个签名参与者的份额秘密泄露，因为是独立选取的，与没有任何关系，所以并不会影响主密钥的安全性，即；另外由于是相互独立选取的随机变量，所以多个份额秘密也不会反映出的任何信息，即。TA秘密分发后会删除，任意个参与者与TA合作，已知参数为个，而式(2)中含有个变量，所以参与者少于个则无法恢复出秘密；此后即使敌手拥有全部秘密分享组合，但所有形如式(2)的方程组合在一起，其系数矩阵的秩为，而变量个数为，所以即使拥有全部组合，没有TA参与也无法求解秘密。因此，的恢复必须要任意个参与者及TA的合作，若参与者少于个或没有TA参与均无法恢复出系统主密钥，更无法生成有效的门限签名。4.3 防冒充性证明 方案存在以下几种伪冒攻击。1) 在份额签名产生阶段，若攻击者截获的份额签名并试图用冒充而伪造其份额签名，则无法通过式(3)的验证。因为： 而通过，身份信息唯一确定，因此根据式(3)可知、及唯一确定份额签名，即与中的必须是一致的，从而保证签名时只能使用自己的份额秘密，攻击无法成功。2) 在份额签名产生阶段，若攻击者截获的并试图获得的份额秘密：此时仅已知或，试图获取份额秘密是困难的，它基于求解椭圆曲线上离散对数问题（ECDLP, ellipse curve discrete logarithm problem）的难解性。3) 若攻击者Pj获得消息及对应的合法群签名，试图以此伪造消息所对应的签名，而： 其中，是签名申请者的伪私钥，秘密分存，及均未曾在单点恢复。伪造的签名要通过式(7)的验证，必须要与中的相同：假设使得式(7)成立，而、及未知，仅从已知的推出是计算上不可行的，因其难度等同于求解计算性Diffie-Hellman问题。综上所述，任何成员或小组均不能假冒生成有效的部分签名或群签名，方案具备防冒充性。4.4 验证简单性证明 收方B通过式(7)和式(8)对签名验证。1) 对于式(7)，事实上：因此，式(7)成立说明来自于发方A，则B可相信A参与了签名，并且A对该签名是不可否认的。2) 对于式(8)，事实上：因此，式(8)成立，收方B可相信TA参与了签名，从而保障了消息的可用性和完整性。4.5 匿名性方案是匿名的，因为收方B对签名进行验证，由公开信息可知所对应的及，从而可验证式(7)是否成立；获取，由计算摘要即可验证式(8)是否成立。整个签名验证过程没有签名参与者的参与，不需要的公共参数及份额签名，因此不会泄漏的身份信息，B完全不知道该签名是由签名参与者群体中哪些成员所签，从而保障了算法的匿名性。4.6 可追查性证明 任何纠纷发生时均可请求可信中心TA的仲裁。式(8)成立说明签名中含有系统主密钥和A的伪私钥信息，因为除TA的公钥以外其他含主密钥信息的点都不可能得到，所以可信中心、签名参与者及签名申请者均参与了签名。而根据式(3)可知：部分签名与中的份额秘密必须一致，且要对公开信息负责，因此TA可据此追查出真实身份，且无法否认参加过签名。而对签名申请者A来说，A要对其公开信息负责，若验证方所提供的使得式(7)及式(8)同时成立，则说明A发出申请并参与了签名，TA可追查A的身份。4.7 强壮性在本方案中，当恶意成员为个时，根据门限特性可知，该k个成员合作不能获得系统主密钥的信息及任何消息的签名信息，能防范合谋攻击。方案中当且仅当个签名参与者与可信中心TA合作可恢复出系统主密钥，但系统不提供主密钥单点恢复的算法；另外当且仅当签名参与者、签名申请者及可信中心合作，才能产生对消息的合法签名。因而恶意成员为时仍然无法获取系统秘密参数。所以，由以上分析可以看出，该签名方案是强壮的。4.8 系统稳定性在本方案中，主密钥及份额密钥均是在有限域上随机选取的，因而主秘密空间与份额秘密空间相同，所以其秘密共享方案信息率为1，是一个理想方案。当剔除违规成员时，只需要在公共数据库中删除其公开信息即可；而当有新成员加入时，选择随机数向TA发出申请，TA同意后便在公共数据库中添加其公开信息，并预计算包含有该新成员的签名参与群的Hj即可。所以，在增删成员时，该方案只需少量改变系统参数，不需要改变其他成员参数，系统是稳定的。表1门限签名方案效率比较方案秘密分发签名验证可信中心每个Pi可信中心每个Pi份额签名验证签名重构文献7方案(t)Pa1Pa+ (t)Ea+ (t-1) Gm1Pa1Pa+1Pm+1Ad1Pa+2(t-1) Gm+1Ea(t)Pm+ (t-1)Ad2Pa+1Ea+1Gm本文方案S1(n)PmPm1Pm+ (t)Ad1Pm2Pa2Pm+1Ad5Pa+1GmS23Pa+1Gm5 效率分析以下对方案效率进行分析。表1中将本文所提门限群签名方案与文献7所提方案的效率进行了比较分析。这里的运算主要包括双线性对运算（Pa）、群上点乘和点加运算（Pm，Ad）、群上乘法运算和指数运算（Gm，Ea）。相对于这些运算，其他普通运算可忽略不计。前面分析表明，本方案中每次签名均进行秘密分发是没有必要的，而且增加了系统可信中心的负担，方案在第一次通信过程（简称S1阶段）中，因为要进行秘密分发，计算量稍大；但是在之后的通信过程（简称S2阶段）中运算量将明显减少。本文方案以t-out-of-n算法思想共享有限域上的数，因此秘密分发过程主要以群上点乘运算及有限域上的运算为主；而文献7方案秘密分发过程主要以双线性对运算、群上的指数运算及群上乘法运算为主，在运算时间和运算次数上均较本文方案高，在签名及验证阶段也有类似情况。基于双线性对的密码体制的时间消耗主要体现在计算双线性对上13，本文方案总的对计算次数在S1、S2阶段分别是7次和5次，而文献7方案共有对运算t+6次。另外在基于身份的密码体制中，可信中心是系统的核心，文献7及本文方案中可信中心均是在线的，要参与每一个秘密共享过程及门限群签名过程，易成为系统的瓶颈。由比较可知，文献7中可信中心在秘密分发及签名阶段的计算主要是双线性对运算，而本文主要以点乘运算为主，所以本文方案的可信中心可以较好地避免成为系统瓶颈。此外，在执行效率上，文献7门限存储用户签名私钥，因而该群组需要进行多次秘密共享过程；而本文方案门限存储主密钥，进而秘密分存用户签名私钥，则在该群组中仅需一次秘密共享过程。因而本文方案在效率方面还是有一定的优势。6 结束语本文基于双线性映射，提出了一个高效的门限群签名方案。该方案门限存储系统主密钥，可减少门限存储用户私钥所带来的多次秘密共享过程，有助于提高效率；并且因为系统主密钥是用户伪私钥的一部分，因此方案中用户的伪私钥事实上也是门限存储，系统整体安全性提高；另外方案在密钥分发过程中，份额秘密是由签名参与者随机选取，方案信息率为1是理想秘密共享方案。本文根据门限群签名的性质对该方案进行安全性分析，并对效率进行了对比分析，结果表明该方案是实用、安全、高效的门限群签名方案。参考文献：1DEMEDT Y, FRANKEL Y. Shared generation of authenticators and signaturesA. Advances in Cryptology- CRYPTO91 ProceedingsC. Berlin, Springer-Verlag, 1991. 457-469.2谢琪. 两种门限签名方案的密码学分析及其改进J. 通信学报, 2005, 26(7): 123-128.XIE Q. Cryptanalysis and improvement of two threshold signature schemesJ. Journal on Communications, 2005, 26(7): 123-128.3SHAMIR A. Identity-based cryptosystems and signature schemesA. Advances in Cryptology-CRYPTO84C. Springer-Verlag, 1984. 47-53.4BONEH D, FRANKLIN M. Identity-based encryption from the weil pairingA. Advances in Cryptology-CRYPTO01C. Springer-Verlag, 2001. 213-229.5BONEH D, LYNN B, SHACHAM H. Short signatures from weil pairingA. Advances in Cryptology-Asiacrypt01C. Springer, Heidelberg, 2002. 514-532.6CHEN X F, ZHANG F G, KIM K. A new ID_based group signature scheme from bilinear pairingsEB/OL. /2003/116, 2003-6-3/2003-8-6.7BAEK J, ZHANG Y. Identity-based threshold signature scheme from the bilinear pairingA. IAS04 Track of ITTC04C. Los Alamitos, 2004. 124-128.8HESS F. Efficient identity based signature schemes based on pairingsA. Selected Areas in Cryptography (SAC 2002)C. Berlin, Springer-Verlag, 2002. 310-324.9彭华熹, 冯登国. 一个基于双线性映射的前向安全门限签名方案J. 计算机研究与发展, 2007, 44(4): 574-580.PENG H X, FENG D G. A forward secure threshold signature scheme from bilinear pairingJ. Journal of Computer Research and Development, 2007, 44(4): 574-580.10SHAMIR A. How to share a secretJ. Communications of the ACM, 1979, 22(11): 612-613.11荆继武, 冯登国. 一种入侵容忍的CA方案J. 软件学报, 2002, 13(8): 1417-1422.JING J W, FENG D G. An intrusion CA schemeJ. Journal of Software, 2002, 13(8): 1417-1422.12王贵林, 卿斯汉. 几个门限群签名方案的弱点J. 软件学报, 2000, 11(10): 1326-1332.WANG G L, QING S H. Weaknesses of some threshold group signature schemesJ. Journal of Software, 2000, 11(10): 1326-1332.13BARRETO P, KIM H Y, LYNN B. Efficient algorithms for pairing-based cryptosystemsA. Advances in Cryptology-CRYPTO02C. Springer-Verlag, 2002. 354-368.刘宏伟（1975-），男，河南卫辉人，博士，深圳大学副教授，主要研究方向为密码学与信息安全。作者简介：谢维信（1941-），男，广东花都人，深圳大学教授、博士生导师，主要研究方向为模糊信息处理。喻建平（1968-），男，湖南沅江人，深圳大学教授、博士生导师，主要研究方向为密码学与信息安全。张鹏（1984-），女，湖北当阳人，深圳大学博士生，主要研究方向为密码学与信息安全。（上接第121页）16CDMA2000 Evaluation Methodology-Revision0R. 3GPP2 C. R1