孫　玉，劉貴全

(1.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027；2.安徽職業(yè)技術(shù)學(xué)院 信息工程系，安徽 合肥 230051)

?

安全高效無(wú)證書(shū)有序多重簽名方案

孫玉1,2，劉貴全1

(1.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027；2.安徽職業(yè)技術(shù)學(xué)院 信息工程系，安徽 合肥 230051)

摘要：無(wú)證書(shū)密碼體制(certificateless cryptography, CLC)將用戶私鑰拆分為部分私鑰和秘密值，其中部分私鑰由密鑰生成中心(key generator center， KGC)生成，而秘密值由用戶自己選定，從而解決了基于身份密碼體制所固有的密鑰托管問(wèn)題。此外，由于用戶公鑰由秘密值決定，無(wú)需認(rèn)證中心(certificate authority，CA)對(duì)用戶的公鑰證書(shū)進(jìn)行管理，解決了傳統(tǒng)密碼體制的證書(shū)管理問(wèn)題。有序多重簽名可用于電子政務(wù)和電子商務(wù)系統(tǒng)實(shí)現(xiàn)公文的逐級(jí)審批發(fā)布，提高認(rèn)證效率。將有序多重簽名和無(wú)證書(shū)密碼相結(jié)合，提出一種安全高效的無(wú)證書(shū)有序多重簽名方案，多重簽名的長(zhǎng)度及驗(yàn)證時(shí)間均與簽名者個(gè)數(shù)無(wú)關(guān)，是緊致的無(wú)證書(shū)有序多重簽名方案。方案使用較少的雙線性對(duì)且只有一個(gè)簽名消息，具有較高的計(jì)算效率和通信效率。證明了方案在隨機(jī)預(yù)言模型(random oracle model，ROM)下具有不可偽造性。

關(guān)鍵詞：無(wú)證書(shū)密碼體制；多重簽名；隨機(jī)預(yù)言模型(ROM)

0引言

無(wú)證書(shū)密碼體制能夠解決傳統(tǒng)公鑰密碼體制和基于身份密碼體制的不足，即不存在證書(shū)管理和密鑰托管問(wèn)題。Al-Riyami等[1]首次提出無(wú)證書(shū)密碼學(xué)的概念，用戶私鑰包括2部分：①部分私鑰，它由密鑰生成中心(key generator center， KGC)生成；②秘密值，它由用戶自己選擇，而公鑰則是用戶通過(guò)使用秘密值來(lái)產(chǎn)生。由于密鑰管理中的系列重要問(wèn)題可以通過(guò)無(wú)證書(shū)密碼體制有效解決，因此,無(wú)證書(shū)簽名方案受到了越來(lái)越多的關(guān)注和研究，具有各種屬性的無(wú)證書(shū)簽名相繼被提出。

通過(guò)對(duì)多重簽名的研究可知，多個(gè)參與者可以對(duì)同一個(gè)消息進(jìn)行簽名。多重簽名的概念由Itakura等[2]提出，依據(jù)所在環(huán)境，可分為有序多重簽名和無(wú)序多重簽名，它們的區(qū)別在于有序多重簽名要求簽名者對(duì)消息進(jìn)行簽名時(shí)要以特定的順序。HARDJONO 等[3]提出基于離散對(duì)數(shù)的多重簽名方案。多重簽名方案的安全模型最早見(jiàn)于由Micali等[4]所發(fā)表的文獻(xiàn)，后面很多研究人員也相繼提出多種多重簽名方案[5-7]。但這些簽名方案大部分是基于傳統(tǒng)公鑰密碼體制[2-4]，或基于身份密碼體制[6-7]，不適用于大規(guī)模分布式網(wǎng)絡(luò)。

目前已有學(xué)者對(duì)無(wú)證書(shū)的多重簽名方案進(jìn)行了研究，Zhang等[8]提出的方案，即簽名長(zhǎng)度隨簽名者個(gè)數(shù)的增加而增加，不滿足緊致性要求。ISLAM等[9]提出了緊致性的多重簽名方案，但在安全性方面并沒(méi)有給出有效的證明。秦艷琳等在文獻(xiàn)[10]中提出緊致的無(wú)證書(shū)有序多重簽名方案，然而該方案的安全性證明存在不足[11]。隨后文獻(xiàn)[11]提出一個(gè)無(wú)證書(shū)多重簽名方案。該文在已有研究的基礎(chǔ)上[12]，構(gòu)造出一個(gè)安全高效的無(wú)證書(shū)有序多重簽名方案。最后證明方案在隨機(jī)預(yù)言模型(random oracle model，ROM)下具有不可偽造性。

1預(yù)備知識(shí)

1.1k-CAA困難問(wèn)題

1.2無(wú)證書(shū)有序多重簽名方案的定義和安全模型

1.2.1方案定義

無(wú)證書(shū)有序多重簽名方案由以下算法[11]構(gòu)成，包含成員KGC，簽名者Ni(i=1,2,…,n)和驗(yàn)證者V。

1)Setup：生成系統(tǒng)參數(shù)。KGC將安全參數(shù)k作為初始參數(shù), 生成主密鑰s和系統(tǒng)參數(shù)Params。

2)ParKeyGen：提取部分私鑰。KGC驗(yàn)證Ni(i=1,2,…,n)的身份標(biāo)識(shí)IDi后，為每個(gè)用戶生成Ni的部分私鑰Di。

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

4)PriKeyGen：生成用戶私鑰。用戶Ni輸出自己的私鑰si=(xi,Di)

5)Sign：簽名。用戶Ni(i=1,2,…,n)以一定的次序K，依次驗(yàn)證上一簽名者的部分簽名σi-1，然后計(jì)算簽名消息σi，作為Ni對(duì)消息的部分簽名。

6)Verify：驗(yàn)證。驗(yàn)證者對(duì)消息m的簽名σn進(jìn)行驗(yàn)證，判斷輸出簽名是否有效。

1.2.2安全模型

假設(shè)存在兩類攻擊者：AⅠ，模擬任意參與者，他們可以替換任意簽名者的公鑰但不知道系統(tǒng)主密鑰；AⅡ，模擬惡意KGC，它不能替換簽名者的公鑰但知道系統(tǒng)主密鑰。方案的安全模型[11-12]如下。

1)系統(tǒng)參數(shù)設(shè)置：挑戰(zhàn)者D得到系統(tǒng)參數(shù)Params和系統(tǒng)主密鑰s。如果攻擊者A=AⅠ，D將Params發(fā)送給A。如果A=AⅡ，將Params和s發(fā)送給A。

2)詢問(wèn)：A已經(jīng)獲得k個(gè)簽名者的完整私鑰。隨后A詢問(wèn)Hash函數(shù)，用戶完整私鑰，公鑰以及執(zhí)行公鑰替換詢問(wèn)，以期獲得未被攻破簽名者的部分簽名。

2具體方案

高效無(wú)證書(shū)多重簽名方案的具體構(gòu)造如下。

4)PriKeyGen：Ni(i=1,2,…,n)輸出si=(xi,zi)作為其完整私鑰。

5)Sign：簽名。

①簽名者Ni對(duì)消息m進(jìn)行簽名。

a)計(jì)算

(1)

(1)式中，K={ID1,ID2,…,IDn}；符號(hào)“a‖b”表示比特串a(chǎn)和b的聯(lián)結(jié)。

b)計(jì)算

(2)

(2)式中，σ1是Ni對(duì)m的部分簽名。

②簽名者Ni對(duì)Ni-1發(fā)來(lái)的簽名消息(m,σi-1)進(jìn)行驗(yàn)證后再簽名。

a)驗(yàn)證：Ni構(gòu)造Cj。計(jì)算

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

(3)

驗(yàn)證等式

(4)

是否成立。若成立，則對(duì)簽名消息(m,σi-1)進(jìn)行簽名，否則，終止算法。

b)計(jì)算

(5)

signi=(Vixi+zi)-1P

(6)

(7)

其中，(7)式是Ni對(duì)m的部分簽名。

c)簽名者Ni(i=1,2,…,n)對(duì)消息m的完整簽名為(m,σn)。

6)Verify：驗(yàn)證者對(duì)簽名消息(m,σn)進(jìn)行驗(yàn)證。

驗(yàn)證者構(gòu)造Ci，計(jì)算

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

(8)

驗(yàn)證等式

(9)

是否成立。若成立，則(m,σn)是正確的簽名。

3方案分析

3.1正確性

證明假設(shè)由簽名方案得到多重簽名(m,σn)，則

(10)

3.2抗偽造性

可以證明在RO模型下，對(duì)任何攻擊者來(lái)說(shuō)本方案都是不可偽造的。

定理1在RO模型下，如果AⅠ能夠以不可忽略的概率偽造出多重簽名，則AⅠ能夠解決k-CAA問(wèn)題。

證明攻擊者AⅠ已經(jīng)攻破了n-1個(gè)簽名者，假設(shè)AⅠ已知N1,…,Nn-1的私鑰，為了攻破本方案，AⅠ必須成功地偽造第n個(gè)簽名者Nn。如果AⅠ能以不可忽略的概率ε攻破無(wú)證書(shū)多重簽名方案，則挑戰(zhàn)者D能將AⅠ作為子程序最終解決k-CAA問(wèn)題，即如果D已獲得參數(shù){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Ⅰ詢問(wèn)(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Ⅰ輸出一個(gè)有效的簽名(IDn,mn,σn)，IDn的公鑰為(Pj,Rj)。如果hj∈{h1,…,hk}，D停止執(zhí)行。否則得到e(signn,Rn+αnQ+βjPj)=e(σn/σ1,…,σn-1,αnW+αnhjP)，因?yàn)锳I能夠詢問(wèn)除了IDn之外所有用戶的私鑰，所以AI能夠計(jì)算出σ1,…,σn-1，signn=σn/σ1,…,σn-1。那么對(duì)于hj?{h1,…,hk}，D能輸出(s+hj)-1P=αnσn/σ1,…,σn-1。從而得知，如果AI能偽造有效的多重簽名，那么D能夠解決k-CAA困難問(wèn)題。

定理2在RO模型下，如果AⅡ能夠以不可忽略的概率偽造出多重簽名，則D能夠解決k-CAA問(wèn)題。

證明定理2的證明與定理1的證明過(guò)程類似，本文將不再給出。

3.3效率分析

與文獻(xiàn)[10-11]類似，在效率分析時(shí)將不考慮Hash函數(shù)這樣的預(yù)計(jì)算，而著重考慮雙線性對(duì)操作。首先，一次雙線性對(duì)操作的計(jì)算時(shí)間是標(biāo)量乘法的21倍，該文方案在整體驗(yàn)證時(shí)只需要2次雙線性對(duì)操作，因此，計(jì)算是高效的；其次，該文方案最終的多重簽名為σn，與單用戶簽名一樣且只有一個(gè)簽名消息，因此，占用較少的通信代價(jià)；最后，方案的簽名長(zhǎng)度與簽名者個(gè)數(shù)無(wú)關(guān)，是緊湊的多重簽名方案。

4結(jié)束語(yǔ)

有序多重簽名在電子政務(wù)和電子商務(wù)領(lǐng)域具有重要的實(shí)際應(yīng)用價(jià)值，無(wú)證書(shū)密碼體制能夠解決證書(shū)管理問(wèn)題和密鑰托管問(wèn)題，有必要對(duì)無(wú)證書(shū)多重簽名進(jìn)行研究。提出一種高效無(wú)證書(shū)有序多重簽名方案，并在隨機(jī)預(yù)言模型下證明方案的安全性等價(jià)于求解k-CAA困難問(wèn)題。通過(guò)安全性和效率分析可知，提出的無(wú)證書(shū)多重簽名方案是安全高效的。下一步將基于已有的無(wú)證書(shū)多重簽名方案設(shè)計(jì)適用于電子商務(wù)系統(tǒng)的身份隱私保護(hù)方案。

參考文獻(xiàn)：

[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]于佳, 郝蓉, 孔凡玉.標(biāo)準(zhǔn)模型下的前向安全多重簽名:安全性模型和構(gòu)造[J].軟件學(xué)報(bào),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] 秦艷琳,吳曉平.高效的無(wú)證書(shū)有序多重簽名方案[J].通信學(xué)報(bào),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] 許艷，黃劉生，田苗苗，等. 可證安全的高效無(wú)證書(shū)有序多重簽名方案[J].通信學(xué)報(bào),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

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61325010)；安徽省重大教學(xué)改革研究項(xiàng)目(2015zdjy200，2015zdjy183)；安徽省社會(huì)科學(xué)創(chuàng)新發(fā)展研究課題(B2015009)；安徽省高校優(yōu)秀青年人才支持計(jì)劃

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.

中圖分類號(hào)：TP309

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)03-0431-04

作者簡(jiǎn)介：

孫玉(1984-)，男，安徽明光人，副教授，博士研究生，主要研究方向?yàn)閿?shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)、模式識(shí)別等。E-mail:sunyu@mail.ustc.edu.cn。

劉貴全(1970-)，男，四川彭山人，副教授，博士，碩士生導(dǎo)師，研究方向?yàn)闄C(jī)器學(xué)習(xí)、網(wǎng)絡(luò)安全、數(shù)據(jù)挖掘、數(shù)據(jù)通信等。E-mail:gqliu@ustc.edu.cn。

(編輯：王敏琦)