基于双线性对的多重数字签名方案

张彩娟，游林，2

（1. 杭州电子科技大学理学院，浙江 杭州 310018；2. 杭州电子科技大学通信学院，浙江 杭州 310018）

基于双线性对的多重数字签名方案

张彩娟1，游林1，2

（1. 杭州电子科技大学理学院，浙江 杭州 310018；2. 杭州电子科技大学通信学院，浙江 杭州 310018）

基于双线性对及3个困难性问题（IFP、DLP、CDHP）提出了新的多重数字签名方案。新方案将广播多重数字签名中签名快速的优点应用到按序多重数字签名，改变签名的一般机制，使签名者同时进行签名；然后，由可信任第三方验证签名，验证通过后发送给验证者；最后，由验证者将签名转变为按序的。同时，分析了方案在3个困难问题、防伪攻击和抗部分成员合谋攻击方面的安全性能。新方案具有计算量少、算法简单、获取签名速度快、安全性强等优点。

多重数字签名；按序签名；广播签名；安全性

1　引言

随着互联网的高速发展，人们希望通过电子设备就能实现远距离的、快速的交易。自 1976 年Diffie和Hellman［1］首次提出公钥密码体制的概念后，数字签名随之产生，并开始在商业通信系统中得到广泛应用。实际情况中，有时需要多个用户对同一消息进行签名，这类需要多个实体对同一份合同进行签名的电子对应物就是多重数字签名。

自引入多重数字签名［2］的概念后，不同的多重数字签名方案相继被提出。文献［3∼5］提出基于离散对数困难性问题的多重数字签名；文献［5］在离散对数困难性的基础上把整数分解问题也应用到签名里，使签名方案更安全、可靠；文献［6∼8］给出关于散列函数的发展和其在多重签名中的应用；文献［9］把盲签名以及代理签名运用到多重签名中形成新的方案；文献［10，11］中对椭圆曲线密码体制的运用和改进，使多重签名方案更加多样化；文献［12］中提出的针对基于离散对数多重签名方案的攻击和文献［13］提出的基于椭圆密码体制的签名方案的攻击，使多重签名方案更加完善、安全。以上文献各有优缺点，但其设计思想值得借鉴。

根据多重签名顺序和过程的不同，可分为按序多重签名和广播多重签名。文献［6，14］给出基于同样问题的按序和广播2种多重签名方案，通过比较可以发现，按序多重签名方案耗时更久些，对重大性和紧急性事件有较大影响。例如，在按序多重数字签名体系中，当消息发送给签名者时，若签名者未及时签名，则后面的签名者也无法对消息进行签名。依此下去，每个签名者都耽误一点时间，则最后验证者收到签名的时间就会延长很久。针对按序多重签名方案这一缺点，本文将按序和广播 2种多重签名在某种程度上结合起来，同时又结合离散对数困难性问题、整数分解问题以及Diffie-Hellman计算问题来构造新方案。与文献［5］的按序多重数字签名方案相比，本方案获取签名速度更快、运算量更少、安全性更高。

2　基础知识

2.1 对称双线性对

2.2 困难问题假设

定义1 大整数分解问题（IFP）。已知2个大素数p， q，求n=pq是容易的，但若由n来求p 和q是困难的，这就是大整数分解困难问题。

定义3 Diffie-Hellman计算问题（CDHP）。对于任意的给出，计算出abP且满足

2.3 基于SDLP和IFP的多重数字签名方案

文献［5］提出基于SDLP和IFP的按序多重数字签名方案。简述如下。

2） 签名算法。

3）签名的验证

3　新的多重数字签名方案

3.1系统的建立

3.2签名算法

3.3签名的验证

这样形成的最终签名长度是固定的，与签名者的个数无关。

上述按序签名方案是在文献［5］的基础上进行改进的，与文献［5］相比，本文引入了双线性对并选取了不同的ni，使方案的安全性更高；同时，又改变了按序签名的体制，使签名经过了可信任第三方和验证者双重的验证，更加真实可靠；且新方案中可信任第三方产生的私钥量较小，节省了密钥存储空间；此外，新方案在整个签名生成的过程中运算量较小、获取签名速度快，签名的长度也是固定的，不随签名者的变化而改变。

4　效率及安全性分析

4.1效率分析

本文提出的新方案与文献［5］在运算量和签名时间上的比较如表1所示。

Ui开始到签名结束所消耗的时间， T△表示从消息发出后到所有签名结束需要的总时间。

由表1可知，本文方案在签名所需总时间和签名生成过程中所需运算量上都占有极大优势。显然，新方案获取签名的速度更快、运算量更少、效率更高。

4.2安全性分析

4.2.1困难问题

表1　2个方案运算效率对比

DLP：因为 e（ g， g）是可以由公共参数求得的，同时是公开的，所以，任何人想要通过 e（ g， g）和）来找到，使成立是不可能的，因为寻找的过程实际就是解决离散对数问题的过程。

4.2.2防伪攻击

4.2.3抗部分成员合谋攻击

本文方案在一定程度上将按序多重签名与广播多重签名结合起来，先由每个签名者立地进行签名，然后，将交给可信任第三方C进行验证，验证通过后由C将签名直接发送给验证者。验证者接收到所有签名后，按照预定的顺序对签名进行逐一验证，验证成功后再统一形成总的签名正是由于该算法中签名者进行签名时是各自独立的，且每个签名要经过C的验证才能发送给验证者，所以，整个方案中没有通过签名者相互合作而形成的公私钥，即部分成员之间是无法通过合谋来伪造任何东西的。

从上面安全性的分析可以看出，双线性对的引入、不同ni的选取以及新结构的构造使新方案更安全，防攻击能力更强。

5　结束语

针对按序多重数字签名方案获取签名速度慢的特点，本文改变了传统按序签名的体制，将按序和广播签名在一定程度上结合起来，形成新的按序多重签名体制。新方案具有运算量少、算法简单、获取签名速度快、安全性强等优点，同时，方案中新的构造方法为签名节省了大量时间，极具推广性，是具有发展潜力的多重数字签名方案。

［1］DIFFIE W， HELLMAN M E. New directions in cryptography［J］. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654.

［2］ITAKURA K. A public-key cryptosystem suitable for digital multi-signatures［J］. Nec Research & Development， 1983， 71（1）：474-480.

［3］LU L R， ZENG J J， KUANG Y H， et al. A new multi-signature scheme based on discrete logarithm problem and its distributed computation［J］. Chinese Journal of Computers， 2002， 25（12）：1417-1420.

［4］BURMESTER M， DESMEDT Y， DOI H， et al. A structured elgamal-type multi-signature scheme［C］//The 3rd International Workshop on Practice and Theory in Public Key Cryptography. c2000：466-483.

［5］DÍAZ R D， ENCINAS L H， MASQUÉ J M. A multi-signature scheme based on the SDLP and on the IFP［C］// International Conference on Computational Intelligence in Security for Information Systems. c2011：135-142.

［6］ZHANG J H， WEI Y Z， WANG Y M. Digital multi-signatures scheme based on RSA［J］. Journal of China Institute of Communications， 2003， 24（8）： 150-154.

［7］U.S. Department of Commerce. Secure Hash standard-SHS： federal information processing standards publication 180-4［M］. Create Space Independent Publishing Platform， 2012.

［8］NOROOZI E， DAND S M， SABOUHI A， et al. A new dynamic hash algorithm in digital signature［J］. Advanced Machine Learning Technologies and Applications， 2012， 322（12）： 583-589.

［9］GUO W， ZHANG J Z， LI Y P， et al. Multi-proxy strong blind quantum signature scheme［J］. International Journal of Theoretical Physics， 2016， 55（3）： 1-13.

［10］LI F， XUE Q. Two improved proxy multi-sigvcdnature schemes based on the elliptic curve cryptosystem［M］//Computing and Intelligent Systems. Berlin Heidelberg： Springer， 2011： 101-109.

［11］CHOUKSEY R， SIVASHANKARI R， SINGHAI P. ECDLP based proxy multi-signature scheme［M］//Advances in Computing and Information Technology. Berlin Heidelberg： Springer， 2012： 71-79.

［12］HAN X X， WANG G P， BAO F， et al. An attack to multi-signature schemes based on discrete logarithm［J］. Chinese Journal of Computers， 2004， 27（8）： 1147-1152.

［13］LIU Y， LUO P， DAI Y Q. Attack on digital multi-signature scheme based on elliptic curve cryptosystem［J］. Journal of Computer Science & Technology， 2007， 22（1）： 92-94.

［14］WANG X F， ZHANG J， WANG S P. Digital multi-signature scheme and its security roof［J］. Chinese Journal of Computer， 2008， 31（1）：176-183.

Digital multi-signature scheme based on bilinear pairing

ZHANG Cai-juan1， YOU Lin1，2

（1. College of Science， Hangzhou Dianzi University， Hangzhou 310018， China；2. College of Communication， Hangzhou Dianzi University， Hangzhou 310018， China）

Based on bilinear pairing and three complicated problems， a new digital multi-signature scheme was proposed. In the new scheme， the advantage of fast signature in broadcasting digital multi-signature was applied to sequential digital multi-signature. By changing the general mechanism of signature， signing could be done simultaneously by the signers. Then， the signature was sent to verifier after it was verified by trusted third party. The transformation from concurrent signature to sequential signature was finally realized by the verifier. The security capabilities in three complicated problems， anti-fake attack and anti-conspiracy attack from some members of the new scheme were analyzed. Proposed scheme has many advantages over the old ones， such as fewer calculation， simpler algorithm， faster signing， higher security.

digital multi-signature， sequential signature， broadcasting signature， security

Zhejiang Province Science and Technology Innovation Program （No.2013TD03）

TP309

A

10.11959/j.issn.2096-109x.2016.00061

2016-05-13；

2016-06-04。通信作者：张彩娟，908332087@qq.com

浙江省重点科技创新团队基金资助项目（No.2013TD03）

张彩娟（1993-），女，山西大同人，杭州电子科技大学硕士生，主要研究方向为信息安全与密码学。

游林（1966-），男，江西临川人，杭州电子科技大学教授，主要研究方向为信息安全与密码学。