基于身份的門限多代理多簽名方案
2009-01-01 00:00:00楊長海唐西林
計算機應用研究 2009年2期
(1.華南理工大學理學院， 廣州 510640； 2.南昌陸軍學院科文教研室， 南昌 330103)
摘 要：
首次利用雙線性映射提出了一個基于身份的門限多代理多簽名方案。在該方案中，原始群和代理群的管理員通過分發共享秘密來控制群成員的行為，在群成員獲得共享秘密后，一定數量的原始簽名者合作可以進行授權，一定數量的代理簽名者合作可以產生簽名。經分析得知方案具有秘密性、不可偽造性和不可否認性等安全特點。
關鍵詞：數字簽名； 門限多代理多簽名； 基于身份； 雙線性映射
中圖分類號：TP309 文獻標志碼：A
文章編號：1001-3695(2009)02-0702-03
Identity-based threshold multi-proxy multi-signature scheme
YANG Chang-hai1，2， TANG Xi-lin1
(1. College of Science， South China University of Technology， Guangzhou 510640，China; 2. Dept.of Science Arts，Nanchang Military Academy， Nanchang 330103， China)
Abstract:This paper introduced an identity-based threshold multi-proxy multi-signature scheme using bilinear pairings for the first time. In this scheme， the administrators of the original group and proxy group could control the behavior of their members by distributing the shared secrets. After original signers and proxy signers obtained the shared secrets， some original signers could cooperatively delegate their signing capability to proxy signers， and some proxy signers could cooperatively generate threshold multi-proxy multi-signature. By analyzing the scheme， conclude that the scheme has many security properties， such as secrecy， unforgeability， nonrepudiation etc.
Key words：digital signature; threshold multi-proxy multi-signature; identity-based; bilinear pairing
1996年，Mambo等人[1]首次提出了代理簽名的概念。在代理簽名方案中，經過原始簽名者的授權，代理簽名者可以代表原始簽名者生成有效的簽名。代理簽名在實際應用中起著重要作用，所以一提出便受到國內外學者的廣泛關注。隨著代理簽名體制的發展，多重代理簽名[2]、代理多重簽名[3]、多重代理多重簽名[4]和混合代理多重簽名[5]等概念相繼提出，并與其他的簽名概念相結合，產生了許多具有不同功能的代理簽名方案。
1997年，Zhang[6]將代理簽名與門限簽名結合起來首次提出了門限代理簽名的概念。在(t，n)門限代理簽名中，只有n個代理簽名者中的任意t個或多于t個一起合作才能代表原始簽名者進行簽名。與普通的代理簽名相比，門限代理簽名具有安全性更高、分散管理權限等良好性質。
然而，門限代理簽名僅僅考慮了代理簽名者是由群組成的情況，在現實的生活中，經常會遇到需要多個原始簽名者合作才能授權給代理簽名者的情況，甚至還會出現需要指定的多個驗證者合作才能完成驗證簽名的情況。為了滿足這些實際需要，許多門限多代理多簽名方案相繼提出[7~14]。2003年，Li等人[7]將(t，n)門限代理簽名概念進行了推廣，提出了一個一般的門限代理簽名方案，稱其為(t1，n1;t2，n2)門限多代理多簽名方案。在該方案中，只有n1個原始簽名者中的任意t1或多于t1個合作才能授權給代理簽名者；同時，只有n2個代理簽名者中的任意t2或多于t2個合作才能產生有效的代理簽名。2004年，Tzeng等人[8]進一步考慮了驗證者也是由群組成的情形，提出了具有共享驗證性質的門限多代理多簽名方案。但是Li和Tzeng方案均存在一些缺陷[9~12]。此后，門限多代理多簽名體制得到進一步發展。2005年，Hwang等人[13]提出了一個門限代理門限簽名方案。該方案的優點是需要原始簽名者和代理簽名者一起合作才能產生代理證書，從而使得原始簽名者和代理簽名者的利益受到公平的保護。2007年，祁傳達等人[14]利用仿射空間的RSA秘密共享技術提出了一種新的基于RSA的門限多代理多簽名方案，該方案具有非交互和無須第三方參與的優點。
上述門限多代理多簽名方案的一個共同點就是，它們都是基于公鑰證書的數字簽名方案。由于基于身份的密碼體制是密碼學的一個主要發展方向，將其運用到門限多代理多簽名中研究基于身份的門限多代理多簽名方案是非常有意義的。在本文中，筆者首次利用雙線性映射提出了一個基于身份的門限多代理多簽名方案。
1 準備知識
1. 1 雙線性映射
假設G1是一個生成元為P的循環加法群，它的階為素數q，G2是一個階為q的循環乘法群。稱映射e為雙線性映射，若映射e:G1×G1→G２滿足下列性質：
a)雙線性。e(aP，bQ)=e(P，Q)ab，P，Q∈G1， a，b∈Z*q。
b)非退化性。存在一個P∈G1，使得e(P，P)≠1。
c)可計算性。對P，Q∈G1，存在一個有效的算法能夠計算e(P，Q)。
1. 2 相關的數學難題
a)離散對數難題(DLP)。設P，Q∈G1，要找到一個正整數n∈z*q，使得滿足Q=nP是困難的。
b)判定Diffie-Hellman難題(DDHP)。對于任意給定的P，aP，bP，cP∈G1，其中a，b，c∈z*q，要判定c≡ab mod q是否成立是困難的。
c)計算Diffie-Hellman難題(CDHP)。對于任意給定的P，aP，bP，cP∈G1，其中a，b，c∈z*q，計算abP是困難的。
d)間隙Diffie-Hellman難題(GDHP)。它是指這樣一類問題，對于任意給定的P，aP，bP，cP∈G1，容易判定c≡ab mod q是成立的，但是計算abP是困難的。
e)雙線性Diffie-Hellman難題(BDHP)。對于任意給定的P，aP，bP，cP∈G1，其中a，b，c∈z*q，計算e(P，P)abc是困難的。
2 基于身份的門限多代理多簽名方案
設OS={O1，O2，…，On1}是由n1個原始簽名者組成的原始組， Go是可信的組管理員，Ioi和Io分別表示組成員及管理員的惟一身份標志符；PS={P1，P2，…，Pn2}是由n2個代理簽名者組成的代理組，GP是可信的組管理員，IPi和IP分別表示組成員及管理員的惟一身份標志符。密鑰生成中心PKG負責系統的初始化。方案組成過程如下。
2. 1 系統初始化過程
a)PKG生成兩個階為素數q的群(G1，+)和(G2，#8226;)，選擇G1的任意一個生成元P，e:G1×G1→G2是一個雙線性映射，H0:{0，1}*→G1，H1:{0，1}*×G2→Z*q為安全hash函數。
b)PKG選擇一個s∈RZ*q，并計算Ppub=sP，將s作為主密鑰保存起來，公開系統參數(G1，G2，e，q，P，Ppub， H0，H1)。
c)每個參與用戶發布其身份信息，PKG發布用戶的公鑰Qoi=H0(Ioi)， QPi=H0(IPi)， Qo=H0(Io)和Qp=H0(Ip)；將Soi=sHo(Ioi)， SPi=sH0(IPi)， So=sH0(Io)和Sp=sH0(IP)作為用戶私鑰通過安全信道發送給用戶。
2. 2 原始簽名者秘密共享過程
假設mω為OS授予PS簽名權的授權證書，它描述了原始組成員及管理員的身份、代理組成員及管理員的身份、原始組及代理組的門限值t1和t2、證書的有效時間、代理的權限和范圍等。
a)管理員Go選擇d0∈RZ*q，計算并公布D0=e(P，P)d0。
b)管理員Go選擇一個t1-1次多項式函數：
F(x)=W+∑t1-1i=1aixi。其中：W=SoH1(mω，D0)+d0P， ai∈G1，然后計算F(Ioi)，并通過安全信道發送給相應原始簽名者，廣播ai=e(ai，P)(i=1，2，…，t1-1)。
c) 每個原始簽名者Oi收到F(Ioi)后，首先計算α0=e(Qo，Ppub)H1(mω，D0)×D0，然后驗證e(F(Ioi)，P)=∏t1-1k=0αIokik是否成立。若等式不成立則要求重發；否則將F(Ioi)作為Oi從管理員Go處獲得的秘密份額。
2. 3 代理授權過程
不失一般性，設{O1，O2，…，Ot1}為實際參與授權的原始簽名者。要完成OS對PS的授權，可通過如下過程產生：
a)Oi(i=1，2，…，t1)選擇di∈RZ*q，計算Di=e(P，P)di，將Di發送給其他原始簽名者Oj(j=1，2，…，t1，j≠i)和管理員Go。
b)Qi(i=1，2，…，t1)和Go收到Di后，計算D=∏t1i=1Di。
c)Oi(i=1，2，…，t1)計算Si=(ηiF(Ioi)+Soi)H1(mω，D)+diP。其中ηi=∏t1j=1，j≠i(-Ioj)(Ioi-Ioj)-1，將Si作為部分代理授權密鑰通過安全信道發送給管理員Go。
d)Go收到Si后，計算ηi=∏t1j=1，j≠i(-Ioj)(Ioi-Ioj)-1，驗證e(Si，P)=e(F(Ioi)，P)ηiH1(mω，D)e(Qoi，Ppub)H1(mω，D)Di是否成立。若不成立則要求重發；若成立，則計算S=∑t1i=1Si，將S作為代理授權密鑰秘密發送給每個代理簽名者和代理群管理員，公布(mω，D)。
2. 4 代理私鑰產生過程
代理簽名者Pi(i=1，2，…，n2)收到S后，驗證
e(S，P)=[e(QoH1(mω，D0)，Ppub)×D0×
e(∑t1i=1Qoi，Ppub)]H1(mω，D)×D
(1)
是否成立。若不成立，則拒絕代理；否則接受原始簽名者的授權，并計算代理私鑰σi=t2-1S+Spi。
2. 5 代理簽名者秘密共享過程
a)管理員GP選擇r0∈RZ*q，計算并公布R0=e(P，P)r0。
b)管理員GP選擇一個t2-1次多項式函數
f(x)=V+∑t2-1i=1bixi，其中V=SpH1(mω，R0)+r0P，bi∈G1；然后計算f(IPi)，并通過安全信道發送給相應代理簽名者，廣播βi=e(bi，P)(i=1，2，…，t2-1)。
c) 每個代理簽名者Pi收到f(IPi)后，首先計算β0=e(QP，Ppub)H1(mω，R0)×R0，然后驗證e(f(IPi)，P)=∏t2-1k=0βIPikk是否成立。若等式不成立則要求重發；否則將f(IPi)作為Pi從管理員GP處獲得的秘密份額。
2. 6 代理簽名產生過程
不妨設{P1，P2，…，Pt2}為實際參與簽名的代理簽名者。為了完成對消息m的簽名，可以通過如下過程產生：
a)Pi(i=1，2，…，t2)選擇ri∈RZ*q，計算Ri=e(P，P)ri，并將其發送給管理員GP。
b)Gp收到Ri后計算R=∏t2i=1Ri。再令v=H1(m，R)，將v發送給Pi(i=1，2，…，t2)。
c)Pi(i=1，2，…，t2)計算Ui=(λi f(IPi)+σi)v+riP，其中λi=∏t2j=1，j≠i(-IPj)(Ipi-IPj)-1，將(Ui， IPi)作為消息m的部分簽名，通過安全信道發送給GP。
d)GP接收到（Ui，IRi）后，計算λi=∏t2j=1，j≠i(-IPj)(IPi-IPj)-1，驗證：
e(Ui，P)=[e(f(IPi)，P)λie(S，P)t-12e(QPi，Ppub)]v×Ri
(2)
對i=1，2，…，t2是否均成立。若不成立則要求重發；否則，計算U=∑t2i=1Ui，將(m，mω，U，v，D，D0，R0)作為最終的(t1，n1;t2，n2)門限多代理多簽名。
2. 7 簽名驗證過程
為了驗證(m，mω，V，v，D，D0，R0)的有效性，驗證者計算
e(S，P)=[e(QoH1(mω，D0)，Ppub)×D0×
e(∑t1i=1Qoi，Ppub)]H1(mω，D)×D
(3)
R=e(U，P)[e(QPH1(mω，R0)，Ppub)×R0×
e(S，P)e(∑t2i=1QPi，Ppub)]-v
(4)
若v=H1(m，R)成立，則接受簽名；否則拒絕。
3 方案的分析
3. 1 正確性分析
a)代理簽名者可通過式(1)來驗證代理授權的有效性。
證明 e(S，P)=e(∑t1i=1Si，P)=
e(∑t1i=1ηiF(Ioi）+∑t1i=1Soi，P)H1(mω，D)e(∑t1i=1diP，P)=
[e(W，P)e(∑t1i=1Qoi，Ppub)]H1(mω，D)×D=
[e(QoH1(mω，D0)，Ppub)×D0×e(∑t1i=1Qoi，Ppub)]H1(mω，D)×D
b)管理員Gp可通過式(2)來驗證部分簽名的有效性。
證明 e(Ui，P)=e((λif(IPi)+σi)v+riP，P)=
[e(f(IPi)，P)λie(t2-1S，P)e(SPi，P)]v×e(riP，P)=
[e(f(IPi)，P)λie(S，P)t-12e(QPi，Ppub)]v×Ri
c)驗證者可通過驗證v=H1(m，R)(其中R由式(3)和(4)給出)是否成立來驗證門限多代理多簽名(m，mω，U，v，D，D0，R0)的有效性。
證明 因為
e(S，P)=[e(QoH1(mω，D0)，Ppub)×D0×e(∑t1i=1Qoi，Ppub)]H1(mω，D)×D
且e(U，P)=e(∑t2i=1Ui，P)=e(∑t2i=1λif(IPi)+
∑t2i=1σi，P)ve(∑t2i=1riP，P)=
[e(V，P)e(S，P)e(∑t2i=1Spi， P)]v×R=
[e(QpH1(mω，R0)，Ppub)×R0×e(S，P)e(∑t2i=1QPi，Ppub)]v×R
所以R=e(U，R)[e(QpH1(mω，R0)，Ppub)×R0×e(S，P)×e(∑t2i=1Q，Ppub)]-v，即有v=H1(m，R)成立。
3. 2 安全性分析
該方案的安全性是基于Hess提出的可證明安全的簽名方案[15]的安全性。
a)該方案具有秘密性，即原始組管理員Go、代理組管理員GP、原始簽名者和代理簽名者的私鑰均不會泄露。在原始簽名者秘密共享過程，任意t1個原始簽名者合作可恢復出W=∑t1i=1ηiF(Ioi)，但是不能由W=SoH1(mω，D0)+d0P進一步獲得Go私鑰So的任何信息，從而保證了Go的私鑰不會泄露；同理，Gp的私鑰在代理簽名者秘密共享過程也不會泄露。由于原始簽名者采用了Hess的簽名方案產生部分代理授權密鑰Si，即Si=(ηiF(Ioi)+Soi)H1(mω，D)+diP，攻擊者要想從Si獲得原始簽名者的私鑰Soi是不可能的；同理，攻擊者要想從部分代理簽名Ui中獲得代理簽名者的私鑰SPi也是不可能的。
b)該方案能抵抗合謀攻擊，即只要攻擊者的個數小于門限值，即使是內部成員進行攻擊也不可能成功。由于在原始簽名者秘密共享過程和代理簽名者秘密共享過程，采用的都是可驗證秘密共享方案(VSS)，即使有t1-1個原始簽名者合謀也不可能由部分代理授權密鑰Si計算出代理授權密鑰S，使其能通過有效性驗證，從而產生合法授權；同理，少于t2個代理簽名者合謀也不可能產生有效的簽名。
c)該方案具有不可偽造性。在簽名過程中，代理簽名者的部分代理簽名采用了Hess的簽名方案，由于該方案是可證明安全的，攻擊者要想通過攻破方案本身來偽造一個簽名使其通過驗證是不可能的。
d)該方案具有不可否認性。一方面，由于簽名驗證方程中包含了原始組管理員Go和代理組管理員Gp的公鑰，Go不能否認簽名是由原始組委托給代理組進行簽署的，Gp也不能否認自己管理的代理組簽署了這個簽名；另一方面，由于簽名驗證方程中包含了實際參與授權的原始簽名者和實際參與簽名的代理簽名者的公鑰，實際參與的原始簽名者不能否認自己參與了授權，實際參與的代理簽名者也不能否認自己參與了簽名。
4 結束語
門限多代理多簽名是門限簽名與多重代理多重簽名的有機結合，與普通的多重代理多重簽名相比具有更強的實用性。本文首先提出了一個基于身份的門限多代理多簽名方案，然后對該方案的正確性和安全性進行了分析。分析表明，該方案不僅具有代理簽名所要求的秘密性、不可偽造性和不可否認性等安全特點，同時還具有門限簽名所具有的特性。因此該方案是安全和實用的。
參考文獻：
[1]MAMBOM， USUDAK， OKAMOTOE. Proxy signatures:delegation of the power to sign messages[J]. IEICE Trans on Fundamentals， 1996 ， E79-A(9):1338-1354.
[2]HWANGS J， SHIC H. A simple multi-proxy signature scheme[C]// Proc of the 10th National Conference on Information Security. Hualien: [s.n.]，2000: 134-138.
[3]YILi-jiang， BAIGuo-qiang， XIAOGuo-zhen. Proxy multi-signature scheme:anew type of proxy signature scheme[J]. Electronics Letters， 2000，36(6): 527- 528.
[4]HWANG S J， CHEN C C. A new multi-proxy-multi-signature scheme[J]. Applied Mathematics and Computation， 2004，147(1):57-67.
[5]WANG Ze-cheng， QIAN hai-feng， LI Zhi-bin. Hybrid proxy multi- signature: a new type multi-party signature[J]. Information Sciences， 2007，177(24): 5638- 5650.
[6]ZHANGKan. Threshold proxy signature schemes[C]//Proc of the 1st International Workshop on Information Security. London: Springer-verlag， 1997:191-197.
[7]LIL H， TZENGS F， HWANGM S. Generalization of proxy signature based on discrete logarithms[J]. Computers Security， 2003，22(3): 245-255.
[8]TZENGS F， YANGC Y， HWANGM S. A nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Future Generation Computer Systems， 2004，20(5):887-893.
[9]HWANG S J， CHAN C C. Improvement on Li， et al.’s generalization of proxy signatureschemes[J]. Computers Security， 2004，23(7):615-619.
[10]BAOHai-yong， CAOZhen-fu， WANGSheng-bao. Improvement on Tzeng et al. ’s nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Applied Mathematics and Computation， 2005，169(2):1419-1430.
[11]HSUC L， TSAIK Y， TSAIP L. Cryptanalysis and improvement of nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J].Information Sciences， 2007，177(2): 543-549.
[12]KANGBao-yuan， HANJing-guang， WANGQin-ju.A new threshold multi- proxy multi-signature scheme[J]. Journal of Electronics 2006，23(4):560- 563.
[13]HWANG S J， CHEN C C. New threshold-proxy threshold-signature schemes[J].Computers and Electrical Engineering， 2005，31(1):69-80.
[14]祁傳達，李溪，金晨輝.基于RSA的門限多重代理多重簽名方案[J].計算機工程與設計，2007，28(21):5105-5107.
[15]HESSF. Efficient identity based signature schemes based on pairings[C]// Proc of SAC 2002，LNCS 2595. Berlin: Springer-Verlag， 2002: 310-324.
