一種新型的群盲簽名方案

摘要：提出了一種新型的可證明安全性的群盲簽名——ID群盲簽名方案。與LR98群盲簽名方案不同的是，新方案的安全性建立在計算DiffieHellman問題假設和隨機預言機模型之上，并且用戶在盲化簽名者的內容時，算法效率比LR98高。在盲化CZK的ID群簽名方案時，僅添加了模加運算，而LR98群盲簽名方案在盲化CS97群簽名方案時，則添加了求雙重離散對數、離散對數根以及隨機置換運算。兩者比較，新提出方案的計算復雜度更低，效率更高。關鍵詞：ID群簽名； 群盲簽名； 信息安全

中圖分類號：TP309．2文獻標志碼：A

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

群簽名是傳統的多人簽名概念的推廣。在群簽名方案中， 群體的成員可代表整個群體簽名， 每個成員的群簽名均可用統一的群體公鑰驗證， 而且對于給定的信息和簽名， 只有群體管理員才能確定簽名者的身份。群體數字簽名最先由文獻[1]提出。其中最著名的群體簽名方案是文獻[2]中的方案，它滿足群簽名的所有安全需求，并且其群公鑰尺寸與群體大小無關，是個常數，且群公鑰在群體生命周期中保持不變。

盲簽名首先由Chaum[3]提出。在電子貨幣系統中，簽名體制使得消費者的身份得以隱藏。盲簽名實際上是簽名者與用戶之間的一個雙方交互式協議，它要求簽名者在不知道文檔的內容情況下對其簽名，并且即便簽名者知道了簽名與文檔對，他也無法將它們聯系起來，雖然簽名者能夠驗證該簽名的確是他簽的。在電子貨幣系統中，文檔相當于電子貨幣，簽名者相當于銀行。消費者在使用貨幣時其身份是匿名的，因為他們使用的電子貨幣是銀行盲發行的。在文獻[4~6]中，盲簽名的概念、性質、安全性、應用等均得到了深入的研究。如同文獻[5]，本文提出的群盲簽名方案的安全性是在隨機預言機模型[7]下論證的。

群盲簽名的概念由A. Lysyanskaya等人[8]提出。他們利用群盲簽名構建了新的電子貨幣體制，即分布式電子銀行。不同于以往的電子貨幣體制，電子貨幣可由多個電子銀行發布。由于群盲簽名概念的提出使得電子貨幣的應用更為廣泛：電子貨幣由單一的銀行發布變為由多個銀行發布。

ID 群簽名方案首先由S. Park等人[9]提出。該方案的效率不高，群公鑰和簽名的長度與群的大小成正比，并且方案中的群公鑰包含群成員的身份，因此該方案不能滿足群簽名的匿名性。目前最好的ID 群簽名方案是由Chen等人[10](簡稱CZK)提出的，該方案的群公鑰和簽名長度與群的大小無關，保持不變，方案的安全性是建立在他們提出的基于ID的公鑰加密方案之上，是可證明安全的ID群簽名方案。本文就是在CZK方案的基礎上構建新的群盲簽名方案，即ID群盲簽名方案。

1預備知識

1．1雙線性對

G1是階數為素數q的加法循環群，由生成元P生成；G2是階數為素數q的乘法循環群；a、b是Zq中的兩個元素。假定在群G1和G2中離散對數問題是難解問題。雙線性對是具有下列三個特性的映射e：G1×G1 → G2。

a）雙線性。e(aP，bQ)=e(P，Q)ab。

b)非退化性。存在P，Q∈G1使得e(P，Q)≠1成立。

c)可計算性。對于所有的P，Q∈G1，存在有效的算法計算e(P，Q)。

1．2Gap DiffieHellman群

G1是階數為素數q的加法循環群，由生成元P生成。群G1中存在下列三個問題：

a)離散對數問題(DLP)。給定兩個元素P、Q，計算n∈Zq，使得Q=nP。

b)計算DiffieHellman問題(CDHP)。給定P、aP、bP，a，b∈Zq，計算abP。

c)判定DiffieHellman問題(DDHP)。給定P、aP、bP、cP，a，b，c∈Zq，判斷c≡ab mod q。

筆者稱G1是Gap DiffieHellman 群，如果它滿足在該群中存在算法在多項式時間內解決DDHP，但不存在概率多項式的算法以不可忽略的概率解決CDHP或DLP。這樣的群可在超奇異橢圓曲線中找到。雙線性對可由Weil或Tate對構建，請參閱文獻[11，12]。

1．3利用雙線性對構建基于ID的公鑰加密方案

基于ID的公鑰加密方案首先由Shamir[13]提出，它利用用戶的姓名、住址或電子郵件地址，而不是任意的字符串作為用戶公鑰；用戶的私鑰由私鑰生成器產生并通過秘密通道傳給用戶?；贗D的公鑰加密方案可通過以下方式構建：

G1是階數為素數q的加法循環群，由生成元P生成；G2是階數為素數q的乘法循環群。雙線性對映射為e:G1×G1 → G2。定義兩個理想的哈希函數H1:{0，1} → Zq，H2:{0，1} → G1。

1)系統參數的建立私鑰生成器隨機選取s∈Zq，令Ppub=sP。私鑰生成器公布參數：params={G1，G2，e，q，P，Ppub，H1，H2}，秘密保留s，將其作為其主密鑰。

2)用戶私鑰的提取用戶將他的身份ID（其公鑰）傳給私鑰生成器，私鑰生成器計算SID=sH2(ID)并將其傳給用戶。

1．4CZK的ID群簽名方案

筆者簡單地敘述CZK的ID群簽名方案。G1是階數為素數q的Gap DiffieHellman群；G2是階數為素數q的乘法循環群。雙線性對映射為e:G1×G1 → G2。定義兩個理想的哈希函數H1:{0，1}×G1 → Zq，H2:{0，1}×G1 → G1。

群管理員隨機選取s∈Zq，令Ppub=sP。群管理員保留s作為他的主密鑰，公布群公鑰Y={G1，G2，e，q，P，Ppub，H1，H2}。用戶隨機選取r∈Zq，用戶將r作為他的長期密鑰，計算rP，將其身份ID和rP傳給群管理員。群管理員計算SID=sH2(ID‖T，rP）并將其傳給用戶。其中T是用戶長期密鑰r的生命周期。用戶的私鑰對為〈r，SID〉，公鑰為其身份ID。需要注意的是，用戶的私鑰對〈r，SID〉與公鑰ID用于CZK構建的基于ID的公鑰加密方案，而CZK的ID群簽名方案是建立在基于ID的公鑰加密方案之上的。請參閱CZK方案[10]。CZK的ID群簽名方案分為四個協議：

a)加入協議

(a)用戶隨機選取xi∈Zq（i=1，2，…，k），然后將rxiP、xiP、rP、ID、SID傳給群管理員；

(b)如果SID=sH2(ID‖T，rP)，e(rxiP，P)=e(rP，xiP)，群管理員計算Si=sH2(T，rxiP)（i=1，2，…，k），并將其傳給用戶；

(c)用戶的成員證書為(Si，rxiP)，其私鑰為rxi；

(d)群管理員將rxiP、xiP、rP、ID添加到成員列表中。

b)簽名協議

簽名者的簽名密鑰為rxi，成員證書為〈Si，rxiP〉。簽名者的簽名過程如下：

(a)簽名者隨機選取a∈Zq，令U=aH2(T，rxiP)；

(b)V=rxiH2(m，U)；

(c)h=H1(m，U+V)；

(d)W=(a+h)Si；

(U，V，W，T，rxiP)就是關于消息m的簽名。

c)驗證協議

驗證者首先檢驗T是否合法，然后計算H2(T，rxiP)，H2(m，U)，h=H1(m，U+V)。

驗證者承認簽名是合法的，如果下面等式成立：

e(W，P)=e(U+hH2(T，rxiP)，Ppub)

d)打開協議

給定一個合法的群簽名，群管理員通過下面兩個等式可以很容易地確定簽名者的身份：

e(rxiP，P)=e(xiP，rP)；

e(SID，P)=e(H2(ID‖T，rP)，Ppub)

2ID群盲簽名方案

該ID群盲簽名方案首先將CZK的ID群簽名方案中的非交互式簽名協議轉換為交互式簽名協議；然后將交互式簽名協議盲化而成。下面為具體步驟：

用戶第0輪：用戶需要信息m的盲簽名， 就向簽名者發送一個簽名請求;

簽名者第1輪：隨機選取a∈Zq，計算U=aH2(T，rxiP)并將U傳給用戶；

用戶第2輪：隨機選取b∈Zq，計算U′=U+bP和H2(m，U′)，并將H2(m，U′)傳給簽名者；

簽名者第3輪：計算V=rxiH2(m，U′)并將V傳給用戶；

用戶第4輪：計算V′=V+bP，h′=H1(m，U′+V′)并將h′傳給簽名者；

簽名者第5輪：計算W=(a+h′)Si并將W傳給用戶；

用戶第6輪：計算W′=W+bPpub。

筆者稱(U′，V′，W′，T，rxiP)為消息m的ID群盲簽名。

下面，通過定理1和2分別說明本方案的正確性及其盲化性質。

定理1方案的正確性。

證明給定一個簽名(U′，V′，W′，T，rxiP)，驗證者首先計算h′=H1(m，U′+V′)和H2(T，rxiP)；然后驗證e(W′，P)=e(U′+h′H2(T，rxiP)，Ppub)是否成立。具體過程如下：

e(W′，P)=e(W+bPpub，P)=e(W，P)e(bP，Ppub)=

e((a+h′)Si，P)e(bP，Ppub)=e(asH2(T，rxiP)+h′sH2(T，rxiP)，P)

e(bP，Ppub)=

e(U+h′H2(T，rxiP)+bP，Ppub)=e(U′+h′H2(T，rxiP)，Ppub）

證畢。

定理2本方案中簽名者無法將其簽名(U′，V′，W′，T，rxiP)同消息m聯系起來。

證明通過用戶第2輪，用戶利用隨機數b盲化了簽名者的U，使其成為U′；同時，用戶通過哈希函數H2的隨機性盲化了消息m。在簽名者第3輪，由于哈希函數H2的隨機性以及用戶在第2輪中利用隨機數b盲化了簽名者的U，使得簽名者在不知道消息m以及U的情況下對其進行了簽名。由用戶第4輪可知，隨機數b盲化了簽名者的V，使其成為V′。簽名者第5輪在不知道其內容的情況下用證書Si對其簽名。在用戶第6輪，利用隨機數b盲化了簽名者的W。因此得證。

3方案的安全性分析

本章對ID群盲簽名方案的安全性進行分析。首先是簽名方案的安全性。

引理1[10]ID群盲簽名方案在隨機預言機模型和CDHP假設下是抗選擇消息攻擊的。

引理2如果存在時間為t、概率為ε的攻擊者A0可以偽造成員證書，那么就可以構造一個時間為t，概率為ε的攻擊者A1解決Gap DiffieHellman群G1中的CDHP。

證明考慮下面的游戲：假定攻擊者有選擇地詢問k次H2，在第i次的輸入為(T，rxiP)，他獲得相應的證書Si。最終，攻擊者輸出(rxP，S)，如果rxP沒有被詢問，并且e(S，P)=e(H2(T，rxP)，Ppub），就稱攻擊者贏得了游戲。

假定存在攻擊者A0在時間t內以不可忽略的概率ε偽造成員證書，可以構造攻擊者A1如下：

a)隨機選取整數u∈{1，2，…，k}，定義Cer(H2(T，rxiP))=Si；

b)對于i=1，…，k，攻擊者A1代替A0回答關于H2和Cer的詢問，當i=u時，A1用x替代xu；

c)A0輸出(rxoutP，Sout)；

d)如果xout=x，并且Sout是合法的證書，A1輸出(rxP，S)。

由于整數u是隨機選取的，對于攻擊者A0來說，攻擊者A1給的詢問結果分布與真實環境下挑戰者給的詢問結果分布是無法區分的。同時，由于H2是隨機函數，如果A0的輸出證書Sout是合法的，那么H2(T，rxP)一定詢問了。

令H2(T，rxP)=aP，Ppub=bP，由e(S，P)=e(H2(T，rxP)，Ppub)可知，本文解決了群G1中的CDHP。

引理3ID群盲簽名方案中的交互式協議是關于簽名者ID的成員證書和簽名者的誠實驗證者的零知識的知識證明。

證明本證明利用了文獻[2]中的技巧，主要證明知識證明部分。驗證了知識提取器在得到兩個合法的簽名時恢復了與之相關的成員證書。

假定(U′，V′，W′，T，rxiP)和(U′，V″，W″，T，rxiP)是兩個關于m的合法簽名。令h′=H1(m，U′+V′)。因為e(W′，P)=e(U′+h′H2(T，rxiP)，Ppub)，由此可得

W′=s(U′+h′H2(T，rxiP))（1）

令h″=H1(m，U′+V″)，同樣地可以得到e(W″，P)=e(U′+h″H2(T，rxiP)，Ppub)。由此可知

W″=s(U′+h″H2(T，rxiP))（2）

由式（1）和（2）可得W′-W″=sh′H2(T，rxiP)-sh″H2(T，rxiP)，因此可得Si=sH2(T，rxiP)=(h′-h″)-1(W′-W″)。由此恢復出了成員證書。證畢。

定理3利用雙線性對構建的基于ID群盲簽名方案在隨機預言機模型和CDHP假設下可證明是安全的。

證明該方案滿足群盲簽名方案的所有特性：

a)正確性（定理1）；

b)盲性（定理2）；

c)不可偽造性（引理2）；

d)匿名性：由于xi是隨機選取的，rxiP沒有透露任何關于簽名者身份的信息給用戶，除了群管理員；

e)不可聯結性：給定rxiP和rxjP，在不知道xiP和xjP的情況下計算rP是困難的；

f)可追蹤性：群管理員可以打開合法的群盲簽名，因為他能提供一個關于簽名者簽名的零知識證明；

g)不可陷害性：由引理1可知，無論是群管理員還是群中的成員都不能偽造群中其他成員的簽名；

h)抗聯合攻擊性，由引理2和3可知，群中的部分成員串通一起也不能偽造一個群管理員不能打開的合法簽名。

4方案的效率分析

本方案中的群公鑰和群盲簽名的長度是固定的，方案中的簽名通信量是一個定值。群盲簽名中所涉及的算法效率高。

與LR98方案相比，本方案盲化群簽名時僅添加了模加運算，而LR98方案則添加了求雙重離散對數、離散對數根以及隨機置換運算。從計算復雜度考慮，本方案的復雜度低于LR98方案的復雜度。

5結束語

本文在CZK方案的基礎上構建了可證明安全的ID群盲簽名方案，方案中的群公鑰和群盲簽名的長度是固定的。本方案是可證明安全性的。與LR98方案比較，本方案的效率更高。對于不同的消息m，簽名者需要一個新的私鑰對對其進行簽名是本方案的缺點所在。

參考文獻：

[1]CHAUM D， HEYST E V. Group signatures[C]//Proc of EUROCRYPT’91. New York: SpringerVerlag， 1991:257－265.

[2]ATENIESE G， CAMENISCH J， JOYE M， et al. A practical and provably secure coalitionresistant group signature scheme[C]//Advances in Cryptology CRYPTO 2000， LNCS 1880. Heidelberg: SpringerVerlag， 2000:255－270.

[3]CHAUM D. Blind signatures for untraceable payments[C]//RIVEST R L， SHERMAN A， CHAUM D. Proc of CRYPTO’82. New York:[s.n.]， 1983:199－203.

[4]CHAUM D， FIAT A， NAOR M. Untraceable electronic cash[C]//GOLDWASSER S. Proc of CRYPTO’88， Lecture Notes in Computer Science 403.[S.l.]: SpringerVerlag，1988:319－327.

[5]POINTCHEVAL D， STERN J. Provably secure blind signature schemes[C]//RHEE M Y， KIM K. Proc of Advances in CryptologyASIACRYPT’96， Lecture Notes in Computer Science 1163.[S.l.]:SpringerVerlag，1996:252－265.

[6]JUELS A， LUBY M， OSTROVSKY R. Security of blind digital signatures[C]//Proc of CRYPTO’97， Lecture Notes in Computer Science 1294.[S.l.]: SpringerVerlag，1997:150164.

[7]BELLARE M， ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols[C]//Proc of the 1st ACM Conference on Computer and Communications Security.[S.l.]: Fairfax， 1993:62－73.

[8]LYSYANSKAYA A， RAMZAN Z. Group blind digital signatures: a scalable solution to electronic cash[C]//Proc of Int’l Conf on Financial Cryptography.New York:SpringerVerlag，1998:184－197.

[9]PARK S， KIM S， WON D. IDbased group signature[J]. Electroni￣cs Letters，1997，33(19):16161617.

[10]CHEN X， ZHANG F， KIMK. A new IDbased group signature scheme from bilinear pairings[EB/OL].(2003－11－06).http://eprint.iacr.org/2003/116.

[11]BONEH D， FRANKLIN M. Identitybased encryption from the Weil pairings[C]//Advances in CryptologyCRYPTO2001， LNCS 2139.[S.l.]: SpringerVerlag， 2001:213－229.

[12]HESS F. Efficient identity based signature schemes based on pairings[C]//Proc of the 9th Workshop on Selected Areas in Cryptography SAC 2002， LNCS2595.[S.l.]: SpringerVerlag，2002:310－324.

[13]SHAMIR A. Identitybased cryptosystems and signature schemes[C]//Advances in CryptologyCRYPTO’84， LNCS196.[S.l.]:SpringerVerlag， 1984:47－53.

[14]CAMENISCH J， STADLER M. Efficient group signature for large groups[C]//Proc of CRYPTO’97. New York: SpringerVerlag， 1997: 410－424.

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