新的基于双线性对的门限代理签名方案.doc

第8A期冯明君等：新的基于双线性对的门限代理签名方案47新的基于双线性对的门限代理签名方案冯明君, 何明星(西华大学 数学与计算机学院, 四川 成都 610039)摘 要：针对现有的门限代理签名方案中所存在的合谋攻击,提出了一个基于双线性对的(t,n)门限代理签名方案。该方案不仅能抵抗合谋攻击,而且可以根据原始签名人的需要,方便地回收部分代理人的签名权。同时,如果部分代理签名人的代理签名密钥泄露,可以方便地更换成新的密钥。关键词：双线性对；门限代理签名；合谋攻击中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2007)8A-0043-05New threshold proxy signature scheme from pairingsFENG Ming-jun, HE Ming-xing(School of Mathematics and Computer Engineering, Xihua University, Chengdu 610039, China)Abstract: A new threshold proxy signature scheme from pairings is proposed aiming at keeping from conspiracy attack, that is , any t (t is threshold value) or more malicious proxy signatures may work together to reconstruct the secret polynomial of the proxy group and derive the secret keys of other members in the proxy group, consequently they can impersonate some other proxy signers to generate a valid threshold proxy signature. The new scheme can withstand the conspiracy attack. Furthermore, the proxy signers proxy signing capability can be revoked and the partial proxy signers proxy signing secret key can be changed conveniently by the original signer.Key words: bilinear pairings; threshold proxy signature; conspiracy attack1 引言收稿日期：2007-06-25基金项目：国家自然科学基金资助项目(60473030)；教育部重点基金资助项目(205136)；四川省科技厅重点基金资助项目(05JY029-131)Foundation Items: The National Natural Science Foundation of China (60473030); The Key Projects Foundation of Ministry of Education of China (205136); The Foundation of Science and Technology Agency of Sichuan Province (05JY029-131)1996年,Mambo等人提出了第一个代理签名方案1,利用代理签名机制,代理签名人可以代表原始签名人对消息签名。自代理签名概念提出以来,相继出现了各种各样的代理签名方案,而其中的门限代理签名方案是一个较重要的数字签名方案，近几年来人们对它进行了广泛研究。目前很多门限代理方案中都存在着合谋攻击的问题,如文献2,3，同时在这些文献中,原始签名人一旦把签名权委托给代理人,代理人就具有永久代理签名权,这对原始签名人很不利，而且对现有的门限代理签名方案来说,如果某个部分代理人的代理签名密钥泄露后,要更改部分代理签名密钥也是件复杂的事。针对以上问题,本文提出了一个基于双线性对的门限代理签名方案。该方案不仅满足门限代理签名的性质,而且能抵抗合谋攻击；同时具有如下性质：根据原始签名人的需要方便地回收代理签名权；根据代理签名能辨认出代理签名人的身份；如果代理签名群中某个成员的代理签名密钥被泄露,可以很方便地更改代理签名人的签名密钥。2 预备知识2.1 双线性对4设为阶为q，生成元为P的循环加法群，是一个阶为q的乘法循环群。其中q是一个大素数。表示均匀随机分布于中。双线性对是指满足下列性质的一个映射:G1G2。 1) 双线性P, Q, RG1, a, bR(P,Q+R)=(P,Q)(P,R)(P+Q,R)=(P,R)(Q,R)(aP,bQ)=(abP,Q)=(P,abQ)=(P,Q)ab2) 非退化性 对任何PG1，存在QG1，使得(P,Q)1。3) 可计算性对所有的P,QG1，存在有效的算法计算(P,Q)。与双线性对有关的数学问题： 离散对数问题(DLP)：给定P和Q，且，计算一个整数n，使得Q=nP。 判定Diffie-Hellman问题(DDHP):对,而言, 给定.判定是否存在。 计算Diffie-Hellman问题(CDHP)：对,而言，给定,计算。 Gap Diffie-Hellman问题(GDHP)：在群中，当DDHP计算容易，但是CDHP计算困难时，称群为Gap Diffie-Hellman(GDH)群。2.2 Shamir (t,n) 门限秘密分享方案5一个(t,n)秘密分享方案是指把密钥K按某种方式分配给n个用户，使得n个用户中任意t个或多于t个用户一起合作能够恢复密钥K，任意少于t个用户一起合作不能得到关于密钥K的任何信息。Shamir方案是基于有限域上的Lagrange插值公式的。方案如下：1) 选择大素数q，建立一个GF(q)上的（t1）次多项式：且要满足：，(=1,t1)。2) 对密钥K的共享：设n个用户的ID号为：(=1,n)，则每个用户的共享秘密份额为：。3) 恢复密钥K：只要有至少t个用户愿意合作贡献出他们的秘密份额，则可用Lagrange插值公式的恢复K。由Lagrange插值公式知所以的常数项便为K的值，即：3 新的门限代理签名方案本节提出新的基于双线性配对的门限代理签名方案。本方案需要一个系统权威SA，他负责定义公开参数。设Alice为原始签名人，为n个人组成的代理群，GP为群管理员，负责选取群私钥，验证部分代理签名的有效性，并用有效的部分代理签名生成最终的代理签名。整个方案由如下几个部分组成。3.1 系统初始化SA选择2个循环群：，生成元为P，阶为q;一个双线性映射：:G1G1G2;三个安全单向Hash函数：, ,。设原始签名人Alice的密钥对为,其中为私钥，为公钥；，代理人的密钥对为,其中为私钥，为其公钥，为其身份标识，且。群管理员GP任选作为私钥，并计算作为群公钥。假设所有公钥都通过了CA认证，群管理员是可信的。是原始签名人Alice任意选择的一个阶为q的生成元6，为代理委任状，它包括了门限t的值，原始签名人、代理签名人身份，待签名的消息类别，代理有效期等信息。SA公布系统参数和公钥()。3.2 分存秘密共享GP任选(t1)次多项式： ,其中(=1,t1)。从Alice的公告栏上获得后计算, (1)，(2)(3)然后发送,并在公告栏NB上公布：（）。3.3 代理密钥生成原始签名人Alice先任选，计算：(4)再随机选择一个(t1)次多项式，其中，(i=1,t1)。并计算(5)（）(6)(=1,t1)，(7)然后发送Pi ，并在公告栏NB上公布mw,A,以及Cj(=1,t1)。每个代理人Pi收到Si,后，先计算(8)(9)再验证和(10)是否成立。如果都成立，则每个Pi计算(11)作为他的部分代理签名密钥。3.4 代理签名生成设为任意t个愿意合作产生代理签名的人组成的群，M为待签名消息，则他们按以下步骤生成代理签名：每个Pi验证M是否符合mw中的要求，若符合，进行下步操作；每个Pi任选tiG1，计算：(12)然后发送GP收到来自成员Pi的后，GP先计算(13)然后验证：(14)是否成立。如果对所有的都通过验证，则GP计算(15)则t个成员合作产生的对消息M的最终代理签名为。3.5 验证代理签名：收到代理签名后，验证人验证(16)是否成立，若成立接收签名为有效的代理签名。3.6 回收代理签名权当原始签名人Alice想收回某个代理人Pi的签名权时，Alice把Pi的身份标识信息IDi换成其他人的身份信息，并更新公告栏NB上的mw。群管理GP从公告栏上获得新的后，计算出新的Si，并刷新NB上的Vi。若Pi仍用原来的部分代理签名密钥产生部分代理签名Upi时，他将通不过GP的有效性验证式因为，更新后的，与原来的，就不相等。验证式不成立，这样GP就知道的权力也被回收，的部分代理签名无效。3.7 更改代理群成员的代理签名密钥如果代理群中某个成员的部分代理签名密钥di被泄露，则他向原始签名人和GP发出更换代理密钥请求。原始签名人Alice收到请求后，在NB上更新的值，再为代理群中每个成员计算方案中对应的值；同时GP获得更新后的值后，也重新为群中每个成员计算方案中对应的值，并更新他的NB。这样原始签名人Alice和群管理员GP都不用再重新选择自己的多项式。与一般的门限方案相比，本方案避免了重新选择多项式或GP重新注册群密钥的麻烦。3.8 添加新成员到代理签名群当Alice想添加某个新成员到代理签名群时，他直接分配新用户身份标识为IDn+1，并将计算出的相应的发给用户，同时刷新NB的mw信息。同样，GP获得新用户的身份标识后计算出相应的给用户，并在NB上添加。那么新用户就可以作为合法群成员了，如果需要也可以参加代理签名。3.9 更换整个代理群当Alice想把代理权授给另一个代理群时，他同时更新NB上的和即可。更新之后，Alice和GP可以安全的给新群的每个成员分配相应的信息，而以前群中任何成员再无法代表Alice产生有效的代理签名。4 方案的安全性分析4.1 正确性对式(8),式(9)的正确性推导:由式(3)知： 从而可得式(8)：成立。同理也可得式(9)成立。对式(10)的正确性推导：因为由式(5)知：，故代入式(4)和式(7)后便得式(10)对式(14)的正确性推导：因为由式(12)知： 将di代入后有： 。对式(16)的正确性推导= =4.2 强不可伪造性因为每个代理群成员的部分代理密钥di包含了Pi的私钥xpi，所以没有代理签名人Pi的私钥，任何第三方和原始签名人均不能冒充Pi生成有效的部分代理签名。4.3 不可否认性一旦代理群成员合作代表原始签名人产生了有效的代理签名，他就不能对任何人否认他参与了门限代理签名，因为部分代理私钥di中包含了他自己的私钥xpi，所以在验证签名有效性时要用到他的公钥，故他不能否认自己参与了代理签名。4.4 可区分性每个代理人的代理私钥di和他自己的私钥xpi是不相同的，所以签名验证者可区分出每个人的正常签名和代理签名。4.5 可识别性从验证式知，要验证签名的有效性，就要用到每个部分代理人的公钥Ypi，代理群的公钥YG和原始人的公钥YA，每个人的身份信息都以公钥形式包含在委任状中，故验证人可以明确知道是来自哪个代理群的哪些成员代表了哪个人产生了该代理签名。4.6 抗合谋攻击性即使有至少t个恶意代理人相互泄露了他们的si和，从而恢复了秘密多项式f1(x)和f2(x)，进一步得到了其他成员的sj和 ()，但他们不能知道其他成员的私钥，从而不能得到其他人有效的代理私钥。故本方案能抵抗群内成员的合谋攻击。4.7 代理密钥丢失后的安全性保障普通的门限方案的安全只考虑到方案本身的抗密码分析能力，很少考虑代理密钥丢失的情况。本方案中，如果某部分代理群签名成员发现自己的代理密钥以丢失，可以根据方案中3.7节的方法来方便更改自己的代理密钥，而使得用旧的代理密钥再生成的部分代理签名Upi通不过GP的有效性验证，这样就保护了该代理人的利益。5 结束语本方案通过引入一个生成元，能够在不重新构造多项式的情况下，方便地更换代理签名密钥；在代理签名密钥di生成的时候，通过引入部分代理人的私钥xpi，从而能抵抗代理群内的合谋攻击；本门限代理签名方案是基于双线性对建立的，根据代理签名能辨认出是来自哪个代理群的哪些代理签名人代表谁产生的该代理签名。当然，方案主要考虑的是抗合谋攻击能力和更换代理密钥以及回收代理权的方便性，没有太多的对计算代价做深入研究，有待进一步从计算代价上优化。参考文献：1MAMBO M, USUDA K, OKAMOTO E. Proxy signatures: delegation of the power to sign message J. IEICE Trans on Fundam, 1996, 79(9): 1338-1354. 2KIM S, PARK S, WON D. Proxy signature, revisited A. ICICS97, Lecture Notes in Computer ScienceC. Springer,Berlin, l997. 223-232.3HSU C L, WU T S ,WU T C. A new nonrepudiable threshold proxy signature scheme with known signersJ. Jou