可证安全的广播多重盲签名方案∗

杨青 张惠玲 吴成晶

（西安航空学院理学院西安710077）

可证安全的广播多重盲签名方案∗

杨青 张惠玲 吴成晶

（西安航空学院理学院西安710077）

对已有多重签名方案进行了安全性分析，提出了可证安全的广播多重盲签名方案。给出了改进的广播多重盲签名算法和验证算法，并证明了改进方案满足盲性和不可伪造性。比较和分析了改进方案的复杂度和安全性，改进方案的运算量减少了37.2n+447.8TML。改进方案所需运算量少，安全性高且易于实现。

超椭圆曲线；约化除子；盲签名；双线性对

Class NumberTP309

1 引言

多个人合作对同一份消息进行签名称为多重数字签名。Harn L在1989年提出了多重签名方案，改进了RSA数字签名方案［1］。在1994年，Harn L又提出了基于Meta-ElGamal方案的多重签名方案［2］。根据签名过程的不同，多重签名可分为有序多重签名和广播多重签名。有序多重签名是指签名者按照串行的顺序进行签名，广播多重签名对签名顺序没有要求，签名者可以同时进行签名，不必遵循先后次序。2005年Harn L提出了基于RSA的有序和广播多重签名方案［3］。近年来，人们在超椭圆曲线上建立密码系统［4］，并将双线性对用于多重签名方案［5～7］。

盲签名是指签名人在不知道消息内容的情况下对消息进行签名。它在电子投票和银行电子现金系统方面具有广泛的应用［8］。盲签名应满足以下几条性质：1）不可伪造性，任何第三方都不能伪造盲签名；2）盲性，签名人不知道所签文件或消息的具体内容；3）不可追踪性，签名人无法将有效的签名和被签名的消息联系起来。

本文对文献［7］的多重签名方案进行了改进，提出了高效的基于超椭圆曲线双线性对的广播多重盲签名方案。首先提出改进的广播多重盲签名方案，给出签名算法和验证算法。其次，证明了算法的正确性和安全性。最后，比较和分析了改进方案的安全性和复杂度，并应用于超椭圆曲线密码系统。改进算法克服了原方案不具有盲性的安全隐患，还保留了原方案的优点，并具有快速、高效且易于实现的特点。

2 双线性映射

定义1设G1为循环加法群，G2为循环乘法群，G1，G2的阶均为大素数q。设双线性映射e:G1×G1→G2，它满足以下三个性质：

1）双线性：如果对于任意P，Q，R∈G1，a，b∈，e(P，Q+R)=e(P，Q) e(P，R)，e(P+Q，R)= e(P，R) e(Q，R)和e(aP，bQ)=e(abP，Q)=e(P，abQ)= e(P，Q)ab。

2）非退化性：存在P∈G1，使得e(P，P)≠1。

3）可计算性：若P，Q∈G1，则e(P，Q)可在多项式时间内有效计算。

3 改进的广播多重盲签名

该算法由n个签名者A1，…，An，消息发送者I和签名验证者C组成。n个广播签名者A1，…，An可以同时进行签名，不必遵循先后次序。

3.1 系统参数的设定

设G1，G2分别是阶为q（q为大素数）加法群和乘法群。加法群G1的生成元为D，双线性映射e:G1×G1→G2。H1和H2是两个哈希函数：H1:{0，1}*×G1→Zq*，H2:{0，1}*→G1。系统公开参数Ω={G1，G2，H1，H2，e，q，D}。

3.2 签名者密钥的生成

n个签名者A1，…，An的公钥和私钥生成：Ai随机选取xi∈Zq*，计算公钥Yi=xiD，私钥为xi，(i=1，…，n)，若公钥相同，则重新选取xi∈Zq*。

3.3 签名的生成

对消息m产生一个广播多重盲签名，每个签名者Ai(1≤i≤n)作如下运算：

1）签名者Ai随机选取ti∈Z*q，计算Ti=tiD，并将Ti发送给消息发送者I。

2）消息发送者I随机选取αi，βi∈Zq*，首先计算αi-1∈Zq*，然后计算Ri=αiTi+βiYi+βiD，，h=H1(m，R)，h′i=αi-1h-αi-1βimodq， Q=H2(m∥R)，并将Q和h′i分别发送给签名者Ai，将Q和h发送给签名-验证者C。-

3）签名者Ai计算Wi=(ti-h′ixi)Q，并发送Wi给消息发送者I。-

4）消息发送者I验证等式：e(D，Wi)= e(Ti-h′iYi，Q)是否成立。若不成立，则消息发送者I向签名者Ai发出拒绝信息，或要求重新签名。若成立，则I计算Wi=αiWi+βiQ，，则(R，W)为消息m的盲签名，并发送(R，W)给签名验证者C。

3.4 签名的验证

3.5 正确性证明

证明：

4 方案分析

4.1 安全性分析

1）盲性分析。改进方案具有盲性，即签名人不能将消息与签名联系，从而判断出消息和对应的盲签名是否是他所签。改进方案中，给定任意一个有效的广播多重盲签名(m，R，W)，，在盲签名过程中产生的

i1， βi。总之，任何一个签名者Ai都不能得出αi， βi。改进方案中任何一个签名者Ai都不能将所签消息和对应的盲签名联系起来，从而改进方案具有盲签名的盲性。

2）方案具有不可伪造性。若攻击者企图冒充签名者Ai的签名-Wi=(ti-h′ixi)Q，需求解xi。这必需求解超椭圆曲线离散对数问题，在计算上是不可行的。若攻击者企图伪造消息m的盲签名(R，W)，由于攻击者无法得到αi，βi（见盲性分析），就不能计算出。所以，方案具有不可伪造性。

3）防止签名集体内部人员伪造盲签名。若签名集体内部的某个签名者想伪造Ai的签名，那他必须通过消息发送者I的验证。假设他可以获得αi，βi，但需要计算-Wi=(ti-h′ixi)Q，这需要求解xi，等同于求解超椭圆曲线离散对数问题，这在计算上是不可行的。所以改进方案能够防止签名集体内部人员伪造盲签名。

4.2 效率分析

本文的方案与文献［9］进行了效率比较，不同密码体制下的运算量转换关系（表1），选取亏格为2的超椭圆曲线，且特征为2。高效的超椭圆曲线除子加法和倍点运算的计算公式，参见文献［10～11］。除子加法运算的运算量为1I+3S+22M，并且除子倍点运算的运算量为1I+5S+22M，其中I，S，M分别表示有限域上的求逆、平方和乘法，并有1I= 30M，1S=0.8M。假定签名者人数均为n，改进方案总的计算量为(n+1)TBP+(8n+1)THEM+(7n-2)THEA，由表1中可得，转换后运算量为(922.8n+32.2)TML。文献［9］方案的总计算量为(4n+2)TEX，即转换后运算量为(960n+480)TML。因此，本文的运算时间量减少了(37.2n+447.8)TML，改进方案具有运算量少，效率高等优点。

表1 不同密码体制下的操作运算转换关系

5 结语

本文提出了基于超椭圆曲线双线性对的广播多重盲签名方案，广泛应用于匿名电子投票系统，电子现金交易、网络职称评审及电子银行系统等。比较和分析了改进方案的安全性和效率，与文献［9］的计算效率相比较，改进方案的运算量减少了(37.2n+447.8)TML。改进方案具有运算量低，高安全性能以及易于实现等优点。

［1］Harn L，Kiesler T.New schem for digital multisignatures［J］.Electronics letters，1989，25（15）：1002-1003.

［2］Harn L.New digital signature scheme based on discrete logarithm［J］.Electronics letters，1994，30（5）：396-398.

［3］Harn L，Lin CY，Wu C T.Structured multisignature algo⁃rithms［J］.IEE computers and digital techniques，2004，151（3）：231-234.

［4］Yang Siman，Wu Hongfeng，LI Jiyou.Access structures of hyperelliptic secret sharing schemes［J］.Finite Fields and Their Applications，2016，37（1）：46-53.

［5］Islam S.H.，Biswas G.P.A provably secure identity-based strong designated verifier proxy signature scheme from bi⁃linear pairings［J］.Journal of King Saud University--Com⁃puter and Information Sciences，2014，26（1）：55-67.

［6］Islam S.H.，Biswas G.P.Provably secure certificateless strong designated verifier signature scheme based on ellip⁃tic curve bilinearpairings［J］.Journal of King Saud Univer⁃sity--Computer and Information Sciences，2013，25（1）：51-61.

［7］Islam S.H.，Biswas G.P.Certificateless short sequential and broadcast multisignature schemes using elliptic curve bilinear pairings［J］.Journal of King Saud Universi⁃ty--Computer and Information Sciences，2014，26（1）：89-97.

［8］Li Fagen，Zhang Mingwu，Takagi Tsuyoshi.Identity-based partially blind signature in the standard model for electron⁃ic cash［J］.Mathematical and computer modeling，2013，58（1）：196-203.

［9］Debasis Giri，Srivastava P.D..An improved efficient mul⁃tisignature scheme in group communication systems［C］// Proceedings of the 2007 International Conference on Ad⁃vanced Computing and Communications（ICACC'07），2007：447-435.

［10］李明，孔凡玉，朱大铭.超椭圆曲线上Montgomery标量乘的快速计算公式［J］.软件学报，2013，24（10）：2275-2288. LI Ming，KONG Fanyu，ZHU Daming.Fast addition for⁃mulae for Montgomery Ladder scalar multiplication on hyperelliptic curves［J］.Journal of Software，2013，24（10）：2275-2288.

［11］Lange T.Formulae for arithmetic on genus 2 hyperellip⁃tic curves［J］.Applicable algebra in engineering，com⁃munication and computing，2005，15（5）：295-328.

Provably Secure Broadcast Blind Multisignature Scheme

YANG QingZHANG HuilingWU Chengjing
（Faculty of Science，Xi'an Aeronautical University，Xi'an710077）

Multisignature algorithm by reference is analyzed.Provably secure broadcast blind multisignature scheme is pre⁃sented.Specific signature and verification algorithms of Improved broadcast blind multisignature scheme are given.And the Im⁃proved scheme meets the properties of both blindness and non-forgery.The complexity and security of improved scheme are com⁃pared and analyzed.Improved scheme reduces computation costs 37.2n+447.8TML.Improved scheme has the advantages of low com⁃putation complexity，high security and easy to achieve.

hyperelliptic curve，reduced divisors，blind signature，bilinear pairings

TP309

10.3969/j.issn.1672-9722.2017.07.026

2017年1月10日，

2017年2月27日

国家自然科学基金（编号：11302158；11626182）；陕西省科技厅项目（编号：2013JM1019；2014K05-43）；陕西省教育厅项目（编号：14JK1310）；西安航空学院基金项目（编号：2015KY1218；2016GJ1004）资助。

杨青，女，硕士，讲师，研究方向：密码学。张惠玲，女，博士，副教授，研究方向：科技评价、信息安全。吴成晶，女，硕士，助教，研究方向：数论和密码学。