ＡＣＪＴ群簽名方案中一種新的成員撤銷方案
2007-01-01 00:00:00婁靜李喬良徐興中
計算機應用研究 2007年4期
摘要:在ACJT群簽名方案的基礎上，提出一個新的成員撤銷方案#65377;新方案中群公鑰的大小僅取決于群中成員的個數，不會隨著撤銷成員的增加而無限增大#65377;增加或撤銷一個成員，群管理者只需作乘法或除法運算來更新群公鑰，簽名和驗證過程更簡單，而且證明了新方案的安全性#65377;
關鍵詞:群簽名; 撤銷; ACJT方案
中圖分類號:TP309文獻標志碼:A
文章編號:10013695(2007)04012703
0引言
群簽名是由Chaum和Heyst[1]于1991年提出的#65377;在一個群簽名方案中，一個群體中的任意一個成員，均可以以匿名的方式代表整個群體對消息進行簽名，并且在有爭議時，群管理員可以確定簽名者的身份#65377;
一個好的群簽名方案應滿足以下安全性要求:
(1)正確性#65377;一個群成員使用簽名算法生成的簽名可以被驗證算法所接受#65377;
(2)防偽造性#65377;只有群成員才能產生有效的群簽名#65377;
(3)匿名性#65377;給定一個群簽名后，對除了唯一的群管理員之外的任何人來說，確定簽名人的身份在計算上是不可行的#65377;
(4)不可鏈接性#65377;在不打開簽名的情況下，確定兩個不同的簽名是否為同一個群成員在計算上是困難的#65377;
(5)防陷害攻擊#65377;包括群管理員在內的任何人均不能以其他群成員的名義產生合法的群簽名#65377;
(6)可跟蹤性#65377;群管理員在必要時可以打開一個簽名以確定出簽名人的身份，而且簽名人不能阻止一個合法簽名的打開#65377;
(7)抗聯合攻擊#65377;即使一些群成員串通在一起也不能產生一個合法的不能被跟蹤的群簽名#65377;
(8)可撤銷性#65377;群中任意一個群成員退出后，群管理員均可以安全地撤銷該成員，使之不能夠產生有效的群簽名，不會對群的安全性構成威脅#65377;
1997年，Camenisch和Stadler[2]提出了第一個效率相對較高且適用于大群體的群簽名方案(以下簡稱CS97方案)#65377;基于CS97方案[2]，Bresson和Stern[3]提出了第一個具有撤銷成員功能的群簽名方案#65377;但該方案要求簽名的長度線性依賴于被撤銷的成員個數，而且CS97群簽名方案后來被發現存在安全性問題，不能抵抗聯合攻擊#65377;
2000年，G.Ateniese等人[4]提出了一種安全高效的群簽名方案，即ACJT群簽名方案#65377;但是，ACJT群簽名方案沒有解決群成員的撤銷問題#65377;2001年，Song[5]基于ACJT群簽名[4]提出了兩個撤銷方案，除了實現撤銷功能外，方案還具有前向安全性，且簽名長度是定長的，但其驗證算法仍然線性依賴被撤銷的成員個數#65377;其后，Ateniese等人[6]提出了另外一個簽名長度獨立于被撤銷成員個數的撤銷方案;但其驗證算法也線性依賴被撤銷的成員個數，而且使用了雙重離散對數方法，增加了簽名和驗證的計算量#65377;Kim等人[7]提出了一種撤銷方案，但已經被證明存在安全性問題#65377;2002年，Camenisch和Lysyanskaya[8]給出了一個動態累加器#65377;該累加器允許動態加入和刪除數據，并利用該累加器實現了ACJT群簽名中的成員撤銷問題以及CL01[9]的匿名Credential系統中的成員撤銷問題#65377;改進后的驗證算法在計算量上僅需增加一個小于2的常數因子#65377;雖然改進后的方案有很多優點，但還存在以下不足:①每撤銷一個成員，剩余的群成員必須更新自己的證據，而這仍然是線性依賴于被撤銷的成員個數;②證明一個承諾值是在累加器中的計算量很大且復雜;③驗證者要定期查看群公鑰;④群管理員每次撤銷成員要經過很多次指數運算來更新群公鑰[10]#65377;
2005年，在ACJT群簽名方案[4]的基礎上， 陳澤文等人提出了ACJT群簽名方案中成員撤銷的實現方案[10]#65377;該方案是利用互素性來實現成員撤銷的#65377;其中群公鑰E等于被撤銷成員證書的素數之積#65377;這樣，E就會隨著撤銷成員的增加而無限增大#65377;在協議PK2中，證明PK1協議中的素數ei與E互素時，T7=(gE)bhw[11]的計算量就會隨著E的增大而增大#65377;
本文是基于ACJT群簽名方案提出的一個新的成員撤銷方案#65377;與以前的方案相比，該方案主要有以下優點:①新方案中，群公鑰E的大小只取決于群中成員證書中的素數之積，不會隨著撤銷成員的增加而無限增大，不會線性依賴于被撤銷成員的個數，相對穩定#65377;②驗證是否為群成員時，只需驗證成員證書中的素數ei是否為E的因子，只需要作一次模運算，計算量更少#65377;③增加或撤銷一個成員，群管理者只需作一次乘法或除法運算來更新群公鑰，運算簡單#65377;④簽名過程只是在ACJT群簽名方案的基礎上增加了三次指數運算，而陳澤文等人的成員撤銷方案每次簽名比ACJT群簽名方案要增加八次指數運算#65377;相對來說，本文的方案效率更高#65377;
1準備知識
設G=
下面是本文用到的一些重要術語:
(1)強RSA假設
存在一個概率算法T，使得對于所有的概率多項式算法A#65380;所有的多項式p(#8226;)和所有充分大的lg∶Pr[z=ue|(G，z):=T(1lg)，(u，e>1):=A(G，z)]<1/p(lg)#65377;
(2)DiffieHellman假設
不存在這樣的概率多項式時間算法#65377;該算法能以不可忽略的概率區分出分布D和R#65377;這里D=(g，gx，gy，gz)，x，y，z∈RZ#G，R=(g，gx，gy，gxy)，x，y∈RZ#G#65377;
(3)平方剩余群QR(n)
令n=pq為一個RSA體制的模數，p=2p′+1，q=2q′+1，且p#65380;p′#65380;q#65380;q′均為素數#65377;全體模n的平方剩余在模乘運算下構成群Z*n的一個循環子群，記為QR(n)#65377;已知QR(n)的階|QR(n)|=p′q′，通常認為在循環群QR(n)上，強RSA假設成立#65377;
2ACJT群簽名方案中的新成員撤銷方案
本方案是在ACJT群簽名方案的基礎上提出的成員撤銷方案，某些過程與ACJT群簽名方案相同#65377;但為了完整，與ACJT群簽名方案相同部分也一并列出#65377;設ε>1，k和lp為安全參數，定義兩個整數區間Λ=[2λ1-2λ2，2λ1+2λ2]，Γ=[2γ1-2γ2，2γ1+2γ2]#65377;這里，λ1>ε(λ2+k)+2，λ2>4lp，γ1>ε(γ2+k)+2，γ2>λ1+2#65377;
(1)初始化
GM隨機地秘密選擇lp比特的素數p′#65380;q′，使得p=2p′+1，q=2q′+1為素數，令n=pq#65377;
GM隨機選擇a，a0，g，h∈RQR(n)#65377;
GM隨機秘密選擇x∈Zp′q′，令y=gx mod n#65377;
GM隨機選擇U∈R{0，1}2lp，計算E=U，同時公布當前時間t#65377;
群公鑰為Y=(n，a，a0，y，g，h，E，t)#65377;
GM的私鑰為S=(p′，q′，x)#65377;
(2)成員加入
假定每個成員與管理員間的信道是安全的#65377;其加入過程如下:
①Pi產生一個秘密值i∈[0，2λ2]，一個隨機整數∈[0，n2]，計算，把C1=gih mod n發送給GM，并證明C1的正確性#65377;
②GM檢查C1∈QR(n)#65377;若是GM隨機選擇αi和βi∈[0，2λ2]，把(αi，βi)發送給Pi#65377;
③Pi計算xi=2λ1+(αii+βi mod 2λ2)，把C2=axi mod n發送給GM#65377;Pi向GM證明:
C2對a的離散對數在Λ內;
知道u#65380;v#65380;w使得u在[-2λ2，2λ2]內;u等于C2/a2λ1對于a的離散對數;Cαi1gβi=gu(g2λ2)vhw#65377;
④GM檢查C1∈QR(n)#65377;如果是且上述證明正確，則GM選擇一個素數ei∈Γ，計算Ai:=(C2a0)1/ei mod n，并發送給Pi成員證書[Ai，ei]#65377;
⑤Pi驗證axia0=Aeii(mod n)#65377;
⑥GM隨機選擇U′∈R{0，1}2lp，計算U=U′/U，更新公鑰E=E×ei×U，并同時更新時間t為當前時間#65377;
(3)簽名
首先查看群公鑰，找到最新群公鑰的更新時間t#65377;
產生一個隨機數w，z∈R{0，1}2lp，計算:
T1=Aiyw mod n，T2=gw mod n，
T3=geihw mod n，T4=zw，T5=wei，
T6=hz mod n
隨機選擇r1∈R±{0，1}ε(γ2+k)，r2∈R±{0，1}ε(λ2+k)，r3∈R±{0，1}ε(γ1+2lp+k+1)，r4∈R±{0，1}ε(2lp+k)，計算:
①d1=Tr11/(ar2yr3) mod n，
d2=T r12/gr3 mod n， d3=gr4 mod n，
d4=gr1hr4 mod n，d5=gr3 mod n，d6=Tr46mod n#65377;
②c=H(t‖g‖h‖y‖a0‖a‖T1‖T2‖T3‖T4‖T5‖T6‖d1‖d2‖d3‖d4‖d5‖d6‖m)#65377;
③s1=r1-c(ei-2γ1)，s2=r2-c(xi-2λ1)，s3=r3-ceiw，s4=r4-cw#65377;
輸出(t，c，s1，s2，s3，s4，T1，T2，T3，T4，T5，T6)#65377;
(4)驗證
首先查看群公鑰，找到最新的群公鑰的更新時間t和對應的群公鑰E#65377;如果簽名中的時間t和最新的群公鑰中的時間t不符，則拒絕簽名;否則進行如下計算:
c′=H(t‖g‖h‖y‖a0‖a‖T1‖T2‖T3‖T4‖T5‖T6‖
ac0T s1-c2γ11/(as2-c2λ1ys3) mod n‖T s1-c2γ12/gs3 mod n‖T c2gs4 mod n‖
T c3gs1-c2γ1hs4 mod n‖gs3+cT5 mod n‖T s46hcT4 mod n‖m)
當且僅當c′=c，T4E mod T5=0且
s1∈±{0，1}ε(γ2+k)+1s2∈±{0，1}ε(λ2+k)+1，s3∈±{0，1}ε(λ1+2lp+k+1)+1，s4∈±{0，1}ε(2lp+k)+1時接受簽名#65377;
(5)打開(與ACJT群簽名方案一樣)
①通過驗證算法驗證簽名的有效性#65377;
②通過自己的私鑰，管理員可以計算Ai=T1/T x2，恢復Ai#65377;
③證明loggy=logT2(T1/Ai mod n)#65377;
(6)撤銷
假設群中成員個數為m，e1，…，em為對應成員證書的素數#65377;當某一成員pi被撤銷時，GM隨機選擇U∈R{0，1}2lp，計算U=U′/U，更新群公鑰E=E×U/ei=e1…ei-1ei+1…em×U′，公布更新后的群公鑰E和更新時間t#65377;
這種方法能更有效地撤銷成員，群公鑰E的大小只取決于隨機數U與群中所有合法成員Pi的證書素數ei之積，相對穩定，不會隨著撤銷成員的增加而無限增大#65377;隨機數U是為了保證在加入成員時，E發生改變時，不泄漏新成員證書的素數ei#65377;驗證是否為群成員時，只需作一次模運算;驗證成員證書中的素數ei是否為E的因子，計算量更少，效率更高#65377;其中隨機數U，w，z∈R{0，1}2lp#65377;因為ei∈Γ，所以ei>U，ei>w，ei>z，ei不可能整除U#65380;w#65380;z，驗證T4E mod T5=0時，當且僅當E的因子有ei才能使驗證通過#65377;其中，隨機數U是為了保證新成員加入時，新成員的證書素數不被泄漏，隨機數w#65380;z是為了保證簽名的不可鏈接性#65377;
3安全性分析
定理1[5]假設發布的成員證書的個數K是多項式有界的，則在強RSA假定下，滿足的成員證書(Ai，ei，xi)僅能由GM生成#65377;其中xi∈Λ，ei∈Γ#65377;
定理2[5]在強RSA假設下，相應的交互式協議是關于(Ai，ei，xi)的統計零知識證明#65377;
(1)正確性#65377;可以通過驗證過程來獲得#65377;
(2)防偽造性#65377;若一個用戶既不是群成員，也不是一個撤銷群成員，那么從定理1可以知道，他不可能產生(Ai，ei，xi)，使得a0axi=Aeii;若他是一個撤銷成員，即他擁有(Ai，ei，xi)#65377;因為此時群公鑰E已經改變為e1…ei-1ei+1…em×U′，則從驗證過程可以看出，T4E mod T5≠0，所以簽名不可能被接受#65377;只有合法群成員才可以代表群體簽名#65377;
(3)可跟蹤性#65377;可以通過計算Ai=T1/Tx2來確定實際簽名者的身份#65377;
(4)防陷害攻擊#65377;群成員和群管理者均不能代表其他成員進行簽名#65377;①從定理1可以知道群成員不能代表其他群成員進行簽名，因為他無法偽造證書(Ai，ei，xi)，使得a0axi=Aeii#65377;②群管理者不能從axi得到一個群成員的密鑰xi，所以也無法進行偽造簽名#65377;
(5)不關聯性#65377;簽名過程沒有泄漏有關群成員的有用信息，(T1，T2，T3，T4，T5，T6)是與隨機數w#65380;z綁定在一起的，因而要決定不同的簽名來自同一個簽名者在計算上是困難的#65377;
(6)匿名性#65377;給定一個合法的簽名(t，c，s1，s2，s3，s4，T1，T2，T3，T4，T5，T6)，在離散對數假設下，可以知道從T1，T2，T3，T4，T5，T6，獲得(Ai，ei，xi)是困難的#65377;因此，對除了管理員之外的任何人來說，確定簽名人的身份在計算上是不可能的#65377;
(7)抗聯合攻擊性#65377;即使幾個人串通在一起，可以偽造出E的因子的某一素數i#65377;由定理1可知，無法偽造出合法成員證書(i，i，xi)，使得驗證時c′=c，T4 mod 2=0，T5 mod 2=1，T4E mod T5=0成立#65377;也就是說，即使幾個人串通也不能產生一個合法的不能被跟蹤的群簽名#65377;
(8)可撤銷性#65377;對一個擁有證書(Ai，ei，xi)的被撤銷的成員來說，他有兩種可能的方式來證明其是合法用戶:①選擇一個與ei不同卻是群公鑰E的因子的i來證明成員資格#65377;根據定理1，無法偽造出合法成員證書(i，i，xi)，使得驗證時c′=c，T4 mod 2=0，T5 mod 2=1，T4E mod T5=0成立，所以這是無法實現的#65377;②還用原來的ei證明成員資格#65377;因為這時的E=e1…ei-1ei+1…em×U′，ei已經不是E的因子，T4E mod T5≠0，驗證時簽名不被接受，所以這也是無法實現的#65377;由以上兩點可以看出，用本文的方案可以解決群成員的撤銷問題，是能夠在保證安全的基礎上撤銷成員的#65377;
4結束語
本文基于ACJT群簽名方案提出了一種新的成員撤銷方案#65377;其實現思想是:群管理員計算群內所有成員證書的素數與某一隨機數U的乘積，為群公鑰E#65377;合法用戶只需要作一次模運算來證明自己的ei是E的一個因子;增加一個成員時僅需一次乘法來更新E;刪除一個成員只需作一次除法來更新E#65377;與原始的不具有撤銷功能的ACJT群簽名方案相比，新的成員撤銷方案每次簽名只要增加三次指數運算，而且驗證算法不會隨著撤銷成員的增加而增大#65377;所以，該群成員撤銷方案的計算量更小，實現效率更高#65377;與陳澤文等人提出的成員撤銷方案[11]相同的是，對于本文的方案，簽名者在簽名前必須查看群公鑰和時間t的更新情況，驗證者也要定期查看群公鑰E和時間t的更新情況#65377;
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
