湯鵬志，陳仁群，左黎明

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西 南昌 330013）

一種基于橢圓曲線的門限部分盲簽名方案

湯鵬志，陳仁群，左黎明

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西 南昌 330013）

通過對(duì)余昭平等人提出的一種基于橢圓曲線上的門限盲簽名方案的分析，了解到該方案結(jié)合了橢圓曲線、門限盲簽名的雙重優(yōu)勢(shì)。在原方案的基礎(chǔ)上提出了一種基于橢圓曲線的門限部分盲簽名的方案，不僅保留了原方案的強(qiáng)可驗(yàn)證性性、不可偽造性等安全特性，還進(jìn)一步增加了簽名的穩(wěn)定性、部分盲性及密鑰共享等特性。最后，對(duì)新提出的方案進(jìn)行了可證的安全性分析及效率分析，事實(shí)證明該方案安全性高、穩(wěn)定性好。

橢圓曲線；門限；部分盲性；不可偽造

1982年，David Chuam［1］首次提出了盲簽名，把盲簽名類比成內(nèi)嵌復(fù)寫紙的信封進(jìn)行傳遞信息這一事例，并對(duì)盲簽名的概念及具體實(shí)現(xiàn)過程進(jìn)行了較為詳細(xì)的論述。盲簽名最大的特點(diǎn)就是把消息進(jìn)行盲化，這可以有效保護(hù)簽署消息的具體內(nèi)容，所以它在電子商務(wù)和電子選舉等領(lǐng)域有著廣泛的應(yīng)用。盲簽名一般分為盲化消息、簽名盲化消息、對(duì)消息進(jìn)行脫盲三個(gè)階段。根據(jù)對(duì)消息的盲化程度又把盲簽名分為強(qiáng)盲簽名和弱盲簽名。

1996年Abe等人［2］提出了部分盲簽名，為的是解決因盲簽名中簽名人完全不知道最終簽名的任何信息而造成實(shí)際應(yīng)用中數(shù)據(jù)庫(kù)無限增長(zhǎng)等問題。隨后，國(guó)內(nèi)一些研究者也相繼提出一些部分盲簽名方案。2001年，鐘鳴等人［3］率先提出了一種基于比特承諾的部分盲簽名方案。2004年，李鴻［4］提出了一種基于橢圓曲線的部分盲簽名方案，該方案具有密鑰比特?cái)?shù)少，在與基于乘法群的密碼體制相同條件下安全性更高的特點(diǎn)。2005年，陸洪文等人［5］又提出了一種基于雙線性對(duì)的門限部分盲簽名方案。這里的“門限”是指對(duì)于有n個(gè)成員的系統(tǒng)中必須至少有t個(gè)成員達(dá)成協(xié)議，共同完成簽名。“門限”一詞最早是由Desmedt等人［6-7］提出，隨后基于Shamir的門限秘密共享思想提出了第一個(gè)門限簽名方案。該方案進(jìn)一步擴(kuò)展了盲簽名在電子商務(wù)中的應(yīng)用，它可以讓多人同時(shí)參與簽名。2007年，余昭平等人［8］又在此基礎(chǔ)上提出了一種新型的基于橢圓曲線的門限盲簽名方案，并且證明了該方案具有盲性、魯棒性、不可偽造性等安全特性。2008年，閆東升等人［9］提出了一種新的高效的基于身份的部分盲簽名方案。2011年，張建中等人［10］又提出了一種隨機(jī)化部分盲簽名方案。2013年，石賢芝等人［11］提出了一種標(biāo)準(zhǔn)模型下高效的門限簽名方案。這些方案大多是在前人的基礎(chǔ)上做了一些相應(yīng)的改進(jìn)。

在電子選票中，很多時(shí)候我們只需要從n個(gè)選舉人中選出t個(gè)人進(jìn)行一場(chǎng)投票選舉，這樣就防止有些選舉人員因個(gè)人問題不能來參加選舉這一情況，保證選舉在規(guī)定的時(shí)間及場(chǎng)合進(jìn)行。提出一種新型的基于橢圓曲線的門限部分盲簽名方案，它將橢圓曲線、秘密共享及盲簽名三者的優(yōu)勢(shì)充分結(jié)合在一起，適用于電子選舉、電子投票及某些軍事領(lǐng)域方面。

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

1.1 離散對(duì)數(shù)難題（DLP）與計(jì)算Diffie-Hellman難題（CDHP）

假設(shè)G是一個(gè)加法群，在G上的2個(gè)數(shù)學(xué)難題分別為：

1.2 門限部分盲簽名

門限部分盲簽名系統(tǒng)是指一個(gè)由n個(gè)簽名者組成的群體，該群體有一個(gè)公、私密鑰對(duì)，群體內(nèi)任意人數(shù)大于等于t個(gè)合法、誠(chéng)實(shí)簽名者的子群體都可代表這個(gè)群體進(jìn)行簽名，并且任意的第三方可利用該群體的公鑰進(jìn)行簽名驗(yàn)證。下面是門限部分盲簽名方案的主要實(shí)現(xiàn)過程：

1）在n個(gè)成員的系統(tǒng)中必須至少有t個(gè)成員達(dá)成協(xié)議，共同行使簽名權(quán)，并且商定共同消息c；

2）每個(gè)簽名者分別獲取自己的公、私鑰；

3）用戶將被簽名的消息m盲化并發(fā)送給每個(gè)簽名者；

4）每個(gè)簽名者分別用自己的私鑰對(duì)盲化的消息進(jìn)行簽名，得到簽名s，再發(fā)送給用戶；

5）用戶收到簽名s后進(jìn)行脫盲，得到簽名s'；

6）任何第三方可以進(jìn)行驗(yàn)證，并無法獲取有關(guān)于c的任何消息。

2 基于橢圓的門限部分盲簽名方案

2.1 系統(tǒng)參數(shù)生成

可信中心CA選取定義在有限域F2p上的一條合適非超奇異的橢圓曲線E，其中，p為一個(gè)大素?cái)?shù)，使得橢圓曲線群上的離散對(duì)數(shù)問題是難解的，且P為橢圓曲線E上q階的基點(diǎn)，公開參數(shù)p，q，E，P，接著

為方便描述所提出的橢圓門限簽名方案及其安全性分析，我們先給出一個(gè)基礎(chǔ)的部分盲簽名方案，該方案的密鑰提取參照了彭慶軍［12］等人的方案，在密鑰提取階段嵌入了簽名者的身份，提升了方案的穩(wěn)定性。

2.2 部分盲簽名方案

2.2.1 密鑰提取

密鑰管理中心隨機(jī)選擇t-1階多項(xiàng)式

其中：f(0)=a0=d∈Zq為中心私鑰；Q=dP為中心公鑰。計(jì)算

其中：ID是簽名者G的身份信息。

把b通過安全信道秘密地發(fā)送給相應(yīng)的簽名者G，作為簽名者G的私鑰，并公開公鑰Q'=bP。

對(duì)簽名者G，驗(yàn)證

若式（1）成立，則簽名者G進(jìn)行對(duì)消息簽名，否則拒絕簽名。

2.2.2 部分盲簽名

（簽名）簽名者G收到h后，計(jì)算s=(kH1(c)+h)Q并發(fā)送給用戶U。

（脫盲）用戶U收到s后，計(jì)算s'=αs，得到消息m的部分盲簽名（r,K,s',m,c)。

2.2.3 簽名驗(yàn)證

驗(yàn)證者先計(jì)算h=H0(m||c,r)，任何人可以通過下面的等式驗(yàn)證簽名的有效性：

若等式（2）成立，則接受該簽名，否則拒絕。

2.3 門限部分盲簽名方案

在余昭平等人的門限盲簽名方案的基礎(chǔ)上，提出一種高效安全的門限部分盲簽名方案。以下是關(guān)于具體方案的執(zhí)行步驟。

2.3.1 密鑰共享協(xié)議［12］

密鑰管理中心隨機(jī)選擇t-1階多項(xiàng)式

其中：g(0)=a0=d∈Zq為中心私鑰；Q=dP為中心公鑰；計(jì)算

其中：IDi是簽名者Gi的身份標(biāo)識(shí)，且每個(gè)簽名者的身份標(biāo)識(shí)是不同的，即當(dāng)i≠j時(shí)，IDi≠IDj。

把di通過安全信道秘密地發(fā)送給相應(yīng)的簽名者Gi，并公開dP,aiP(i=1,2,...,t-1)。

對(duì)每個(gè)參與者Gi，驗(yàn)證

若式（1）成立，則簽名者Gi廣播“確認(rèn)”消息，否則Gi廣播“中止”消息。

2.3.2 門限部分盲簽名生成協(xié)議

根據(jù)門限定義，在n個(gè)成員的系統(tǒng)中必須至少有t個(gè)成員達(dá)成協(xié)議，才能行使共同簽名權(quán)，不妨設(shè)成員G={G1,G2,...,Gt}t個(gè)成員已經(jīng)達(dá)成協(xié)議共同行使簽名權(quán)，并共同協(xié)商了公共信息c（簽名發(fā)布日期、地點(diǎn)及電子貨幣金額等）。簽名過程如下：

1）每個(gè)簽名者Gi計(jì)算：bi=widi，其中，再計(jì)算Qi=biP并公開。接著，任取計(jì)算Ki=H1(c)kibi(1≤i≤t)并公開。

3）（簽名）簽名者Gi收到h后，計(jì)算si=(kiH1(c)+h)Qi并發(fā)送給用戶U。

4）（脫盲）用戶U收到si后，計(jì)算，得到消息m的部分盲簽名σ=（r,s,m,c)。

2.3.3 簽名驗(yàn)證協(xié)議

若等式（2）成立，則接受該簽名，否則拒絕。

3 安全性分析

3.1 穩(wěn)定性

定理1門限部分盲簽名方案具有良好的穩(wěn)定性。

證明該證明可直接參照彭慶軍［12］等人的方案。

在新方案中，若后面有新的簽名者Gi想加入門限簽名協(xié)議，可信中心CA只需給新成員提供一個(gè)與其他成員人不同的公開身份，并計(jì)算簽名者的私鑰發(fā)送給他即可，無需改動(dòng)系統(tǒng)及之前成員的相關(guān)參數(shù)。若某個(gè)成員想退出該協(xié)議，可信中心CA只需廣播該成員的ID無效。因此，該方案具有良好的穩(wěn)定性。

3.2 正確性

定理2門限部分盲簽名方案是正確的。

3.3 部分盲性

定理3門限部分盲簽名方案是部分盲性的。

證明用戶U若要去除簽名者Gi的簽名中的部分盲因子γ，δ，可這樣進(jìn)行脫盲，計(jì)算

3.4 不可偽造性

這里，我們假設(shè)一種最糟糕的情況：即攻擊者C可勾結(jié)t-1個(gè)密鑰分享者。接下來，我們參照文獻(xiàn)［13］并利用Gennaro［14-15］的思想進(jìn)行證明。在文獻(xiàn)［14］中，Gennaro思想為：如果新的門限盲簽名方案是可模擬的，所提出的基礎(chǔ)盲簽名方案是不可偽造的，則此門限盲簽名方案也是不可偽造的。所以，這里我們只需證明：新的門限部分盲簽名方案是可模擬的，所提出的基礎(chǔ)部分盲簽名方案是不可偽造的。即知門限部分盲簽名方案是不可偽造的。

下面首先給出定理4，證明所提出的基礎(chǔ)部分盲簽名方案是不可偽造的：

定理4在隨機(jī)預(yù)言機(jī)模型下，假設(shè)存在攻擊者C能夠在t時(shí)間內(nèi)，以ε的優(yōu)勢(shì)贏得自適應(yīng)性下選擇密文的游戲，那么，就存在一個(gè)算法F，能夠在時(shí)間內(nèi)，以O(shè)(ε)的優(yōu)勢(shì)解決橢圓曲線離散對(duì)數(shù)問題（ECDLP），其中，τadv表示計(jì)算一次逆運(yùn)算所需要的時(shí)間。

證明設(shè)算法F收到G中ECDLP實(shí)例(P,dP,Q)，其中d∈Zq未知，算法F調(diào)用攻擊者為子程序去求解d是否成立。

系統(tǒng)設(shè)置：F生成系統(tǒng)公共參數(shù)(p,q,E,P,Q)，其中系統(tǒng)公鑰設(shè)置為Q=dP，即用d（未知）模擬系統(tǒng)主密鑰。F隨機(jī)選取ID*∈{0,1}*，再將系統(tǒng)公開參數(shù)及ID*一起發(fā)送給攻擊者C。

詢問：需要維護(hù)列表L0響應(yīng)Α的 f詢問、L1響應(yīng)Α的H1詢問、L2響應(yīng)Α的H2詢問、LK響應(yīng)Α的密鑰提取詢問、LS響應(yīng)Α的部分盲簽名生成詢問；q0表示攻擊者至多進(jìn)行 f詢問的次數(shù)、q1表示攻擊者至多進(jìn)行H1詢問的次數(shù)、q2表示攻擊者至多進(jìn)行H2詢問的次數(shù)、qK表示攻擊者至多進(jìn)行密鑰提取詢問的次數(shù)、qS表示攻擊者至多進(jìn)行部分盲簽名生成詢問的次數(shù)。這些列表初始時(shí)是空的。具體交互過程如下：

f詢問：對(duì) F關(guān)于 f(ID)的詢問時(shí)，若 ID=ID*，則 F隨機(jī)選取，返回 b*；否則返回 bm(1≤m≤q0)。無論是否有ID=ID*，F(xiàn)都將(ID,b)（其中b=b*或bm）添加到表L0中。

H1詢問：對(duì)F關(guān)于H1(c)的詢問時(shí)，若在表L1中有(c,h)，則F返回h，否則F隨機(jī)選取返回，并把(c,h)添加在列表L1中。

H2詢問：對(duì)F關(guān)于H2(m||c,r)的詢問時(shí)，若在表L2中有(m,c,r,y)，則F返回y，否則F隨機(jī)選取返回，并把(m,c,r,y)添加在列表L2中。

密鑰提取詢問：對(duì)F關(guān)于ID的密鑰提取詢問（假設(shè)已經(jīng)做過關(guān)于ID的 f詢問，否則先執(zhí)行 f詢問），F(xiàn)從列表L0中找出項(xiàng)(ID,b)。如果ID=IDm，F(xiàn)宣告失敗，算法終止。否則，F(xiàn)計(jì)算Q=f(0)P=dP，將(dP,Q)添加到列表L3。

部分盲簽名生成詢問：當(dāng)詢問(ID,m,c)時(shí)，F(xiàn)首先查詢列表L0、L1得到(ID,b)和(c,h)，再隨機(jī)選取s'、，然后計(jì)算r=Rx(s'+K-Qy))，并定義H2(m||c,r)=y，最后若在列表L2中有(m,c,r,y)，則F終止并輸出失敗，否則F將(r,K,s')發(fā)送給C，并將(m,c,r,y)添加到列表L2中。

偽造：最后，如果算法F沒有終止，則C在沒有做過密鑰提取詢問和部分簽名詢問的條件下，以一個(gè)不可忽略的概率ε對(duì)一個(gè)輸入消息m輸出對(duì)應(yīng)的有效部分盲簽名（r,K,s',m,c)。根據(jù)Forking引理［16］，通過對(duì)C哈希重放，存在有效的算法S可以獲得兩個(gè)關(guān)于消息m及c的有效簽名（r1,K1,s1',m,c)和（r2,K2,s2',m,c)，其中r1≠r2。結(jié)合這兩個(gè)有效的部分盲簽名，算法S能以一個(gè)不可忽略的概率解決ECDLP，從而反證所提出的門限部分盲簽名方案是不可偽造的。證明步驟如下：

給定橢圓曲線上的一個(gè)任意二元組（P,Q)，令Q=aP。待算法S與攻擊者C執(zhí)行了多項(xiàng)式次部分盲簽名協(xié)議后，算法S得到兩個(gè)有效的部分盲簽名（r1,K1,s1',m,c)和（r2,K2,s2',m,c)，其中r1≠r2。即有下面2個(gè)等式

從而算法S解決了ECDLP。

在的計(jì)算時(shí)間方面，每次簽名詢問都是最多需要1次雙線性對(duì)逆運(yùn)算。所以

其中：τ表示回答一個(gè)H提問所需要的時(shí)間。

然后，我們先給出一個(gè)等價(jià)定義：

定義［14］所提出的門限部分盲簽名方案是可模擬的，等價(jià)于以下兩個(gè)條件成立：

1）密鑰共享協(xié)議算法是可模擬的。存在模擬器1，當(dāng)輸入中心公鑰Q和被攻擊者勾結(jié)的t-1個(gè)成員的私鑰d1,d2,...,dt-1時(shí)，能夠模擬攻擊者在密鑰共享協(xié)議算法中輸出Q的全過程。

2）門限部分盲簽名生成算法是可模擬的。存在模擬器2，當(dāng)輸入公鑰Q、消息m、公共消息c和它的簽名（r,s,m,c)，t-1個(gè)成員的私鑰d1,d2,...,dt-1時(shí)，能夠模擬攻擊者在門限部分盲簽名生成算法中輸出σ=（r,s,m,c)的全過程。

最后，給出定理5并證明第三部分所提出的方案是抗攻擊的。

定理5［13］在計(jì)算Diffie-Hellman難題假設(shè)下，即使攻擊者勾結(jié)t-1個(gè)成員，這里提出的新方案仍是安全的。

證明根據(jù)Gennaro的思想，下面我們只需證明門限部分盲簽名方案是可模擬的。

不失一般性，假設(shè)攻擊者C成功勾結(jié)了t-1個(gè)成員G1,G2,...,Gt-1。

1）證明門限密鑰生成算法是可模擬的。模擬器1［13］擁有中心公鑰Q和被勾結(jié)的t-1個(gè)成員的私鑰d1,d2,...,dt-1及d，再根據(jù)等式

模擬器1可以反算出Qt=btP，并類似地計(jì)算出Qi=biP(i=t+1,...,n)。所以模擬器1可以模擬攻擊者在密鑰共享協(xié)議算法中輸出Q的全過程。

2）證明門限簽名算法是可模擬的。設(shè)模擬器2擁有盲消息m、部分盲簽名σ=（r,s,m,c)、被勾結(jié)的t-1個(gè)成員的私鑰d1,d2,...,dt-1及d。模擬器2可以從d1,d2,...,dt-1計(jì)算出消息m的子簽名si=(kiH1(c)+h)Qi(i=1,2,...,t-1)，根據(jù)等式

模擬器2可以反算出σt=（rt,st,m,c)，類似地計(jì)算出σi=（ri,si,m,c)(i=t+1,...,n)。所以模擬器2可以模擬攻擊者在門限部分盲簽名生成算法中輸出σ=（r,s,m,c)的全過程。

綜上，可知該方案是不可偽造的。

4 效率分析

表1是將文獻(xiàn)［8］所提的方案與本方案的效率分析，通過通信量與計(jì)算量?jī)煞矫娴闹笜?biāo)進(jìn)行了明確的對(duì)比。為方便敘述，給出以下標(biāo)記：tH、tM、tE(?)、tE(+)、tI分別代表計(jì)算哈希函數(shù)的運(yùn)算時(shí)間、模乘的運(yùn)算時(shí)間、橢圓曲線上加法運(yùn)算時(shí)間、橢圓曲線上點(diǎn)乘運(yùn)算時(shí)間及求逆運(yùn)算時(shí)間。至于一般的加減法運(yùn)算，和一般的數(shù)乘運(yùn)算所需時(shí)間表中忽略不計(jì)。

表1 文獻(xiàn)［8］及本方案的效率分析對(duì)比Tab.1 Efficiency contrast between reference［8］and the proposed scheme

5 結(jié)束語(yǔ)

隨著電子信息時(shí)代的迅速發(fā)展，電子商務(wù)、電子選舉、電子支付、電子政務(wù)等越來越普遍，信息安全就顯得尤為重要。本文提出的方案是結(jié)合了橢圓曲線、門限方案及部分盲簽名提出的一種基于橢圓曲線上的門限部分盲簽名，這個(gè)方案具有短密鑰、簽名人數(shù)自由及部分盲性等特點(diǎn)，并進(jìn)一步擴(kuò)展了盲簽名的應(yīng)用范圍，在一定程度上解決了盲簽名在匿名性與可控性之間的矛盾。最后，借鑒Gennaro的思想對(duì)其進(jìn)行了詳細(xì)的安全性分析，證明了該方案是安全可行的。

[1]CHAUM D.Blind Signature for Untraceable Payments[C]//Proceeding of Advance in Crytology-EUROCtypto’82,Plenum Press, 1983:199-203.

[2]ABEm,FUJISAKI E.How to Date Blind Signature[C]//Proceedings of Advances in Cryptology-Asiacrypt’96,LNCS,Springer, 1996:244-251.

[3]鐘鳴,楊義先.一種基于比特承諾的部分盲簽名方案[J].通信學(xué)報(bào),2001,22(9):1-6.

[4]李鴻.一種基于橢圓曲線的部分盲簽名方案[J].宿州師專學(xué)報(bào),2004,19(1):89-91.

[5]陸洪文,鄭卓.基于雙線性對(duì)的門限部分盲簽名方案[J].計(jì)算機(jī)應(yīng)用,2005,25(9):2057-2059.

[6]DESMEDT Y,FRANKEL Y.Threshold cryptosystems[C]//Advances in Cryptology-Crypto 89,Lectures Notes in Computer Sci?ence 435,Berlin:Springer-Verlag,1989:307-315.

[7]DESMEDT Y.Threshold cryptosystems[J].European Trans on Telecommunications,1994,5(4):449-457.

[8]余昭平,康斌.基于橢圓曲線的新型可驗(yàn)證門限盲簽名方案[J].計(jì)算機(jī)工程,2007,33(23):161-162.

[9]閆東升.一個(gè)新的高效的基于身份的部分盲簽名方案[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(2):137-139.

[10]張建中,馬冬蘭.一種高效的門限部分盲簽名方案[J].計(jì)算機(jī)工程,2012,38(1):130-134.

[11]石賢芝,林昌露,張勝元,等.標(biāo)準(zhǔn)模型下高效的門限簽名方案[J].計(jì)算機(jī)應(yīng)用,2013,33(1):15-18.

[12]彭慶軍.一種基于橢圓曲線的可驗(yàn)證門限簽名方案[J].通信技術(shù),2008,3(41):104-106.

[13]周萍,何大可.一種CDH難題的強(qiáng)壯門限盲簽名方案設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用研究,2011,28(2):704-707.

[14]GENNARO R,JARECKI S,KRAWCZYK H,et al.Robust threshold DSS signatures[C]//Lectures Notes in Computer Science,Ber?lin:Springer-Verlag,1996:354-371.

[15]GENNARO R,JARECKI S,KRAWCZYK H,et al.Secure distributed key generation for discrete-log based cryptosystems[C]// Lectures Notes in Computer Science,Berlin:Springer-Verlag,1999:295-310.

[16]POINTCHEVAL D,STERN J.Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,13(3): 316-396.

A Threshold Partially Blind Signature Based on ECDLP

Tang Pengzhi,Chen Renqun,Zuo Liming
(School of Basic Science,East China Jiaotong University,Nanchang 330013,China)

The threshold blind signature based on ECDLP presented by Yu et al.combines advantages of elliptic curve signature and blind threshold signature.This study proposes a new threshold partially blind signature based on ECDLP,which not only keeps strong-verification and unforgeability,but also further increases stability and key sharing.Through provable security and efficiency analysis,it verifies the higher safety and good stability for the proposed new scheme.

elliptic curve;threshold;partially blind signature;unforgeability

TP301

A

2014-09-22

國(guó)家自然科學(xué)基金項(xiàng)目（11361024，11061014）；江西省教育廳科技項(xiàng)目（GJJ13339）；華東交通大學(xué)校立科研基金項(xiàng)目（11JC04）

湯鵬志（1961—），男，教授，主要研究方向?yàn)樾畔踩?/p>

1005-0523（2014）06-0096-07