一種適合大群組的完全匿名的短群簽名

摘 要：基于CS98加密方案和SDH假設(shè)，提出一種新的三元組(A，x，y)的零知識(shí)證明協(xié)議，并基于此協(xié)議構(gòu)造了一種可證明安全的短群簽名方案。該方案具有IND-CCA2完全匿名性，允許新成員動(dòng)態(tài)加入，并且群管理員不能偽造任何成員的簽名，具有不可陷害性。簽名長(zhǎng)度僅為1 534 bit。

關(guān)鍵詞：短群簽名；完全匿名性；CS98加密；IND-CCA2安全;不可陷害性

中圖分類號(hào)：TP393.08文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)06-2173-04

doi:10.3969/j.issn.1001-3695.2009.06.053

Short group signature with full anonymity for large groups

MA Hai-ying1， WANG Zhan-jun2， ZHANG Ya-juan1

(1.College of Computer Science Technology， Nantong University， Nantong Jiangsu 226019， China；2.School of Science， Nantong University， Nantong Jiangsu 226007， China)

Abstract:This paper presented a new zero-knowledge protocol for the triple(A，x，y)， which was based on CS98 encryption and SDH assumption. Using this protocol as a building block，constructed a new short group signature， which was provable secure. The scheme was of IND-CCA2-full-anonymity，allowed new members to join in the group dynamically， and group mana-ger couldn’tforge any member’s signature， then the scheme satisfied non-frameability.The signature is only 153 4 bit in size.

Key words:short group signature; full anonymity; CS98 encryption; IND-CCA2 secure; non-frameability

群簽名是一個(gè)非常有用的密碼學(xué)工具。在一個(gè)群簽名方案中，一個(gè)群體中的任意一個(gè)成員可以匿名的方式代表整個(gè)群體對(duì)消息進(jìn)行簽名，并且在有爭(zhēng)議時(shí)，群管理者可以確定簽名者的身份。群簽名方案有很多的應(yīng)用場(chǎng)合，如電子現(xiàn)金系統(tǒng)、投票協(xié)議等，然而群簽名在實(shí)際應(yīng)用中還有一些問(wèn)題需要解決，比如如何構(gòu)造一個(gè)適合大群組安全的短群簽名。

1991年，Chaum等人^[1]提出了群簽名的概念。近年來(lái)，有很多種安全高效的群簽名方案被提出，比較著名的有ACJT方案^[2]；2004年提出的基于SDH和決定線性假設(shè)的BBS方案^[3]，實(shí)現(xiàn)了高效的、長(zhǎng)度為1 533 bit的簽名，但該方案僅具有CPA完全匿名性。Bellare等人^[4]給出了群簽名安全的形式化模型，并首先提出一個(gè)標(biāo)準(zhǔn)模型下可證明安全的方案，采用的是廣義的非交互式零知識(shí)證明技術(shù)，所以效率較低，并不實(shí)用。Bellare等人^[5]針對(duì)動(dòng)態(tài)群將BMW模型作了擴(kuò)展（允許群成員動(dòng)態(tài)加入），提出了一個(gè)標(biāo)準(zhǔn)動(dòng)態(tài)群簽名方案的安全模型，在該模型中給出了一個(gè)動(dòng)態(tài)群簽名方案應(yīng)該具備的正確性和三個(gè)安全需求的實(shí)驗(yàn)。Boyen等人^[6]提出了第一個(gè)標(biāo)準(zhǔn)模型下的可證明安全并且實(shí)用的群簽名方案，而且該方案只依賴于相對(duì)弱的計(jì)算假設(shè)，即CDH假設(shè)和他們新引入的子群判定假設(shè)；該方案的缺點(diǎn)是群公鑰和簽名長(zhǎng)度與用戶數(shù)呈對(duì)數(shù)關(guān)系，因此群簽名的長(zhǎng)度隨群大小增長(zhǎng)。由于是在合數(shù)階群上進(jìn)行簽名，表示群簽名的每一個(gè)元素都非常長(zhǎng)，一個(gè)完整的群簽名通常要數(shù)萬(wàn)比特。2007年，Boyen等人^[7]采用新的非交互零知識(shí)證明技術(shù)提出一個(gè)簽名長(zhǎng)度為常數(shù)的群簽名，但該方案依然是在合數(shù)階群上實(shí)現(xiàn)的，但模型的完全匿名性被弱化為CPA完全匿名性，即在試圖攻破匿名性定義時(shí)對(duì)攻擊者作了限制，不允許提問(wèn)打開(kāi)預(yù)言機(jī)。

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

1）雙線性群 設(shè)G1=〈g1〉，G2=〈g2〉和GT是階為素?cái)?shù)p的循環(huán)群；ψ是G2到G1的可計(jì)算的同構(gòu)映射，ψ(g2)=g1；e為可計(jì)算的映射e:G1×G2→GT，該映射具有雙線性和非退化性兩個(gè)性質(zhì)，則稱（G1，G2）是一對(duì)雙線性群。

2）q-SDH假設(shè) 如果對(duì)任意概率多項(xiàng)式時(shí)間（簡(jiǎn)寫為ppt）算法A，解決q-SDH問(wèn)題^[8]的概率是可以忽略的。

3)DDH假設(shè) 如果對(duì)任意ppt算法A，解決DDH問(wèn)題^[9]的概率是可以忽略的，則稱DDH假設(shè)成立。

4)CDH假設(shè) 如果對(duì)任意ppt算法A，解決CDH問(wèn)題^[9]的概率是可以忽略的。5)XDH假設(shè) 設(shè)G1、G2和GT是階為素?cái)?shù)p的循環(huán)群，ψ:G2→G1為單向同構(gòu)映射e:G1×G2→GT為雙線性映射，DDH問(wèn)題在G2中是容易的，但是在G1中是困難的。

2 一種新的(A，x，y)的零知識(shí)證明協(xié)議

本文基于DDH假設(shè)下的CS98加密方案和SDH假設(shè)給出了擁有三元組(A，x，y)知識(shí)的一種新的零知識(shí)證明協(xié)議。該協(xié)議是群簽名方案的一個(gè)構(gòu)造模塊， 用來(lái)證明簽名者擁有一個(gè)合法的(A，x，y)。

選擇素?cái)?shù)階為p的雙線性群G1、G2、GT，其生成元分別為g1、g2、gT，雙線性映射e:G1×G2→G T，H:{0，1}→Zp是抗碰撞的哈希函數(shù)；w=g2γ，γ∈Zp。隨機(jī)選擇x1，x2，x3，x4，x5∈Zp，計(jì)算y1=g1x1hx2，y2=g1x3hx4，y3=g1x5。其中h∈G1。三元組(A，x，y)滿足e(A，wgx2)×e(k，g2)-y=e(g1，g2)，其中A∈G1，x∈Zp且Ax+γ=g1ky，k∈G1。下面使用協(xié)議1證明素?cái)?shù)階群上離散對(duì)數(shù)的知識(shí)。

協(xié)議1 示證者Alice隨機(jī)選擇α∈Zp，計(jì)算A的CS98加密T1=gaα，T2=hα，T3=y3αA，T4=y1αy2αQ，其中Q=H(T1，T2，T3)；然后計(jì)算輔助值δ=αx。Alice和驗(yàn)證者Bob進(jìn)行滿足以下等式的值(α，x，y，δ)的知識(shí)證明：

T1=gaα，T2=hα，T4=y1αy2αQ，Tx1g-δ1=1，Tx2h-δ=1，Tx4y-δ1y-δQ2=1，e(T3，g2)x×e(y3，g2)-δ×e(y3，w)-α×e(k，g2)-y=e(g1，g2)/e(T3，w)。

證明 Alice隨機(jī)選擇rα，rx，ry，rδ∈Zp，計(jì)算R1=grα1，R2=hrα，R3=e(T3，g2)rx×e(y3，w)-rα×e(y3，g2)-rδ×e(k，g2)-ry，R4=y1rαy2rαQ，R5=T1rxg1-rδ，R6=T2rxh-rδ，R7=T4rxy1-rδy2-rδQ，然后將(T1，T2，T3，T4，R1，R2，R3，R3，R5，R6，R7)發(fā)送給Bob。Bob在Zp中隨機(jī)選擇詢問(wèn)值c發(fā)送給Alice。Alice計(jì)算并發(fā)送回sα=rα+cα，sx=rx+cs，sy=ry+cy，sδ=rδ+cδ∈Zp；最后，Bob驗(yàn)證以下七個(gè)等式：

g1sα=R1×T1c（1）

hsα=R2×T2c（2）

e(T3，g2)sx×e(y3，g2)-sδ×e(y3，w)-sα

×e(k，g2)-sy=R3×(e(g1，g2)/e(T3，w))c(3)

y1sαy2sαQ=R4×T4c（4）

T1sx×g1-sδ=R5（5）

T2sxh-sδ=R6（6）

T4sxy1-sδy2-sδQ=R7（7）

如果以上七個(gè)等式都成立，Bob接受證明。

定理1 協(xié)議1是誠(chéng)實(shí)驗(yàn)證者在 DDH假設(shè)下三元組（A，x，y）知識(shí)的零知識(shí)證明。

定理1的證明可以通過(guò)以下三個(gè)引理的證明得出。

引理1 協(xié)議1是完備的，即驗(yàn)證者總是接受與一個(gè)誠(chéng)實(shí)示證者的交互。

證明 如果Alice是一個(gè)擁有（A，x，y）的誠(chéng)實(shí)示證者，并且遵守協(xié)議1中規(guī)定的指令，那么式(1)~(7)必然成立。

首先，g1sα=g1rα+cα=(g1α)c×g1rα=R1×T1c，所以式（1）成立，類似地式（2）成立；然后，y1sαy2sαQ=y1rα+cαy2(rα+cα)Q=y1rαy2rαQ(y1αy2αQ）c=R4×T4c，所以式（4）成立，類似式（5）~（7）成立；最后e(T3，g2)sx×e(y3，w)-sα×e(y3，g2)-sδ×e(k，g2)-sy=e(T3，g2)rx+cx×e(y3，g2)-rδ-cδ×

e(y3，w)-rα-cα×e(k，g2)-ry-cy=(e(T3，gx2)×e(y3-α，w)×e(y3-α，gx2)×e(k，g2)-y×e(T3，w)/e(T3，w))c×R3=(e(A，g2xw)×e(k，g2)-y/e(T3，w))c×R3=(e(g1，g2)/e(T3，w))c×R3，所以式（3）成立，對(duì)Bob隨機(jī)選取詢問(wèn)值的所有情況，Alice的應(yīng)答都能滿足他每一步的驗(yàn)證。

引理2 協(xié)議1的副本在DDH假設(shè)下可以仿真。

證明 首先描述一個(gè)輸出協(xié)議1證明副本的仿真器。選取A∈G，α∈Zp，令T1=gα，T2=hα，T3=y3α A，T4=y1αy2αQ，其中Q=H(T1，T2，T3)，假設(shè)DDH假設(shè)在群G上成立。由仿真器生成的四元組(T1，T2，T3，T4)的分布與任一示證者輸出的分布是不可區(qū)分的。仿真器的剩余部分沒(méi)有用到知識(shí)A、x、y或α，所以當(dāng)T1、T2、T3、T4預(yù)先指定時(shí)仍可以使用，當(dāng)預(yù)先指定的T1、T2、T3、T4是某個(gè)A的隨機(jī)CS98加密時(shí)，證明的副本的剩余部分可以被完美仿真。

隨機(jī)選擇詢問(wèn)值c∈Zp和sα，sx，sy，sδ∈Zp，計(jì)算R1=g1sα×T1-c，R2=hsα×T2-c，R3=e(T3，g2)sx×e(y3，w)-sα×e(y3，g2)-sδ×e(k，g2)-sy×（e(g1，g2)/e(T3，w))c，

R4=y1sαy2sαQ×T-c4，R5=T1sxg1-sδ，R6=T2sxh-sδ，R7=T4sxy1-sδy2-sδQ。上述值顯然滿足式（1）~（7），此時(shí)仿真器輸出(T1，T2，T3，T4，R1，R2，R3，R4，R5，R6，R7，c，sα，sx，sy，sδ)的值分布與實(shí)際的協(xié)議副本相同。

引理3 存在一個(gè)協(xié)議1的提取器。

證明 在協(xié)議1的第一步，示證者向驗(yàn)證者發(fā)送(T1，T2，T3，T4，R1，R2，R3，R4，R5，R6，R7，c，sα，sx，sy，sδ)。對(duì)于不同的詢問(wèn)值c和c′，示證者的響應(yīng)分別為(sα，sx，sy，sδ)和(s′α，s′x，s′y，s′δ)，它們均要滿足式（1）~（7），令Δc=c-c′，Δsα=sα-s′α，Δsx，Δsy，Δsδ定義與前面類似。將上述兩組值集代入式（1）~（7），得到上述等式的兩個(gè)實(shí)例。

將式（1）的兩個(gè)實(shí)例等號(hào)兩邊分別相除，得

g1Δsα=T1Δc。由于指數(shù)是素?cái)?shù)階群的元素，對(duì)g1Δsα=T1Δc求根運(yùn)算得g1=T1，其中

=Δsα/Δc。類似地由式（2）可得

h=T2，式（4）可得

y1y2Q=T4，

式（5）兩端分別相除得

g1Δsδ=T1Δsx，將T1=g1代入得

g1Δsδ=g1Δsx，得

Δsδ=Δsx。最后將式（3）的兩個(gè)實(shí)例等號(hào)兩邊分別相除，

e(T3，g2)Δsx×e(y3，g2)-Δsδ×e(y3，w)-Δsα×e(k，g2)-Δsy=(e(g1，g2)/e(T3，w))Δc

令Δsx/Δc=，Δsy/Δc=，對(duì)上式兩邊去Δc得e(T3，g2)×e(y3，g2)-α×e(y3，w)-×

e(k，g2)-=e(g1，g2)/e(T3，w)。令=T3y-α3，可得

e(，wg2)×e(k，g2)-=e(g1，g2)，因此提取器得到了三元組(，，)。這個(gè)三元組與CS98加密(T1，T2，T3，T4)中的三元組相同。

3 完全匿名的動(dòng)態(tài)短群簽名

3.1 系統(tǒng)初始化

選擇素?cái)?shù)階為p的雙線性群G1、G2、GT，其生成元分別為g1、g2、gT，雙線性映射e:G1×G2→GT，H:{0，1}→Zp是抗碰撞的哈希函數(shù)；w=g2γ，γ∈Zp，γ是群管理員的私鑰。打開(kāi)管理者隨機(jī)選擇x1，x2，x3，x4，x5∈Zp作為自己的私鑰，計(jì)算y1=g1x1hx2，

y2=g1x3hx4，y3=g1x5。其中h∈G1，群公鑰gpk為(g1，g2，gT，y1，y2，y3，h，w，k)。

3.2 新成員的加入

用戶ui隨機(jī)選擇y∈Zp作為自己的私鑰，計(jì)算C=ky，將申請(qǐng)的身份信息id和C提交給群管理員。在群管理員對(duì)身份信息認(rèn)可的前提下，群管理員首先驗(yàn)證C∈G1，計(jì)算H(id)→x，A=(g1C)1/(γ+x)，將(A，x)通過(guò)安全信道發(fā)送給用戶。用戶收到信息后，驗(yàn)證e(A，wgx2)×e(k，g2)-y=e(g1，g2)，如果相等則接收成員證書(A，x)，否則返回出錯(cuò)消息給群管理員。群管理員將reg[i]=(id，A，x)添加到注冊(cè)表reg。此時(shí)ui擁有自己合法的群簽名私鑰Kid=(A，x，y)。

3.3 產(chǎn)生簽名

該算法的參數(shù)為群公鑰gpk 、用戶i的私鑰Kid和待簽消息M∈{0，1}。用戶ui首先執(zhí)行協(xié)議1第一輪中規(guī)定的計(jì)算，得到T1、T2、T3、T4、R1、R2、R3、R4、R5、R6、R7，將上述值與消息M進(jìn)行hash運(yùn)算后獲得詢問(wèn)值c，即c←H2（T1、T2、T3、T4、R1、R2、R3、R4、R5、R6、R7，M），然后執(zhí)行第三輪規(guī)定的計(jì)算得到sα、sx、sy、sδ，最后，輸出簽名σ←(T1，T2，T3，T4，c，sα，sx，sy，sδ)。

3.4 驗(yàn)證簽名

給定群公鑰gpk、消息M和群簽名δ，驗(yàn)證該簽名是否為知識(shí)(A，x，y)的有效簽名，驗(yàn)證者根據(jù)協(xié)議1中的式（1）~（7）重推R1~R7，1=g1sα×T1-c，2=hsα×T2-c，3=e(T3，g2)sx×e(y3，g2)-sδ×e(y3，w)-sα×e(k，g2)-sy×（e(g1，g2)/e(T3，w))c，4=y1sαy2sαQT-c4，5=T1sxg1-sδ，6=T2sxh-sδ，7=T4sx×y1-sδy2-sδQ，然后計(jì)算c=?H2(

T1，T2，T3，T4，1，2，3，4，5，6，7，M)，如果等式成立，則驗(yàn)證者接受。

3.5 打開(kāi)簽名

打開(kāi)管理者利用自己私鑰對(duì)群簽名中的（T1，T2，T3，T4）進(jìn)行解密獲得成員的證書。計(jì)算如下：打開(kāi)者首先計(jì)算Q=H(T1，T2，T3)，然后驗(yàn)證Tx1+x3Q1

Tx2+x4Q4是否等于T4，如果相等，則T3/Tx51=gTx5αA/gTx5α=A。

4 安全性分析 

動(dòng)態(tài)群簽名方案必須滿足四個(gè)安全屬性^[4]:a)正確性。誠(chéng)實(shí)簽名者生成的簽名能被正確驗(yàn)證和追蹤。b)完全匿名性。簽名不會(huì)泄露它的簽名者的身份。c)完全可追蹤性。所有的簽名，即使是用戶與群管理員合謀生成的簽名都要能被打開(kāi)和追蹤。d)防陷害性。本文中的群簽名的安全性可由以下四個(gè)定理的證明得出。

定理2 本文中的群簽名是正確的。

證明 對(duì)于群公鑰gpk=(g1，g2，gT，y1，y2，y3，h，w，k)和某一用戶的私鑰gsk[i]=(A，x，y)，密鑰生成算法確保A←(g1C)1/(γ+x)。本文的簽名σ是第2章協(xié)議1的一個(gè)副本，是關(guān)于知識(shí)（A，x，y）的知識(shí)證明，簽名驗(yàn)證等價(jià)于驗(yàn)證協(xié)議副本是正確的，由引理1可知，σ總是被驗(yàn)證者接受。由誠(chéng)實(shí)驗(yàn)證者產(chǎn)生的簽名中，（T1，T2，T3，T4）是A的CS98加密，擁有密鑰（x1，x2，x3，x4，x5）的打開(kāi)管理者能夠解密得出A。因此任何有效的簽名總能被正確打開(kāi)。

定理3 若敵手A以優(yōu)勢(shì)ε經(jīng)qS次簽名提問(wèn)和qH次hash提問(wèn)攻破本文簽名方案的IND-CCA2完全匿名性，則可以構(gòu)造敵手B以優(yōu)勢(shì)ε/ 2-(qH+qS )/p4攻破CS98加密方案的IND-CCA2安全性。

證明 設(shè)算法A以(t，qS，qH，ε)攻破群簽名方案的IND-CCA2完全匿名性，構(gòu)造一個(gè)算法B以至少ε的優(yōu)勢(shì)攻破改進(jìn)CS98加密的IND-CCA2安全性。給算法B CS98加密的公鑰(y1，y2，y3，h，g1)，由它根據(jù)群簽名方案的密鑰生成算法產(chǎn)生其余的群公鑰，然后算法B向算法A提供群公鑰(g1，g2，gT，h，y1，y2，y3，w，k)和用戶私鑰gsk[i]=(A，x，y)以及打開(kāi)管理者密鑰(x1，x2，x3，x4，x5)。

在任何時(shí)候算法A都可以提問(wèn)隨機(jī)預(yù)言機(jī)H，算法B以Zp中均勻隨機(jī)地選擇的元素作為應(yīng)答，但要保證對(duì)相同提問(wèn)的應(yīng)答是相同的。算法B要回答A的所有打開(kāi)提問(wèn)，當(dāng)算法A發(fā)出打開(kāi)提問(wèn)時(shí)，算法B應(yīng)用解密預(yù)言機(jī)檢驗(yàn)簽名是否有效，然后B將簽名的加密部分提交解密預(yù)言機(jī)，從明文中提取簽名者身份發(fā)送給A。

算法A提出兩個(gè)群成員標(biāo)志i0、i1以及消息M，發(fā)起用兩個(gè)群成員標(biāo)志i0、i1中的某一個(gè)對(duì)消息M的簽名提問(wèn)。算法B選擇隨機(jī)比特b∈{0，1}，用私鑰gsk[ib]生成一個(gè)消息M的簽名，然后發(fā)送給算法A；A向打開(kāi)預(yù)言機(jī)發(fā)起打開(kāi)提問(wèn)，驗(yàn)證簽名有效性，有效性的證明可以通過(guò)協(xié)議1的仿真器模擬，驗(yàn)證過(guò)程在獲取隨機(jī)預(yù)言機(jī)值時(shí)僅以一個(gè)可忽略的概率(qH+qS)/p4失敗，這時(shí)算法B中止，否則說(shuō)明(T1，T2，T3，T4，c，sα，sx，sy，sδ)是消息M的一個(gè)有效簽名，并輸出b 的一個(gè)猜測(cè)比特。采用與文獻(xiàn)[12]相同的分析方法，可以得出算法A以ε/2的優(yōu)勢(shì)區(qū)分(A，x，y)，此時(shí)算法B攻破群G1上的DDH假設(shè)，即敵手B以ε/2-(qH+qS)/p4攻破XDH假設(shè)。

定理4 若敵手A以優(yōu)勢(shì)ε經(jīng)qS次簽名提問(wèn)和qH次hash提問(wèn)攻破本文簽名方案的可追蹤性，則可以構(gòu)造敵手B以優(yōu)勢(shì)(ε-1/p)2/(16qH)解(n+1)-SDH實(shí)例，或敵手B′以優(yōu)勢(shì)(ε/n -1/p)2/(16 qH)解n-SDH實(shí)例。

證明 假設(shè)存在敵手A以優(yōu)勢(shì)ε打破完全匿名性游戲，構(gòu)造一個(gè)算法B，可以打破SDH問(wèn)題。設(shè){(Ai，xi，yi)}qi=1，其中q=q1+q2為攻擊過(guò)程中產(chǎn)生的證書；進(jìn)一步令{(Ai，xi，yi)}qi=1是誠(chéng)實(shí)用戶，他們?cè)诠暨^(guò)程中可以被完全腐化（通過(guò)詢問(wèn)私鑰預(yù)言機(jī)）。{(Ai，xi，yi)}q1+q2i=1為腐化用戶。

如果敵手A產(chǎn)生了一個(gè)簽名，打開(kāi)追蹤到A（一個(gè)不存在的用戶），用文獻(xiàn)[9]中引理8相同的方法可以產(chǎn)生一個(gè)新的證書(A，x，y*)，從攻擊過(guò)程看A{Ai}qi=1，令B被給定q-SDH串(G，G′，θG′，…，θqG′)。

定理5 群簽名方案是可追蹤的。

證明 假設(shè)存在一個(gè)敵手A以ε的優(yōu)勢(shì)打破方案的可追蹤性，描述一個(gè)算法B在A的幫助下可打破SDH問(wèn)題。

令{(Ai，xi，yi)}qi=1，其中q=q1+q2是整個(gè)攻擊過(guò)程中所涉及到的證書，準(zhǔn)確地說(shuō){（Ai，xi，yi）}q1i=1是誠(chéng)實(shí)用戶，可通過(guò)詢問(wèn)私鑰預(yù)言機(jī)被賄賂，{（Ai，xi，yi）}q1+q2i=q1+1是敵手A自己增加的用戶。

如果敵手A可產(chǎn)生一個(gè)簽名，該簽名被追蹤到A（A為不存在的用戶），用文獻(xiàn)[9]中引理8不可偽造性的方法，可以得到一個(gè)證書(A，x，y*)，由追蹤性實(shí)驗(yàn)可知

(A，x，y){（Ai，xi，yi）}qi=1。假設(shè)給定B一個(gè)q-SDH串(G，G′，θG′θ，…，G′θq)，G=ψ(G′)，B計(jì)算：

a）任取α∈Zp，xi∈Zp，i=1，2，…，q，要求xi兩兩互不相等。b）任取yi∈Zp，i=1，…，q1，k∈{1，2，…，q1}，定義γ=θ-xk，γ未知。c）從q-SDH串中計(jì)算，g2=G′αqi=1(θ+xi-xk)×G′-yki≠k(θ+xi-xk)，g1=ψ(G2)，k=Gi≠k(θ+xi-xk)，w=gγ2。d）任取打開(kāi)管理員私鑰，并計(jì)算相應(yīng)的加密密鑰。e）產(chǎn)生可拔出協(xié)議^[9]，但是知道陷門。f）模仿第一類用戶{(Ai，xi，yi)}q1i=1，根據(jù)i計(jì)算Ai=(g1kyi)1/(γ+xi)，若i=k， Ak=(kαθ)1/(γ+xk)=G

αi≠k(θ+xi-xk)；若i≠k，yi=(yi-yk)+yk，kyi-yk

=G(yi-yk)i≠k(θ+xi-xk)， Ai=(g1kyi)1/(γ+xk)=(g1kykkyi-yk)1/(xi+r)=Gαj≠i(θ+xi-xk)×G(yi-yk)j≠i，k(θ+xi-xk)。g）A利用所需預(yù)言機(jī)模型產(chǎn)生用戶ui(i=q1+1，…，q1+q2)，B用陷門計(jì)算與Ai、xi對(duì)應(yīng)的yi，由前知此時(shí)i≠k；最后，證書A滿足A=(g1×ky)1/(x+γ)=g(αθ+y-yk)/(x+θ-xk)i≠k(θ+xi-xk)，因?yàn)锳{Ai}qi=1，所以A≠Ak，y-yk≠α(x-xk)。

有兩種情況可能發(fā)生：a）x∈{x1，…，xq}的概率大于1/2，因?yàn)椴恢纊，對(duì)于j，可得x=xj(j≠k)的概率大于(q1-1)/2q，且有(Ayi×A-yj)1/(yj-y)=G1/(xi+θ-xk)，因此B得到(G1/(θ+x)，x)為q-SDH的解，其中x=xj-xk；b）x{x1，…，xq}的概率大于1/2，用輾轉(zhuǎn)相除法得A=g(c/(θ+x-xk)+p(θ))，其中c=(α(xk-x)+y-yk)i≠k(xi-x)≠0，P為一個(gè)q-1次多項(xiàng)式，這樣B可以在原始的式子中計(jì)算c和gP(θ)，最后得到(G1/(θ+x)，x)為q-SDH問(wèn)題的解。其中x=x-xk。

定理6 群簽名方案具有防陷害性。

證明 假定存在一個(gè)敵手A可攻破不可陷害性，描述一個(gè)算法B能攻破離散對(duì)數(shù)問(wèn)題。令{(Ai，xi，yi)}q+q′i=1為攻擊過(guò)程中所涉及到的證書，γ和所有的{(Ai，xi)}給了敵手A，因此敵手A知道所有的kyi但只知道賄賂集的{yi}qi=1。如果敵手A可以偽造一個(gè)被追蹤到A∈{Ai}q+q′i=q+1（賄賂集以外），用文獻(xiàn)不可偽造性相同的方法，可得證書(A，x，y)。有兩種情況可能發(fā)生：

a)A∈{Ai}q+q′i=q+1，但(A，x){(Ai，xi)}q+q′i=q+1的概率大于1/2，給定G2中的離散對(duì)數(shù)串(G，G′)，描述算法B可計(jì)算θ=logGG′。在此情況下，B計(jì)算群公鑰(G1，G2，GT，e，ψ，g1=ψ(G)，k=ψ(G′)，g2=G，w=Gγ)，其中γ∈Zp，則k=gθ1。因?yàn)锳=Aj

{Ai}q+q′i=q+1，x≠xj，所以y≠yj，有A=(g1×ky)1/(x+γ)=(g1×g1yθ)1/(x+γ)

=(g1×kyj)1/(xj+γ)=(g1×gyjθ)1/(xj+γ)，故(xj+γ)(1+yθ)=(x+γ)(1+yjθ)，且yj=y，θ=(xj-x)/((xj+γ)y-(x+γ)yj)。

b)（A，x){(Ai，xi)}q+q′i=q+1的概率大于1/2，給G1中離散對(duì)數(shù)問(wèn)題(G，G′)，則B可計(jì)算。B計(jì)算群公鑰(G1，G2，GT，e，ψ，g2∈G2，g1=ψ(g2)，k=G，w=gγ2)，其中γ∈Zp。因?yàn)锽有γ，所以可隨機(jī)選擇j=(q+1，…，q+q′)使得Aj=(g1×g′)1/(xj+γ)；因?yàn)?A，x)∈{(Ai，xi)}q+q′i=q+1，所以(A，x)=(Aj，xj)的概率為1/q′，故A=(g1×ky)1/(x+γ)=(g1×gy)1/(x+γ)

=Aj=(g1×g′)1/(xj+γ)=(g1×gθ)1/(xj+γ)=(g1×gθ)1/(x+γ)，θ=y。

5 簽名方案的性能分析

本文的短群簽名方案由四個(gè)群G1中的元素和五個(gè)Zp中的元素組成。參照文獻(xiàn)[10]中所描述的橢圓曲線族， 取p為170 bit的素?cái)?shù)，群G1中的元素為171 bit，則本文群簽名長(zhǎng)度為1 534 bit。



簽名的計(jì)算開(kāi)銷主要體現(xiàn)在雙線性對(duì)運(yùn)算、指數(shù)和多指數(shù)運(yùn)算，尤其以雙線性對(duì)運(yùn)算的開(kāi)銷最大，因此分析計(jì)算開(kāi)銷時(shí)，將指數(shù)和多指數(shù)運(yùn)算都?xì)w為指數(shù)運(yùn)算。由于雙線性對(duì)

e(g1，g2)，e(A，g2)，e(A，ω)，e(y3，g2)，e(y3，ω)和e(k，g2)均可以預(yù)計(jì)算， 并且e(T3，g2)=e(yα3A，g2)=e(y3，g2)α×e(A，g2)，使得計(jì)算e(T3，g2)無(wú)須雙線性對(duì)運(yùn)算，因此在簽名生成過(guò)程中需要11次指數(shù)運(yùn)算， 0次雙線性對(duì)運(yùn)算。在驗(yàn)證過(guò)程中，根據(jù)雙線性群的運(yùn)算性質(zhì)可以將e(T3，g2)sxe(T3，w)c合并為e(T2，gsx2wc)，因此需要七次指數(shù)運(yùn)算以及一次雙線性對(duì)運(yùn)算。

本文方案中的具體性能指標(biāo)在表1中分別列出。其中ME表示多指數(shù)運(yùn)算，BM表示雙線性運(yùn)算。從表1的各項(xiàng)數(shù)據(jù)比較中可以看出，本文的方案以一個(gè)強(qiáng)的假設(shè)為代價(jià)提高系統(tǒng)的效率和減少簽名長(zhǎng)度，與BBS短群簽名相比， 本文在保持簽名長(zhǎng)度基本不變的情況下，雖然計(jì)算開(kāi)銷上略有增加，但以很小的性能代價(jià)實(shí)現(xiàn)了更嚴(yán)格安全定義下的IND-CCA2完全匿名性，允許新的成員動(dòng)態(tài)加入，并且群管理員不能偽造任何成員的簽名，具有不可陷害性。與張方案^[10]相比，簽名長(zhǎng)度明顯減少，更適合大群組的應(yīng)用。

表1 短群簽名方案性能比較

簽名方案BBS方案^[3]張方案^[10]本文方案

簽名長(zhǎng)度1 533 bit1 704 bit1 534 bit

簽名過(guò)程計(jì)算量8ME+0BM11ME+0BM11ME+0BM

驗(yàn)證過(guò)程計(jì)算量6ME+1BM8ME+1BM7ME+1BM

匿名性CPA full anonymityIND-CCA2full anonymityIND-CCA2full anonymity加入新成員否否能

群管理員陷害成員能能否

6 結(jié)束語(yǔ)

本文基于IND-CCA2 安全的線性CS98公鑰加密方案，設(shè)計(jì)了一種新的三元組（A，x，y）的零知識(shí)證明協(xié)議，并根據(jù)該協(xié)議提出了一種新的具有IND-CCA2完全匿名性的動(dòng)態(tài)短群簽名，簽名的長(zhǎng)度為1 534 bit，簽名算法需要11次多指數(shù)運(yùn)算，而驗(yàn)證算法需要七次多指數(shù)運(yùn)算和一次雙線性對(duì)運(yùn)算。與BBS的短群簽名方案相比，在保持簽名長(zhǎng)度基本相同情況下，本文提出的短群簽名方案具有IND-CCA2完全匿名性，允許新的成員動(dòng)態(tài)加入，并且群管理員不能偽造任何成員的簽名，具有不可陷害性。

參考文獻(xiàn)：

［1］CHAUM D，HEYST E van.Group signatures[C]//Lecture Notes in Computer Science.Berlin:Springer-Verlag，1991:257-265.

[2]ATENIESE G，CAMENISCH J，JOYE M，et al.A practical and prova-bly secure coalition-resistant group signature scheme[C]//Proc of the 20th Annual International Cryptology Conference on Advances in Cryptology.London:Springer-Verlag，2000:255-270.

[3]BONEH D， BOYEN X， SHACHAM H. Short group signatures[C]//Proc of the 24th Annual International Cryptology Conference.Berlin:Springer-Verlag， 2004:41-55.

[4]BELLARE M，MICCIANCIO D， WARINSCHI B. Foundations of group signatures: formal definitions， simplified requirements， and aconstruction based on general assumptions [C]//Proc of EUROCRYPT.Berlin:Springer-Verlag，2003:614-629.

[5]BELLARE M， SHI Hai-xia，ZHANG Chong.Foundations of group signatures:the case of dynamic groups[C]//Proc of Cryptographers’ Track at the RSA Conference.Berlin: Springer-Verlag， 2005:136-153.

[6]BOYEN X，WATERS B.Compact group signatures without random oracles[C]//Proc of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer-Verlag，2006:427-444.

[7]BOYEN X，WATERS B.Full-domain subgroup hiding and constant- size group signatures[C]//Proc ofthe 10th International Conference on Practice and Theory in Public-Key Cryptography.Berlin: Springer- Verlag，2007: 1-15.

[8]DELERABLEE C，POINTCHEVAL D.Dynamic fully anonymous short group signatures[C]//Proc of the 1st International Conference on Cryptology in Vietnam.Berlin:Springer-Verlag，2006.

[9]CRAMER R， SHOUP V.A practical public key cryptosystem provably secure against adaptive chosen cipher text attack[C]//Proc ofthe 18th Annual International Crytology Conference on Adwance in Cryptology.Berlin:Springer-Verlag，1998:13-25.

[10]張躍宇，陳杰，蘇萬(wàn)力，等.一種IND-CCA2完全匿名的短群簽名[J].計(jì)算機(jī)學(xué)報(bào)，2007，30(10):1865-1871.