基于身份的強(qiáng)指定驗(yàn)證人簽名方案

摘 要:在有些情況下， 需要將驗(yàn)證者限定為某一個(gè)人。 利用基于身份的密碼體制， 提出了一種強(qiáng)指定驗(yàn)證人簽名和一種強(qiáng)指定驗(yàn)證人多重代理簽名， 并對其安全性進(jìn)行了分析。 在簽名代價(jià)和驗(yàn)證代價(jià)上， 提出的強(qiáng)指定驗(yàn)證人簽名比Kang等人的方案要低。提出的強(qiáng)指定驗(yàn)證人多重代理簽名可以同時(shí)授權(quán)給n個(gè)代理人， 可以有效防止代理簽名人對簽名權(quán)的濫用。

關(guān)鍵詞:基于身份的簽名; 指定驗(yàn)證人簽名; 代理簽名; 雙線性對

中圖分類號:TP309

文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)02-0689-03

doi:10.3969/j.issn.1001-3695.2010.02.079

Identity-based strong designated verifier signature schemes

MAO Wei-xia， LI Zhi-hui， XUE Ting

(College of Mathematics Information Science ， Shaanxi Normal University， Xi’an 710062， China)

Abstract:We should specify a verifier in some circumstances. Using identity-based cryptography， this paper proposed a strong designated verifier signature and a strong designated verifier multi-proxy signature. It also analyzed the proposed schemes. The proposed strong designated verifier signature scheme was lower than Kang et al.’s scheme in the signing cost and verifying cost. The proposed strong designated verifier multi-proxy signature scheme could delegate n proxy signers. Thus it could prevent proxy signers abusing signing authority.

Key words:identity-based signature;designated verifier signature;proxy signature;bilinear pairings

0 引言

在基于身份的密碼體制中， 用戶的公鑰可以是任意的字符串(如姓名、電子郵件地址、IP地址等)， 而私鑰由私鑰生成中心(private key generator， PKG)生成。這種思想最早是由Shamir在文獻(xiàn)[1]中提出的。基于身份的密碼體制無須公鑰證書的管理與鑒別， 在實(shí)際應(yīng)用中帶來很大的便利。

Jakobsson等人在文獻(xiàn)[2]中首先提出了指定驗(yàn)證人簽名的概念。指定驗(yàn)證人簽名將驗(yàn)證者限定為某一個(gè)人， 在許多領(lǐng)域(如電子現(xiàn)金、電子選舉)中有著重要的作用。在這種簽名方案中， Alice指定一個(gè)驗(yàn)證人 Bob。Alice可以使Bob相信他的簽名是正確的， 并且Bob不能向第三方證明該簽名是由Alice所簽， 原因是Bob可以模擬出與簽名者Alice不可區(qū)分的簽名。

Saeednia等人[3]將指定驗(yàn)證人的私鑰應(yīng)用到驗(yàn)證等式中， 提出了強(qiáng)指定驗(yàn)證人簽名。強(qiáng)指定驗(yàn)證人簽名是指只有指定的驗(yàn)證人才能檢驗(yàn)簽名的合法性， 并且第三方不能確定該簽名到底是誰所簽。在2004年， Susilo等人[4]提出了基于身份的強(qiáng)指定驗(yàn)證人簽名方案。后來， Kumar等人在文獻(xiàn)[5]中提出了新的基于身份的強(qiáng)指定驗(yàn)證人簽名方案， 但沒有證明安全性。與文獻(xiàn)[4，5]的方案相比， Kang等人[6]提出的方案簽名長度較短， 簽名代價(jià)和驗(yàn)證代價(jià)較低。

Mambo等人[7]提出了代理簽名的概念。代理簽名解決了數(shù)字簽名權(quán)力委托的問題， 即原始簽名人將簽名權(quán)委托給代理簽名人， 同時(shí)又不暴露自己的私鑰。多重代理簽名是原始簽名人將簽名權(quán)分散給多個(gè)代理簽名人， 這樣可以有效防止代理簽名人對簽名權(quán)的濫用。強(qiáng)指定驗(yàn)證人多重代理簽名是指定驗(yàn)證人簽名的延伸。

1 相關(guān)知識

1.1 雙線性對

令G1和G2分別是階為大素?cái)?shù)q的加群和乘群，P為G1的生成元。e:G1×G1→G2是一個(gè)映射，若e滿足下列三條性質(zhì):

a)雙線性性。e(aP，bQ)=e(P，Q)ab，對所有的P，Q∈G1和a，b∈Z。

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

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

稱e為一個(gè)雙線性對。由雙線性對的性質(zhì)b)知，若P為G1的生成元，則e(P，P)為G2的生成元。

1.2 與雙線性對有關(guān)的數(shù)學(xué)問題

1)離散對數(shù)問題(DLP) 給定P，Q∈G1，找出整數(shù)a， 使得Q=aP， 如果這樣的整數(shù)a存在。

2)計(jì)算Diffie-Hellman問題(CDHP) 給定P，aP，bP∈G1，對于所有的a，b∈Zq， 計(jì)算abP。

3)判定Diffie-Hellman問題(DDHP) 給定P，aP，bP，cP∈G1，對于所有a，b，c∈Zq，判定c=ab mod q是否成立。

4)雙線性Diffie-Hellman問題(BDHP) 給定P，aP，bP，cP∈G1，對于所有a，b，c∈Zq，計(jì)算e(P，P)abc。

假設(shè)群上的DLP、CDHP和BDHP都是難解問題。當(dāng)群上的DDHP容易而CDHP難解時(shí)， 這樣的群叫GDH(gap Diffie-Hellman)群。這樣的群可以在超橢圓曲線中找到， 并且可以利用超橢圓曲線上的Weil對或經(jīng)改造的Tate對來構(gòu)造雙線性對。具體細(xì)節(jié)可參考文獻(xiàn)[8]。

2 基于身份的強(qiáng)指定驗(yàn)證人簽名

2.1 系統(tǒng)初始化

(1)私鑰生成中心PKG選取階都為素?cái)?shù)q的GDH群G1和乘法群G2， 雙線性映射e:G1×G1→G2，P為G1的生成元。任取s∈Zq為主密鑰，公鑰為Ppub=sP。H1:{0，1}→G1和H2:{0，1}×G2→G1為兩個(gè)安全的哈希函數(shù)。系統(tǒng)參數(shù)為(G1，G2，q，e，P，Ppub，H1，H2)。參與者為簽名者A和指定驗(yàn)證人C。

(2)私鑰生成中心PKG利用身份ID計(jì)算SID=sH1(ID)，并發(fā)送給其身份為ID的用戶，QID=H1(ID)為其公鑰。

2.2 簽名階段

簽名者A對消息m進(jìn)行簽名。簽名者A任意選取r∈Zq，計(jì)算R=rQIDA，σ=H2(m，e(Ppub+rSIDA，QIDC))，把(R，σ)發(fā)送給指定驗(yàn)證人C。

2.3 驗(yàn)證階段

指定驗(yàn)證人C收到(R，σ)后， 驗(yàn)證下式是否成立。若成立，則(R，σ)就是關(guān)于消息m的簽名。

σ=H2(m，e(P+R，SIDC))

2.4 簽名模擬階段

指定驗(yàn)證人C任取r′∈Zq，計(jì)算R′=r′QIDA，σ′=H2(m，e(P+R′，SIDC))。

2.5 方案分析

1)正確性

e(Ppub+rSIDA，QIDC)=e(P+rQIDA，SIDC)=e(P+R，SIDC)

故

σ=H2(m，e(Ppub+rSIDA，QIDC))=H2(m，e(P+R，SIDC))

并且指定驗(yàn)證人C的私鑰SIDC出現(xiàn)在驗(yàn)證等式中， 因此只有指定驗(yàn)證人C才能檢驗(yàn)簽名的合法性。

2)不可偽造性

由于

σ=H2(m，e(Ppub+rSIDA，QIDC))=H2(m，e(P+R，SIDC))

攻擊者不知道SIDA和SIDC就無法偽造σ， 從而也就無法偽造簽名。 求SIDA和SIDC必須知道s， 而求s將會(huì)面臨離散對數(shù)問題(DLP)。

3)簽名源的隱匿性

只有指定驗(yàn)證人C才能驗(yàn)證和模擬簽名， 并且指定驗(yàn)證人C不能向第三方證明該簽名是由A所簽， 即簽名是由簽名者A或指定驗(yàn)證人C兩者之一產(chǎn)生。因此， 對于消息m和關(guān)于消息m的簽名(R，σ)， 攻擊者不可能確定該簽名到底是誰所簽。

4)簽名者身份的匿名性

在簽名階段， 攻擊者知道r∈Zq和SIDA才能對消息進(jìn)行簽名。在驗(yàn)證階段， 攻擊者知道SIDC才能對簽名進(jìn)行驗(yàn)證。攻擊者不知道r，SIDA，SIDC就無法求出σ。因此， 攻擊者不可能確定簽名到底是誰所簽， 從而也就無法知道簽名者的身份。

5)效率分析

Cp為雙線性對運(yùn)算，C為G1上的乘法，Ce為G2上的指數(shù)運(yùn)算，Ch為哈希函數(shù)運(yùn)算，Ci為求逆運(yùn)算，省略G1上的加法。假設(shè)G1的元素的比特長度為|G1|(|G1|=|G2|)。分別用[4]、[5]、[6]表示文獻(xiàn)[4， 5， 6] ， 用[0]表示本文所提方案。從表1可以看出， 所提出的方案明顯優(yōu)于文獻(xiàn)[4， 5， 6]。

表1 不同方案的比較

方案長度簽名代價(jià)驗(yàn)證代價(jià)

[5]4|G1|1Cp+5C+1Ch+1Ci4Cp+1Ch

[4] 2|G1|+|H|1Cp+2C+1Ce+1Ch+1Ci2Cp+1C+2Ce+1Ch

[6]2|G1|2Cp+2C+1Ce+1Ch1Cp+1C+1Ce+1Ch

[0]2|G1|1Cp+2C+1Ch1Cp+1Ch

3 基于身份的強(qiáng)指定驗(yàn)證人多重代理簽名

3.1 系統(tǒng)初始化

1)(G1，G2，q，e，P，Ppub，H1，H2)與2.1節(jié)中的參數(shù)相同。選取H3:{0，1}→Zq為另一個(gè)安全的哈希函數(shù)，公布H3。消息m∈{0，1}，‖表示比特串并聯(lián)。參與者分別為原始簽名人A、代理簽名組{P1，P2，…，Pn}和指定驗(yàn)證人C。

2)私鑰生成中心PKG利用身份ID計(jì)算SID=sH1(ID)，把SID發(fā)送給其身份為ID的用戶，QID=H1(ID)為其公鑰。

3.2 代理密鑰生成階段

1)原始簽名人A制定代理授權(quán)書mw(其中包括原始簽名人A和代理簽名人Pi(1≤i≤n)的身份、代理簽名文件的范圍、代理終止時(shí)間等信息)。原始簽名人A任取ri∈Zq，計(jì)算Ri=riH3(mw‖QIDPi)，Ti=RiSIDA，把(mW，Ri，Ti)發(fā)送給代理簽名人Pi。

2)代理簽名人Pi收到(mw，Ri，Ti)后，檢驗(yàn)e(Ti，P)=e(RiQIDA，Ppub)是否成立。若成立，計(jì)算代理簽名密鑰SPi=Ti-SIDPi， 代理簽名公鑰為QPi=RiQIDA-QIDPi。

3.3 代理簽名階段

代理簽名人Pi對消息m進(jìn)行簽名。代理簽名人Pi任意選取ui，vi∈Zq，計(jì)算

Ui=uiSPi

Vi=H2(mw，e(uiQIDC，viSPi))

hi=H3(m‖Ui‖Vi)

σi=uiQPi+hiP

然后把(mw，m，Ui，Vi，hi，Qi)發(fā)送給指定驗(yàn)證人C。

3.4 代理簽名驗(yàn)證階段

1)指定驗(yàn)證人C收到(mw，m，Ui，Vi，hi，σi)后， 首先檢查一下消息m是否包含在代理授權(quán)書mw中，A和Pi是否是真正的原始簽名人和代理簽名人。

2)因?yàn)橛衝個(gè)代理簽名人， 就有n個(gè)簽名。指定驗(yàn)證人C計(jì)算σ=∑ni=1σi， 并驗(yàn)證下式是否成立。若成立，則σ就是關(guān)于消息m的簽名。

e(σ，SIDC)=Πni=1e(Ui+hiPpub，QIDC)

3.5 代理簽名模擬階段

指定驗(yàn)證人C任取u′i，v′i∈Zq，計(jì)算

U′i=u′iSIDC

V′i=H2(mw，e(v′iSIDC，u′iQPi))

h′i=H3(m‖U′i‖V′i)

σ′i=u′iQIDC+h′iP

然后計(jì)算σ′=∑ni=1σ′i，此時(shí)(U′i，h′i，σ′)能通過下面等式的驗(yàn)證。

e(σ′，SIDC)=Πni=1e(U′i+h′iPpub，QIDC)

3.6 方案分析

1)正確性

e(σ，SIDC)=e∑ni=1σi，SIDC=Πni=1e(σi，SIDC)=

Πni=1e(uiQPi+hiP，SIDC)=

Πni=1e(uiSPi+hiPpub，QIDC)=

Πni=1e(Ui+hiPpub，QIDC)

2)不可偽造性

攻擊者想偽造關(guān)于消息m的簽名σ，需知代理簽名密鑰SPi或者指定驗(yàn)證人C的私鑰SIDC。而SPi=Ti-SIDPi=RiSIDA-SIDPi。其中Ri=riH3(mw‖QIDPi)具有隨機(jī)性，SIDA和SIDPi分別為原始簽名人A和代理簽名人Pi的私鑰。求解SIDA、SIDPi和SIDC將會(huì)面臨離散對數(shù)問題(DLP)或計(jì)算Diffie-Hellman問題(CDHP)。

此外， 攻擊者已經(jīng)知道某個(gè)代理簽名人Pi的簽名(Ui，Vi，hi，σi)， 想從驗(yàn)證等式e(σ，SIDC)=Πni=1e(Ui+hiPpub，QIDC)中求出SIDC也是不可能的。

e(σ，SIDC)=Πni=1e(Ui+hiPpub，QIDC)

e(σi，SIDC)=e(Ui+hiPpub，QIDC)

由于σ1，SIDC，Ui，QIDC∈G1，設(shè)σi=aP，SIDC=xP，Ui=bP，QIDC=cP。

e(σi，SIDC)=e(Ui+hiPpub，QIDC)

e(aP，xP)=e(bP+shiP，cP)

e(P，P)ax=e(P，P)c(b+shi)

但求解e(P，P)ax與e(P，P)c(b+shi)將會(huì)面臨雙線性Diffie-Hellman問題(BDHP)， 并且確定a、b、c、s將會(huì)面臨離散對數(shù)問題(DLP)。因此，攻擊者不可能從等式e(P，P)ax=e(P，P)c(b+shi)中求出x，也就求不出SIDC。

3)簽名源的隱匿性

代理簽名人Pi的簽名為(Ui，Vi，hi，σi)，簽名中不包括代理簽名人Pi的任何信息。在驗(yàn)證等式e(σ，SIDC)=Πni=1e(Ui+hiPpub，QIDC)中，出現(xiàn)了指定驗(yàn)證人C的私鑰SIDC而沒有代理簽名人Pi的公鑰QIDpi，即代理簽名人Pi的簽名對于外界而言具有不確定性。因此， 其他人僅根據(jù)消息m和簽名σ， 無法確定該簽名到底是誰所簽。

4)簽名者身份的匿名性

由于有n個(gè)代理簽名人，就有n個(gè)簽名(Ui，Vi，hi，σi)(1≤i≤n)。攻擊者想確定消息m∈{0，1}是誰所簽， 需知簽消息m的每個(gè)代理簽名人Pi的身份。由3)可知， 攻擊者無法確定消息m到底是誰所簽， 從而也就不能確定代理簽名人Pi的身份。

另外， 簽名過程中使用了代理授權(quán)書mw， 并且指定驗(yàn)證人C的私鑰SIDC出現(xiàn)在驗(yàn)證等式e(σ，SIDC)=Πni=1e(Ui+hiPpub，QIDC)中， 故強(qiáng)指定驗(yàn)證人多重代理簽名與一般的簽名是可以區(qū)分的。代理授權(quán)書mw中已明確規(guī)定了代理簽名人所簽消息的具體內(nèi)容、代理終止時(shí)間等信息， 故代理簽名人Pi不能濫用自己的權(quán)利任意地對消息進(jìn)行簽名。從以上分析可以看出， 代理簽名的可驗(yàn)證性、不可偽造性、可區(qū)分性、防止濫用性也是滿足的。

5)效率分析

Cp、C 、Ch與2.5節(jié)的參數(shù)相同，省略G1上的加法和G2上的乘法。假設(shè)G1的元素的比特長度為|G1|(|G1|=|G2|)。單重代理簽名的驗(yàn)證等式為e(σi，SIDC)=e(Ui+hiPpub，QIDC)。從表2可以看出， 簽名長度無變化， 簽名代價(jià)和驗(yàn)證代價(jià)也沒有明顯增加。

表2 單重代理與多重代理的比較

方案長度簽名代價(jià)驗(yàn)證代價(jià)

單重|G1|1Cp+5C+2Ch2Cp+1C

多重|G1|nCp+5nC+2nCh(n+1)Cp+nC

4 結(jié)束語

指定驗(yàn)證人簽名在電子現(xiàn)金、電子選舉中有著重要的應(yīng)用。目前所提出的指定驗(yàn)證人簽名方案要么簽名長度較長， 要么簽名代價(jià)和驗(yàn)證代價(jià)較高。利用基于身份的密碼體制， 提出了兩個(gè)強(qiáng)指定驗(yàn)證人簽名方案。分析表明所提出的方案是安全高效的。

參考文獻(xiàn):

[1]SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Proc of CRYTO’84. Berlin: Springer-Verlag，1984: 47-53.

[2]JAKOBSSON M， SAKO K， IMPAGLIAZZO R. Designated verifiers proofs and their applications[C]//Lecture Notes in Computer Science 1070: Advances in Cryptology - Eurocrypt’96. Berlin: Springer-Verlag，1996:143-154.

[3]SAEEDNIA S， KRAMER S， MARKOWITCH O. An efficient strong designated verifier signature scheme[C]//Proc of the 6th Internatio-nal Conference on Information Security and Cryptology’03. Berlin: Springer-Verlag，2003:40-54.

[4]SUSILO W， ZHANG F， MU Y. Identity-based strong designated verifier signature schemes[Z].2004:313-324.

[5]KUMAR K， SHAILAJA G， SAXENA A. Identity-based strong designated verifier signature scheme[EB/OL]. http://eprint.jacr.org/complete/134.pdf.

[6]KANG Bao-yuan， BOYD C， DAWSON E. A novel identity-based strong designated verifier signature scheme[J]. The Journal of Systems and Software，2009，82(2):270-273.

[7]MAMBO M， USUDA K， OKAMOTO E.Proxy signature: delegation of the power to sign messages[J]. IEICE Trans on Fundamentals，1996(9):1338-1354.

[8]GALBRAITH S D， HARRISON K， SOLDERA D. Implementing the tate pairing[C]//Proc of the 5th International Symposium on Algorithmic Number Theory. Berlin: Springer-Verlag，2002:324-337.