安全高效無證書有序多重簽名方案

孫　玉，劉貴全

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

?

安全高效無證書有序多重簽名方案

孫玉1,2，劉貴全1

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

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

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

0引言

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

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

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

1預(yù)備知識

1.1k-CAA困難問題

1.2無證書有序多重簽名方案的定義和安全模型

1.2.1方案定義

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

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

2)ParKeyGen：提取部分私鑰。KGC驗證Ni(i=1,2,…,n)的身份標(biāo)識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安全模型

假設(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)詢問：A已經(jīng)獲得k個簽名者的完整私鑰。隨后A詢問Hash函數(shù)，用戶完整私鑰，公鑰以及執(zhí)行公鑰替換詢問，以期獲得未被攻破簽名者的部分簽名。

2具體方案

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

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

5)Sign：簽名。

①簽名者Ni對消息m進行簽名。

a)計算

(1)

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

b)計算

(2)

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

②簽名者Ni對Ni-1發(fā)來的簽名消息(m,σi-1)進行驗證后再簽名。

a)驗證：Ni構(gòu)造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)進行驗證。

驗證者構(gòu)造Ci，計算

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

(8)

驗證等式

(9)

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

3方案分析

3.1正確性

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

(10)

3.2抗偽造性

可以證明在RO模型下，對任何攻擊者來說本方案都是不可偽造的。

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

證明攻擊者AⅠ已經(jīng)攻破了n-1個簽名者，假設(shè)AⅠ已知N1,…,Nn-1的私鑰，為了攻破本方案，AⅠ必須成功地偽造第n個簽名者Nn。如果AⅠ能以不可忽略的概率ε攻破無證書多重簽名方案，則挑戰(zhàn)者D能將AⅠ作為子程序最終解決k-CAA問題，即如果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Ⅰ詢問(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停止執(zhí)行。否則得到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函數(shù)這樣的預(yù)計算，而著重考慮雙線性對操作。首先，一次雙線性對操作的計算時間是標(biāo)量乘法的21倍，該文方案在整體驗證時只需要2次雙線性對操作，因此，計算是高效的；其次，該文方案最終的多重簽名為σn，與單用戶簽名一樣且只有一個簽名消息，因此，占用較少的通信代價；最后，方案的簽名長度與簽名者個數(shù)無關(guān)，是緊湊的多重簽名方案。

4結(jié)束語

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

參考文獻：

[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é)報,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].通信學(xué)報,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].通信學(xué)報,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

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

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

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

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

作者簡介：

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

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

(編輯：王敏琦)