孙　玉，刘贵全

(1.中国科学技术大学 计算科学与技术学院，安徽 合肥 230027；2.安徽职业技术学院 信息工程系，安徽 合肥 230051)



安全高效无证书有序多重签名方案

孙玉1,2，刘贵全1

(1.中国科学技术大学 计算科学与技术学院，安徽 合肥 230027；2.安徽职业技术学院 信息工程系，安徽 合肥 230051)

摘要：无证书密码体制(certificateless cryptography, CLC)将用户私钥拆分为部分私钥和秘密值，其中部分私钥由密钥生成中心(key generator center， KGC)生成，而秘密值由用户自己选定，从而解决了基于身份密码体制所固有的密钥托管问题。此外，由于用户公钥由秘密值决定，无需认证中心(certificate authority，CA)对用户的公钥证书进行管理，解决了传统密码体制的证书管理问题。有序多重签名可用于电子政务和电子商务系统实现公文的逐级审批发布，提高认证效率。将有序多重签名和无证书密码相结合，提出一种安全高效的无证书有序多重签名方案，多重签名的长度及验证时间均与签名者个数无关，是紧致的无证书有序多重签名方案。方案使用较少的双线性对且只有一个签名消息，具有较高的计算效率和通信效率。证明了方案在随机预言模型(random oracle model，ROM)下具有不可伪造性。

关键词：无证书密码体制；多重签名；随机预言模型(ROM)

0引言

无证书密码体制能够解决传统公钥密码体制和基于身份密码体制的不足，即不存在证书管理和密钥托管问题。Al-Riyami等[1]首次提出无证书密码学的概念，用户私钥包括2部分：①部分私钥，它由密钥生成中心(key generator center， KGC)生成；②秘密值，它由用户自己选择，而公钥则是用户通过使用秘密值来产生。由于密钥管理中的系列重要问题可以通过无证书密码体制有效解决，因此,无证书签名方案受到了越来越多的关注和研究，具有各种属性的无证书签名相继被提出。

通过对多重签名的研究可知，多个参与者可以对同一个消息进行签名。多重签名的概念由Itakura等[2]提出，依据所在环境，可分为有序多重签名和无序多重签名，它们的区别在于有序多重签名要求签名者对消息进行签名时要以特定的顺序。HARDJONO 等[3]提出基于离散对数的多重签名方案。多重签名方案的安全模型最早见于由Micali等[4]所发表的文献，后面很多研究人员也相继提出多种多重签名方案[5-7]。但这些签名方案大部分是基于传统公钥密码体制[2-4]，或基于身份密码体制[6-7]，不适用于大规模分布式网络。

目前已有学者对无证书的多重签名方案进行了研究，Zhang等[8]提出的方案，即签名长度随签名者个数的增加而增加，不满足紧致性要求。ISLAM等[9]提出了紧致性的多重签名方案，但在安全性方面并没有给出有效的证明。秦艳琳等在文献[10]中提出紧致的无证书有序多重签名方案，然而该方案的安全性证明存在不足[11]。随后文献[11]提出一个无证书多重签名方案。该文在已有研究的基础上[12]，构造出一个安全高效的无证书有序多重签名方案。最后证明方案在随机预言模型(random oracle model，ROM)下具有不可伪造性。

1预备知识

1.1k-CAA困难问题

1.2无证书有序多重签名方案的定义和安全模型

1.2.1方案定义

无证书有序多重签名方案由以下算法[11]构成，包含成员KGC，签名者Ni(i=1,2,…,n)和验证者V。

1)Setup：生成系统参数。KGC将安全参数k作为初始参数, 生成主密钥s和系统参数Params。

2)ParKeyGen：提取部分私钥。KGC验证Ni(i=1,2,…,n)的身份标识IDi后，为每个用户生成Ni的部分私钥Di。

3)UserKeyGen：生成用户密钥。用户Ni生成自己的秘密值xi和公钥Pi。

4)PriKeyGen：生成用户私钥。用户Ni输出自己的私钥si=(xi,Di)

5)Sign：签名。用户Ni(i=1,2,…,n)以一定的次序K，依次验证上一签名者的部分签名σi-1，然后计算签名消息σi，作为Ni对消息的部分签名。

6)Verify：验证。验证者对消息m的签名σn进行验证，判断输出签名是否有效。

1.2.2安全模型

假设存在两类攻击者：AⅠ，模拟任意参与者，他们可以替换任意签名者的公钥但不知道系统主密钥；AⅡ，模拟恶意KGC，它不能替换签名者的公钥但知道系统主密钥。方案的安全模型[11-12]如下。

1)系统参数设置：挑战者D得到系统参数Params和系统主密钥s。如果攻击者A=AⅠ，D将Params发送给A。如果A=AⅡ，将Params和s发送给A。

2)询问：A已经获得k个签名者的完整私钥。随后A询问Hash函数，用户完整私钥，公钥以及执行公钥替换询问，以期获得未被攻破签名者的部分签名。

2具体方案

高效无证书多重签名方案的具体构造如下。

4)PriKeyGen：Ni(i=1,2,…,n)输出si=(xi,zi)作为其完整私钥。

5)Sign：签名。

①签名者Ni对消息m进行签名。

a)计算

(1)

(1)式中，K={ID1,ID2,…,IDn}；符号“a‖b”表示比特串a和b的联结。

b)计算

(2)

(2)式中，σ1是Ni对m的部分签名。

②签名者Ni对Ni-1发来的签名消息(m,σi-1)进行验证后再签名。

a)验证：Ni构造Cj。计算

Vj=Hj(m‖IDj‖K‖Pj‖Rj‖Q),

(3)

验证等式

(4)

是否成立。若成立，则对签名消息(m,σi-1)进行签名，否则，终止算法。

b)计算

(5)

signi=(Vixi+zi)-1P

(6)

(7)

其中，(7)式是Ni对m的部分签名。

c)签名者Ni(i=1,2,…,n)对消息m的完整签名为(m,σn)。

6)Verify：验证者对签名消息(m,σn)进行验证。

验证者构造Ci，计算

Vj=Hj(m‖IDj‖K‖Pj‖Rj‖Q),1≤i≤n

(8)

验证等式

(9)

是否成立。若成立，则(m,σn)是正确的签名。

3方案分析

3.1正确性

证明假设由签名方案得到多重签名(m,σn)，则

(10)

3.2抗伪造性

可以证明在RO模型下，对任何攻击者来说本方案都是不可伪造的。

定理1在RO模型下，如果AⅠ能够以不可忽略的概率伪造出多重签名，则AⅠ能够解决k-CAA问题。

证明攻击者AⅠ已经攻破了n-1个签名者，假设AⅠ已知N1,…,Nn-1的私钥，为了攻破本方案，AⅠ必须成功地伪造第n个签名者Nn。如果AⅠ能以不可忽略的概率ε攻破无证书多重签名方案，则挑战者D能将AⅠ作为子程序最终解决k-CAA问题，即如果D已获得参数{P,W=sP,h1,…,hk,(s+h1)-1P,…,(s+hk)-1P}，那么最终将能输出(s+h)-1P，h∉{h1,…,hk}。

5)替换公钥查询：AI替换IDi的公钥。AⅠ输入(Pi,Ri)作为IDi新的公钥。

7)签名查询：AⅠ询问(mi,IDi)的签名，IDi的秘密值xj。考虑如下情况。

①i≠n，D输出签名σj=(zi+βjxj)-1P；

②i=n，如果hj∉{h1,…,hk}，D停止输出。否则，D输出σj=(αn)-1(s+hj)-1P。易知以上2种情况下，σj是合法签名。

最后，AⅠ输出一个有效的签名(IDn,mn,σn)，IDn的公钥为(Pj,Rj)。如果hj∈{h1,…,hk}，D停止执行。否则得到e(signn,Rn+αnQ+βjPj)=e(σn/σ1,…,σn-1,αnW+αnhjP)，因为AI能够询问除了IDn之外所有用户的私钥，所以AI能够计算出σ1,…,σn-1，signn=σn/σ1,…,σn-1。那么对于hj∉{h1,…,hk}，D能输出(s+hj)-1P=αnσn/σ1,…,σn-1。从而得知，如果AI能伪造有效的多重签名，那么D能够解决k-CAA困难问题。

定理2在RO模型下，如果AⅡ能够以不可忽略的概率伪造出多重签名，则D能够解决k-CAA问题。

证明定理2的证明与定理1的证明过程类似，本文将不再给出。

3.3效率分析

与文献[10-11]类似，在效率分析时将不考虑Hash函数这样的预计算，而着重考虑双线性对操作。首先，一次双线性对操作的计算时间是标量乘法的21倍，该文方案在整体验证时只需要2次双线性对操作，因此，计算是高效的；其次，该文方案最终的多重签名为σn，与单用户签名一样且只有一个签名消息，因此，占用较少的通信代价；最后，方案的签名长度与签名者个数无关，是紧凑的多重签名方案。

4结束语

有序多重签名在电子政务和电子商务领域具有重要的实际应用价值，无证书密码体制能够解决证书管理问题和密钥托管问题，有必要对无证书多重签名进行研究。提出一种高效无证书有序多重签名方案，并在随机预言模型下证明方案的安全性等价于求解k-CAA困难问题。通过安全性和效率分析可知，提出的无证书多重签名方案是安全高效的。下一步将基于已有的无证书多重签名方案设计适用于电子商务系统的身份隐私保护方案。

参考文献：

[1]RIYAMI A S S, PATERSON K G. Certificateless public key cryptography[C]//Proc of Asiacrypt 2003.Berlin：Springer-Verlag, 2003:452-473.

[2]ITAKURA K, NAKAMURA K.A public-key cryptosystem suitable for digital multisignatures[R].[s.l.]:NEC Research & Development,1983, 71:1-8.

[3]HARDJONO T,ZHENG Y.A practical digitalmultisignature scheme based on Discrete Logarithms[C]∥Jennifer Seberry.Advances in Cryptology-AUSCRYPT’92,LNCS718.Berlin：Springer-Verlag,1992:122-132.

[4]MICALI S, OHTA K, REYZIN L. Accountable Subgroup multisignatures[C]//Pierangela Samarati.Proc of the 8th ACM Conf on Computer and Communications Security.New York：ACM，2001:245-254.

[5]于佳, 郝蓉, 孔凡玉.标准模型下的前向安全多重签名:安全性模型和构造[J].软件学报,2010,21(11):2920-2932.

YU J, HAO R, KONG F Y.Forward secure multi-signature in the standard model:security model and construction[J].Journal of Software,2010,21(11):2920-2932.

[6]HARN L, REN J. Efficient identity based RSA multisignatures[J].Computers & Security,2010,27(3):12-15.

[7]LU S, OSTROVSKY R, SAHAI A, et al.Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles[J].Journal of Cryptology，2013,26(2):340-373.

[8]ZHANG L, ZHANG F T.A new certificateless aggregate signature scheme[J].Computer Communications,2009,32(6):1079-1085.

[9]ISLAM S H,BISWAS G P.Certificateless strong designated verifier multisignature scheme using bilinear pairings[C]//Sabu M Thampi.Proceedings of the International Conference on Advances in Computing,Communications and Informatics.Chennai,New York：ACM,2012,540-546.

[10] 秦艳琳,吴晓平.高效的无证书有序多重签名方案[J].通信学报,2013,34(7):105-110.

QIN Y L, WU X P. Efficient certificateless sequential multi-signature scheme[J]. Journal on Communications,2013,34(7):105-110.

[11] 许艳，黄刘生，田苗苗，等. 可证安全的高效无证书有序多重签名方案[J].通信学报,2014,(11):126-131.

XU Y, HUANG L S, TIAN M M, et al.Provably secure and efficient certificateless sequential multi-signature scheme in random oracle model[J].Journal on Communications, 2014,(11):126-131.

[12] TIAN M M, HUANG L S, YANG W. Practical certificateless short signature scheme[J].International Journal of Electronic Security and Digital Forensics,2014, 6(3): 204-218.

Secure and efficient certificateless sequential multi-signature scheme

SUN Yu1,2，LIU Guiquan1

(1. School of Computer Science and Technology,University of Science and Technology of China, Hefei 230027, P.R.China;2. Departmen of Information Engineering,Anhui Vocational and Technical College, Hefei 230051, P.R.China)

Abstract:In the certificateless cryptography(CLC), the user's private key is split in partial private key and secret value. The partial private key is generated by the key generator center (KGC), while the secret value is chosen by the user itself, and the certificateless cryptography solves the key-escrow problem in the ID-based cryptography(IBC). Furthermore, the user's public key is generated by the secret value, and there is no certificate authority(CA) to manage the public key certificate. The CLC is also used to eliminate certificates in traditional public key cryptography. The sequential multi-signature scheme could resolve the problem of authentication of recommendation information transmitted through trust train, and improve the efficiency of the verification. We combine the certificateless cryptography with the sequential multi-signature, and propose a secure and efficient certificateless sequential multi-signature scheme, the size of the multi-signature and the time for verification are independent on the number of signers. The scheme uses less bilinear pairing and generates only one signature message, which has lower computation cost and communication cost. Finally, we prove that the scheme can resist the forgery attack under the random oracle model.

Keywords：certificateless cryptography; multi-signature; random oracle model(ROM)

DOI：10.3979/j.issn.1673-825X.2016.03.025

收稿日期：2015-11-01

修订日期：2016-04-11通讯作者：孙玉sunyu@mail.ustc.edu.cn

基金项目：国家自然科学基金(61325010)；安徽省重大教学改革研究项目(2015zdjy200，2015zdjy183)；安徽省社会科学创新发展研究课题(B2015009)；安徽省高校优秀青年人才支持计划

Foundation Items：The National Natural Science Foundation of China(61325010);The Major Research Project on Teaching Innovation of Anhui Province(2015zdjy200，2015zdjy183);The Research Project on innovation and development of Social Science of Anhui Province(B2015009); The Projects of Anhui Province University Outstanding Youth Talent Support Program.

中图分类号：TP309

文献标志码：A

文章编号：1673-825X(2016)03-0431-04

作者简介：

孙玉(1984-)，男，安徽明光人，副教授，博士研究生，主要研究方向为数据通信、计算机网络、模式识别等。E-mail:sunyu@mail.ustc.edu.cn。

刘贵全(1970-)，男，四川彭山人，副教授，博士，硕士生导师，研究方向为机器学习、网络安全、数据挖掘、数据通信等。E-mail:gqliu@ustc.edu.cn。

(编辑：王敏琦)