一個基于ＩＤ的可刪除群簽名方案

摘要：在第三方不可信任的情況下，傳統(tǒng)的ID簽名系統(tǒng)不適用于安全的群簽名。給出一個安全的基于ID的群簽名方案，即使在KGC不可信的情況下也能保證其安全性，而且該方案可以安全地增加或刪除群成員而不需要改變其他有效群成員密鑰和群公開密鑰。同時，密鑰長度及簽名長度與群成員的多少無關(guān)。

關(guān)鍵詞：群簽名; ID加密; 二次線性對映射

中圖分類號：TP309．2文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)03－0924－03

自D. Chaum等人于1991年首次提出了群簽名的概念[1]以后，群簽名因其在商業(yè)上的廣泛應(yīng)用而引起人們的關(guān)注[1~4]。群簽名允許群中合法成員代表群組對信息進(jìn)行匿名簽名，該簽名可以利用群組公開密鑰進(jìn)行驗證。在發(fā)生糾紛時，只有指定的群主管可以打開簽名，確定簽名成員的身份。Park等人于1993年首次提出基于ID的群簽名，該方案使得管理中心打開簽名變得簡便。但Mao等人指出該方案不能保證簽名成員的匿名性，且公鑰和簽名的長度與群成員線性相關(guān)，即群中成員很多時效率低。群簽名方案的一個重要進(jìn)展是J. Camenish等人于1997年提出的群簽名方案[5]。該方案中群簽名及群組公鑰的長度是固定的，與群組成員的個數(shù)無關(guān)，即群組建立后可以加入新成員，且新成員的加入不改變?nèi)航M的公開密鑰。

在群簽名的實際應(yīng)用中，群組成員的進(jìn)出是動態(tài)的，即群組中不僅有新成員的加入，同時還有群組成員的刪除問題。因此，在不改變原有群組簽名私鑰和驗證公鑰的條件下，如何保證其他合法群組成員簽名的匿名性和安全性對群簽名方案的設(shè)計就顯得十分重要。目前，群成員的刪除問題及

抗偽造攻擊問題是影響群簽名應(yīng)用的一個主要障礙。2000年，H. J. Kim等人提出了一個可以撤銷成員的群簽名方案[6]，該方案每次更新秘密密鑰時需要大量的指數(shù)運算，給群組中的其他成員帶來繁重和額外的開銷。2001年，Song提出了一種成員可撤銷的群簽名方案[7]，在不改變其他有效群成員密鑰的情況下可以安全地刪除群成員。2004年，黃達(dá)人提出了一種基于中國剩余定理的群簽名方案[8]，但該方案在群成員刪除過程中需要更新群管理中心的公開密鑰。

群簽名的匿名性要求：用戶的公開密鑰ID不能泄露關(guān)于用戶身份的任何信息。因此，傳統(tǒng)的ID簽名系統(tǒng)在KGC不可信的條件下不適用于安全的群簽名。如果用任意字符串作為用戶的公開密鑰，則不可信的KGC可以偽造一個有效簽名，因為KGC同樣可以產(chǎn)生每個用戶的公鑰，并計算其相應(yīng)的私鑰。2002年，Chen Xiaofeng在KGC不可信的條件下提出一個基于ID的簽名方案（XC方案），并基于該方案提出一個基于ID的群簽名方案[9]。

本文對XC方案的安全性進(jìn)行分析，指出其存在的安全隱患，并在KGC不可信的情況下，給出了一個新的可刪除群簽名方案。其具有以下幾個特點：a）即使在KGC不可信的情況下也能保證其安全性；b）在不改變KGC的秘密密鑰和其他有效群成員簽名密鑰的情況下，可以安全地刪除群成員；c）安全性好，可以抵抗偽造攻擊和聯(lián)合攻擊。

1相關(guān)定義

1．1群簽名的定義及安全性要求

定義1[1]一個群簽名方案是包含以下過程的數(shù)字簽名方案：

a）創(chuàng)建。一種用于產(chǎn)生群公鑰和私鑰的多項式時間算法。

b）加入。一個用戶與群管理人之間使用戶成為群成員的交互式協(xié)議。

c）簽名。一種算法，當(dāng)輸入一個消息和一個群成員的簽名密鑰后，輸出對消息的簽名。

d）驗證。一種在輸入對消息的簽名及群公鑰后確定簽名是否有效的算法。

e）打開。一種在給定簽名及群私鑰的條件下確定簽名人身份的算法。

群簽名的安全性要求：

a）匿名性。給定一個群簽名后，除了惟一的群主管，任何人確定簽名人的身份在計算上是不可行的。

b）不關(guān)聯(lián)性。在不打開簽名的情況下，任何人確定兩個或兩個以上的消息是否由同一個成員產(chǎn)生在計算上是不可行的。

c）防偽造性。只有群成員才能產(chǎn)生有效的群簽名。

d）可跟蹤性。群管理人在必要時可以打開一個簽名以確定簽名人的身份，而且簽名人不能阻止一個合法簽名的打開。

e）抗聯(lián)合攻擊。即使一些群成員串通在一起也不能產(chǎn)生一個合法的不能被跟蹤的群簽名。

1．2二次線性對映射和Gap DiffieHellman群

以|G|表示群G的階，n為一整數(shù)，Zn表示模n的剩余類環(huán)，H1、H2表示抗碰撞的hash函數(shù)，Z表示整數(shù)。

1．2．1二次線性對映射

定義2[9]設(shè)G1=〈P〉是一循環(huán)加群，q是素數(shù)，|G1|=q，G2是一循環(huán)乘群，|G2|=q，a，b∈Zq，對映射e：G1×G1 →G2，若：

a)對于任意R，Q∈G1， e(aR，bQ)=e(R，Q)ab。

b)存在R和Q∈G1，滿足e(R，Q)≠1。其中：1為G2的幺元。

c)對于任意R，Q∈G1，計算e(R，Q)是可行的，則稱映射e為二次線性對映射。

由定義2，顯然有e(aR，bQ)=e(R，abQ)=e(abR，Q)。

1．2．2Gap DiffieHellman群

設(shè)G1=〈P〉是一循環(huán)加群，q∈Z，|G1|=q，若：

a)給定元素R，Q∈G1，找到一個n∈Zq，使得Q=nR，則稱其為DLP問題。

b)給定元素R，aR，bR（其中：a，b∈Zp），計算abR，則稱其為CDHP問題。

c)給定元素R，aR，bR（其中：a，b，c∈Zp），計算是否c≡ab mod q，則稱其為DDHP問題。

定義3[9]如果對于群G1，DDHP問題能在多項式時間內(nèi)解決，而DLP和CDHP問題不能在多項式時間內(nèi)解決，則稱G1為Gap DiffieHellman群。

2XC方案及分析

設(shè)G1=〈P〉是一Gap DiffieHellman群，q是素數(shù)，|G1|=q，G2是一循環(huán)乘群，|G2|=q，a，b∈Zq，二次線性對映射e：G1×G1 → G2，單向哈希函數(shù)H1:{0，1}×G1 → Zq和H2:{0，1}×G1 → G1。

2．1初始化

KGC選擇隨機數(shù)s∈Zq，計算Ppub=sP，公開系統(tǒng)參數(shù){G1，G2，e，q，P，Ppub，H1，H2}，秘密保存私鑰s。

2．2密鑰提取

用戶隨機選擇r∈Zq作為他的私鑰，計算rP并將該值同身份信息ID一起發(fā)送給KGC。KGC計算QID=H2(ID‖T，rP)及SID=sQID，并將SID發(fā)送給用戶。其中：T為r的存活期。用戶的簽名密鑰為(SID，r)（其中r對KGC保密），公開密鑰為ID。

2．3簽名

設(shè)簽名消息為m，用戶隨機ID選取整數(shù)a∈Zq，計算

U=aQID

V=rH2(m，U)

h=H1(m，U+V)

W=(a+h)sQID

得到對消息m的簽名（U，V，W，T，rP)。

2．4驗證

驗證者首先計算Q=H2(ID‖T，rP)，H2(m，U)，h=H1(m，U+V)，然后驗證下列等式是否成立：

e(W，P)=e(U+hQ，Ppub)

e(V，P)=e(H2(m，U)，rP)

如果等式成立，說明簽名（U，V，W，T，rP)是有效的。

2．5安全性分析

文獻(xiàn)[9]對XC方案的安全性進(jìn)行了分析，指出XC方案抗KGC偽造攻擊。事實上，XC方案只可保證KGC不能偽造已與KGC進(jìn)行2.2節(jié)交互協(xié)議的用戶簽名，而對于未與KGC進(jìn)行該交互協(xié)議的用戶，KGC仍可偽造其簽名。假設(shè)KGC欲偽造用戶ID（該用戶未與KGC進(jìn)行2.2節(jié)交互協(xié)議）的簽名，可執(zhí)行如下操作： 隨機選擇r′∈Zq，計算

QID′=H2(ID‖T，r′P)

U′=aQID′

V′=r′H2(m，U)

h′=H1(m，U′+V′)

W′=(a+h′)sQID′

得到的偽造簽名(U′，V′，W′，T，r′P)滿足等式

e(W′，P)=e(U′+hQID′，Ppub)

e(V′，P)=e(H2(m，U′)，r′P)

因此該簽名是有效的。由于該用戶未與KGC進(jìn)行2.2節(jié)交互協(xié)議，他無法采用文獻(xiàn)[9]中的方法向仲裁機構(gòu)證明自己的清白。文獻(xiàn)[9]中的群簽名方案也存在該缺陷。對于XC方案的這一缺陷，可采取如下方法解決：假設(shè)用戶還有一對用于普通簽名的密鑰，用戶與KGC進(jìn)行2.2節(jié)交互協(xié)議時，首先對rP進(jìn)行普通數(shù)字簽名，將rP及其簽名一起發(fā)送給KGC；當(dāng)出現(xiàn)爭議時，仲裁機構(gòu)可要求KGC出示用戶對rP的簽名，即可防止KGC偽造簽名。

3基于ID的可刪除群簽名方案

下面給出一個新的群簽名方案，該方案在KGC不可信的情況下也是安全的，在有效刪除群成員的同時不改變KGC的秘密密鑰和其他有效群成員的簽名密鑰。由于群簽名的驗證公鑰由KGC的身份信息計算而得，不泄露簽名用戶的身份信息，簽名過程得以簡化，生成簽名密鑰后采用F. Hess[10]提出的基于ID的簽名方案產(chǎn)生簽名即可，且與文獻(xiàn)[9]中群簽名方案相比，本方案產(chǎn)生的簽名長度更短。

設(shè)G1=〈P〉是DiffieHellman群，q∈Z+，|G1|=q，G2是一循環(huán)乘群，|G2|=q，a，b∈Zq，二次線性對映射e：G1×G2→G2，單向哈希函數(shù)H1:{0，1}×G2→Zq，H2:{0，1}×G1→G1。

3．1初始化

設(shè)KGC的身份信息為IDKGC∈Zq，KGC選擇隨機數(shù)s∈Zq，計算Ppub=sP，并公開系統(tǒng)參數(shù){G1，G2，e，q，P，Ppub，IDKGC，H1，H2}，秘密保存密鑰s。

3．2加入

假設(shè)加入群組的用戶都還有一對用于普通簽名的密鑰。若用戶M欲成為群成員，首先將其身份信息ID發(fā)送給KGC。若KGC確定身份合法，M隨機選擇xi∈Zq(i=1，…，k)，計算xiP并對xiP進(jìn)行普通簽名得到σi；然后將(xiP，σi)發(fā)送給KGC。

KGC計算

QID，i=H2(IDKGC，xiP)

SID，i=sQID，i

并將SID，i發(fā)送給M，則SID，i為M的簽名密鑰。KGC保存M的(xiP，ID，σi)。

3．3簽名

假設(shè)M對消息m簽名（不妨設(shè)是第i次簽名），M首先隨機選擇A∈G1，計算

c=H1(m，e(A，P))

T=A-c×SID，i-cxiQID，i

則(c，T，xiP)為對消息m的簽名。

3．4驗證

驗證者計算

QID，i=H2(IDKGC，xiP)

R=e(T，P)×e(cQID，i，Ppub+xiP)

如果等式H1(m，R)=c成立，說明簽名者對消息m的簽名(c，T，xiP)是一個有效的簽名。

3．5打開

因為KGC保存著每個群成員的(xiP，ID，σi)，所以對一個有效的簽名(c，T，xiP)，KGC能夠從xiP中識別簽名者的身份，從而打開其身份。

3．6刪除

如果要刪除成員M，KGC只需把M的xiP發(fā)布于刪除列表中，這樣驗證者即可從刪除列表中找到已被刪除的成員。

在成員刪除過程中，組中其他有效成員并不需要更新自己的簽名密鑰；同時，KGC的公開密鑰和秘密密鑰也保持不變。所以新方案對KGC和群成員都是簡單、高效的。

4安全性分析

本文的安全性分析基于四種可能的攻擊：群成員偽造簽名、聯(lián)合攻擊、非群成員的偽造攻擊及KGC偽造簽名。

4．1群成員偽造簽名、聯(lián)合攻擊、非群成員的偽造攻擊

由文獻(xiàn)[10]中方案的安全性分析可知，任何得到簽名(c，T，xiP)的人無法計算出簽名用戶的簽名密鑰SID，i或秘密信息xi，因此無法偽造滿足驗證等式的有效簽名，即上述方案可抵抗群成員偽造簽名、聯(lián)合攻擊、非群成員的偽造攻擊。

4．2KGC偽造簽名

若KGC偽造成員M進(jìn)行簽名，KGC隨機選取x′i∈Zq，計算

Q′ID，i=H2(IDKGC，x′iP)

S′ID，i=sH2(IDKGC，x′iP)

再隨機選擇A′∈G1，計算

c′=H1(m，e(A′，P))

T′=A′-c′×S′ID，i-cx′iQ′ID，i

顯然簽名(c′，T′，x′iP)滿足驗證等式。

但當(dāng)用戶M對簽名提出異議時，仲裁機構(gòu)可要求KGC出示用戶對xiP的簽名σi。由于KGC無法偽造有效的σi，偽造群簽名失敗。

4．3不關(guān)聯(lián)性

本方案中每個秘密信息xi只使用一次，但在用戶加入群組的過程中，用戶可產(chǎn)生多個秘密信息，每次簽名使用不同的秘密信息，即能保證簽名的不關(guān)聯(lián)性。

5結(jié)束語

本文對XC方案的安全性進(jìn)行了分析，并基于Hess方案提出一個可刪除群簽名方案。該方案由于簽名的驗證公鑰由KGC的身份信息計算而得，不包含用戶的任何身份信息，簽名過程得以簡化，簽名長度更短。

參考文獻(xiàn)：

[1]CHAUM D， HEYST E van. Group signatures[C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 1991: 257－265.

[2]CHEN L， PEDERSEN T P. On the efficiency of group signatures providing informationtheoretic anonymity [C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 1995:171181.

[3]CAMENISH J. Efficient and generalized group signatures[C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 1997: 465－479.

[4]PETERSEN H. How to convert any digital signature scheme into a group signature scheme[C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 1997: 67－78.

[5]CAMENISH J，STADLER M. Efficient group signatures for large groups[C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 1998:160174.

[6]KIM H J， LIM J I， LEE D H. Efficient and secure member deletion in group signature schemes[C]//Lecture Notes in Computer Science. Berlin: SpringerVerlag， 2000:150161.

[7]SONG Xiaodong. Practical forward secure group signature schemes[EB/OL]. http://tdt.sjtu.edu.cn/.

[8]陳澤文.一種基于中國剩余定理的群簽名方案[J]. 電子學(xué)報， 2004，32(7): 10621065.

[9]CHEN Xiaofeng， ZHANG Fangguo， KIM K. A new IDbased group signature scheme from bilinear pairings[EB/OL]. (2003).http://eprint.iacr.org/.

[10]HESS F. Exponent group signature schemes and efficient identity based signature schemes based on pairings[EB/OL]. (2002).http://eprint.iacr.org/.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”