一種新的基于橢圓曲線的門限群簽名方案

謝 冬,李佳佳,沈忠華

(杭州師范大學(xué)理學(xué)院,浙江 杭州310036)

一種新的基于橢圓曲線的門限群簽名方案

謝 冬,李佳佳,沈忠華

(杭州師范大學(xué)理學(xué)院,浙江 杭州310036)

在門限群簽名體制中,任何t或多于t個(gè)成員合作就可以產(chǎn)生一個(gè)有效的群簽名.基于橢圓曲線離散對數(shù)問題的難解性,提出了一個(gè)安全、有效的門限簽名方案.與現(xiàn)有的基于橢圓曲線離散對數(shù)問題的門限簽名方案相比,提出的方案具有以下優(yōu)勢：在可信中心TC的幫助下能夠追蹤到簽名者的身份；t個(gè)成員合謀攻擊不能偽造其他成員的簽名也無法獲取系統(tǒng)的全部秘密；系統(tǒng)具有一定的穩(wěn)定性.

數(shù)字簽名;門限簽名;秘密共享;橢圓曲線離散對數(shù)

0 引 言

隨著信息時(shí)代的到來,信息安全的重要性越來越受到人們的關(guān)注.數(shù)字簽名技術(shù)被廣泛應(yīng)用于人們生活的各個(gè)領(lǐng)域,例如電子商務(wù)、大型企業(yè)等等.A.Shamir于1979年提出了一種經(jīng)典的秘密共享方法[1],而后D.Chaum和E.van Heyst于1991年首次提出群簽名的概念[2].在群簽名體制中,加入秘密共享的思想,便形成了門限群簽名體制[3-6].在一個(gè)門限群簽名方案中,任何t或多于t個(gè)成員能夠代表整個(gè)群去簽署任意的消息,但是群中任意少于t個(gè)成員不能夠合作產(chǎn)生一個(gè)有效的群簽名.在群公共參數(shù)的幫助下,任意的群簽名接收者都可以驗(yàn)證簽名的有效性,但是他并不知道群中的哪些具體成員參加了此次簽名.

在具有相同的安全性水平條件下,橢圓曲線密碼體制(ECC)相比于其他的公鑰密碼體制具有更短的密鑰長度.一般說來,一個(gè)160比特密鑰長度的橢圓曲線密碼體制和一個(gè)1 024比特密鑰長度的RSA密碼體制具有相同的安全性.由于橢圓曲線密碼體制具有密鑰長度短、加解密速度快以及存儲空間小等特點(diǎn),一些基于ECC的具有實(shí)際應(yīng)用的簽名方案被相繼提出.Wang等提出了一個(gè)基于橢圓曲線的可驗(yàn)證的門限數(shù)字簽名方案[7],此方案中沒有可信第三方的參與.Pin-Chang Su等提出了一個(gè)基于身份的橢圓曲線門限群簽名方案[8].隨后,Xia等提出了一個(gè)基于ECC的動態(tài)門限簽名體制[9].然而,上述提到的幾個(gè)方案均有一個(gè)弱點(diǎn)：群中的任意t個(gè)成員能夠攻破整個(gè)系統(tǒng),獲得系統(tǒng)的所有秘密參數(shù),從而能夠有效地偽造任意其他t個(gè)成員的簽名,而整個(gè)過程都不會被可信的第三方發(fā)現(xiàn)(若方案存在可信第三方).此外,當(dāng)事后產(chǎn)生糾紛時(shí),一些現(xiàn)有的方案[7-8]并不能追蹤到簽名者的身份.一些方案也存在穩(wěn)定性問題,如文獻(xiàn)[7].

為了解決以上方案中存在的一些問題,基于橢圓曲線離散對數(shù)的難解性,我們提出了一個(gè)新的安全、有效的門限簽名方案.接下來首先描述新方案，然后給出新方案的安全性和可行性分析，最后給出一個(gè)結(jié)論.

1 新方案的描述

新方案的安全性是基于橢圓曲線離散對數(shù)的難解性.此方案中,可信中心TC負(fù)責(zé)群私鑰、群公鑰以及其他系統(tǒng)參數(shù)的選取.本方案的所有實(shí)體包含可信中心TC、n個(gè)群成員以及一個(gè)指定的群簽名合成者clerk.我們用U表示所有可能參與簽名的群成員集合,其中U={P1,P2,…,Pn}.新方案包括系統(tǒng)初始化、(t,n)門限數(shù)字簽名的產(chǎn)生以及(t,n)門限數(shù)字簽名的驗(yàn)證3個(gè)部分.

1.1 系統(tǒng)初始化

TC通過以下7個(gè)步驟來產(chǎn)生系統(tǒng)參數(shù)：

1)TC選擇一個(gè)大素?cái)?shù)q,一個(gè)GF(q)上的橢圓曲線E：y2=x3+ax+b,其中a,b∈Zq,4a3+27b2≠0modq.

2)TC選擇橢圓曲線E上的一個(gè)基點(diǎn)G,其中G有足夠大的階p,且滿足在由基點(diǎn)G生成的循環(huán)群中求解離散對數(shù)問題是困難的.

3)TC選擇一個(gè)安全的單向哈希函數(shù)h(·).

4)TC選擇一個(gè)函數(shù)f(x)=at-1xt-1+…+a1x+a0modp,其中ai(i=0,…,t-1)為1到p-1之間的隨機(jī)整數(shù).

5)我們以f(0)作為群的私鑰,TC計(jì)算群公鑰Y=f(0)G=(xY,yY).

完成以上7個(gè)步驟后,TC將xi保密,將ci和di通過安全信道發(fā)送給ui,并公開Y和(ui,Yi,Wi,vi).

1.2 (t,n)門限數(shù)字簽名的產(chǎn)生

若群中t個(gè)成員同意參加對于消息m的簽名,我們讓A表示所有參與簽名的t個(gè)成員的集合.不失一般性,令A(yù)={P1,P2,…,Pt}.門限數(shù)字簽名產(chǎn)生的整個(gè)過程包含份額簽名的產(chǎn)生、份額簽名的驗(yàn)證以及門限群簽名的產(chǎn)生.集合A中的成員和clerk通過以下步驟合作產(chǎn)生(t,n)門限數(shù)字簽名：

1)集合A中的每個(gè)成員Pi計(jì)算σi=ciG=(xσi,yσi),并發(fā)送xσi給指定的群簽名合成者clerk.

2)clerk計(jì)算xσiG=(vi′,zi′),并驗(yàn)證vi′是否等于vi.若vi′≠vi,則表明Pi是一個(gè)欺騙者.若vi′=vi(i=1,…,t),則clerk用t個(gè)簽名者的公共值(vi,ui)構(gòu)造一個(gè)身份識別函數(shù)F(x),其中

然后clerk將F(x)廣播給所有的簽名者Pi,其中i=1,2,…,t.

4)集合A中的每個(gè)成員Pi首先計(jì)算

(1)

5)當(dāng)clerk收集到所有參與簽名成員的份額簽名后,首先根據(jù)式(1)計(jì)算e,r和w,然后根據(jù)下式是否成立來判斷Pi份額簽名的有效性：

Gsi+erQi=wBi(Wi+Yi).

通過以上步驟,對于消息m,群成員和clerk共同產(chǎn)生了一個(gè)門限群簽名(r,s).

1.3 (t,n)門限數(shù)字簽名的驗(yàn)證

接收到由以上步驟產(chǎn)生的群簽名時(shí),接收者首先計(jì)算e=h(m,F(xY)),然后驗(yàn)證等式sG+erQ=w(L+Y)是否成立.若等式不成立,則表明存在惡意的成員偽造群簽名或者簽名并不是由A中的t個(gè)成員產(chǎn)生；若等式成立,則簽名是有效的.

定理1 若群簽名驗(yàn)證等式sG+erQ=w(L+Y)成立,則對于消息m的群簽名(r,s)是有效的.

證明根據(jù)方程si=wBidi-kiermodp,其中e=h(m,F(xY)),將方程兩邊同時(shí)乘以G,得到

siG=wBidiG-kierG.

因此有

移項(xiàng)得到sG+erQ=w(L+Y),故定理成立.

2 新方案的安全性和可行性分析

1)新方案具有門限特性.任何少于t個(gè)成員組成的集合均不能產(chǎn)生一個(gè)有效的門限群簽名.根據(jù)拉格朗日插值定理,只有t個(gè)或者多于t個(gè)簽名者的(ui,di)才能夠恢復(fù)群私鑰f(0).此外,任何少于t個(gè)成員也無法完成簽名步驟,因?yàn)閏lerk必須收集到t個(gè)成員的份額簽名才會合成群簽名.

2)若指定的簽名合成者clerk想要偽造一個(gè)身份識別函數(shù)F(x),錯(cuò)誤的身份識別函數(shù)并不能全部滿足t個(gè)等式F(vi)=ui(i=1,2,…,t)的驗(yàn)證.

3)新方案具有匿名性以及驗(yàn)證簡單性.當(dāng)簽名接收者接收到群簽名時(shí),在群公鑰的幫助下,他可以很簡單地驗(yàn)證簽名的有效性.在沒有可信中心TC的幫助下,接收者也無法知道具體是哪些成員參與了此次簽名.

4)新方案能夠抵抗偽造攻擊.首先,惡意攻擊者不能偽造有效的份額簽名,因?yàn)閻阂夤粽卟⒉恢纃i,所以他不能計(jì)算一個(gè)有效的si.其次,惡意攻擊者并不能直接偽造一個(gè)有效的群簽名.根據(jù)群簽名的驗(yàn)證等式sG+erQ=w(L+Y),他不可能偽造一個(gè)有效的(r,s)滿足驗(yàn)證方程.因?yàn)橹纑,s中的一個(gè)數(shù)去求第二個(gè)數(shù)都是橢圓曲線上的離散對數(shù)問題,在計(jì)算上是困難的.

5)新方案具有可追蹤性.現(xiàn)有的大多基于橢圓曲線的門限簽名方案均無追蹤性,如文獻(xiàn)[7-8].然而,在本方案中,若事后產(chǎn)生了簽名糾紛,在TC的幫助下,任何合法的接收者均能追蹤到真實(shí)簽名者的身份.因?yàn)閏lerk通過t個(gè)(vi,ui)構(gòu)造了一個(gè)身份識別函數(shù)F(x),接收者利用公開的系統(tǒng)參數(shù)一一驗(yàn)證等式F(vi)=ui是否成立.若對于某個(gè)ui方程成立,則接收者將ui發(fā)送給TC,而TC知道ui和用戶之間的一一對應(yīng)關(guān)系.因此TC能夠揭露真實(shí)簽名者的身份.

6)新方案具有防冒充性和強(qiáng)壯性.在現(xiàn)有存在的門限方案中,t或者多于t個(gè)成員合作能夠恢復(fù)系統(tǒng)秘密多項(xiàng)式函數(shù)f(x).因此,群中任意t或者多于t個(gè)成員能夠計(jì)算其他成員的私鑰f(ui),從而能夠偽造其他成員的份額簽名.但是在本方案中,任何簽名小組不能冒充其他小組生成群簽名.即使t個(gè)成員恢復(fù)了秘密多項(xiàng)式f(x),然而他們并不知道xi,因此不能計(jì)算其他成員的個(gè)人私鑰di,他們依然無法偽造群中其他成員的份額簽名.也就是說,群中t個(gè)成員合作也無法恢復(fù)系統(tǒng)所有的秘密參數(shù),本方案具有強(qiáng)壯性.

7)新方案具有一定的穩(wěn)定性.在新方案中,當(dāng)群需要增加或者刪除一些群成員時(shí),只需要較少地改變系統(tǒng)參數(shù),在計(jì)算上是方便的.當(dāng)一個(gè)新成員Pn+1想要加入群時(shí),TC首先選擇一個(gè)與xi(i=1,…,n)均不相同的整數(shù)xn+1,然后計(jì)算Wn+1=xn+1G,Yn+1=f(un+1)G.接下來TC隨機(jī)選擇整數(shù)cn+1,根據(jù)系統(tǒng)初始化的步驟,計(jì)算dn+1以及vn+1.然后TC將(cn+1,dn+1)發(fā)送給Pn+1,并公開(un+1,Wn+1,vn+1).而整個(gè)過程其他成員的參數(shù)均未改變.當(dāng)TC想要從群中刪除一個(gè)老成員Pj時(shí),通過以下步驟完成：首先,TC選擇一個(gè)新的秘密多項(xiàng)式f(x)′且滿足f(0)′=a0,以及n-1個(gè)新的xi′；其次,TC根據(jù)系統(tǒng)初始化的步驟產(chǎn)生n-1個(gè)新的ci′和di′；最后,TC將(ci′,di′)發(fā)送給Pi且公開(ui′,Yi′,Wi′,vi′),其中i=1,2,…,j-1,j+1,…,n.通過以上步驟,群中便刪除了成員Pj.

3 結(jié) 論

基于橢圓曲線離散對數(shù)的難解性,提出了一個(gè)新的具有實(shí)際應(yīng)用的門限群簽名方案.相對于其他的公鑰密碼系統(tǒng),新方案具有密鑰長度短、存儲空間小以及安全性高等特點(diǎn).分析表明,提出的方案具有很高的實(shí)際應(yīng)用價(jià)值.

[1] Shamir A. How to share a secret[J]. Communications of the ACM,1979,22(4):612-613.

[2] Chaum D, Heyst E. Group signatures[C]//Advances in Cryptology-Eurocrypt’91 Proceeding. Berlin: Springer Verlag,1992:257-265.

[3] Desmedt Y, Frankel Y. Shared generation of authenticator and signatures(extended abstract)[C]//Feigenbaum J. Advances in Cryptology-CRYPTO’91. Berlin: Springer-Verlag,1992:457-469.

[4] Wang G T, Lin C H , Chang C C. Threshold signature schemes with traceable signers in group communications[J]. Computer Communications,1998,21(8):271-276.

[5] Tseng Y M, Jan J K. Attacks on threshold signature schemes with traceable signatures in group communications[J]. Computer Communications,2000,23(5):771-776.

[6] Wang Guilin, Qing Sihan. Weaknesses of some threshold group signature scheme [J]. Journal of Software,2000,11(10):1326-1332.

[7] Wang Huaqun, Zhao Junxi, Zhang Lijun. Verifiable (t,n) threshold signature scheme based on elliptic curve[J]. Wuhan University Journal of Natural Sciences,2005,10(1):165-168.

[8] Su P C, Chang H K C, Lu E H. ID-based threshold digital signature schemes on the elliptic curve discrete logarithm problem[J]. Applied Mathematics and Computation,2005,164(3):757-772.

[9] Xia Xiangsheng, Hong Fan, Geng Yongjun,etal. Efficient dynamic threshold group signature scheme based on elliptic curve cryptosystem[J]. Journal of Southwest Jiaotong University :English Edition,2008,16(1):18-23.

ANewThresholdSignatureSchemeBasedonEllipticCurveCryptosystem

XIE Dong, LI Jiajia, SHEN Zhonghua

(College of Science, Hangzhou Normal University, Hangzhou 310036, China)

In the threshold group signature cryptosystem, any t or more than t members can cooperate to produce a valid group signature. Based on the difficulty of solving the ECDLP(elliptic curve discrete logarithm problem), a secure and efficient threshold scheme was proposed. Comparing to the existing threshold signature scheme based on the ECDLP, this scheme has some advantages ,it is able to track the signer’s identity with the assistance of the trusted center TC,tmembers in the group can not forge other members’ partial signature and can not obtain all the system’s secrets, and the system has certainly stability.

digital signature; threshold signature; secret sharing; elliptic curve discrete logarithm

2012-04-19

浙江省自然科學(xué)基金項(xiàng)目(Y6110782).

沈忠華(1973—),男,教授,主要從事數(shù)論與密碼學(xué)、信息安全技術(shù)等研究.E-mail: ahtshen@126.com

10.3969/j.issn.1674-232X.2013.01.011

TP309MSC2010: 94A60

A

1674-232X(2013)01-0057-04