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

湯鵬志，陳仁群，左黎明

（華東交通大學基礎科學學院，江西 南昌 330013）

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

湯鵬志，陳仁群，左黎明

（華東交通大學基礎科學學院，江西 南昌 330013）

通過對余昭平等人提出的一種基于橢圓曲線上的門限盲簽名方案的分析，了解到該方案結合了橢圓曲線、門限盲簽名的雙重優勢。在原方案的基礎上提出了一種基于橢圓曲線的門限部分盲簽名的方案，不僅保留了原方案的強可驗證性性、不可偽造性等安全特性，還進一步增加了簽名的穩定性、部分盲性及密鑰共享等特性。最后，對新提出的方案進行了可證的安全性分析及效率分析，事實證明該方案安全性高、穩定性好。

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

1982年，David Chuam［1］首次提出了盲簽名，把盲簽名類比成內嵌復寫紙的信封進行傳遞信息這一事例，并對盲簽名的概念及具體實現過程進行了較為詳細的論述。盲簽名最大的特點就是把消息進行盲化，這可以有效保護簽署消息的具體內容，所以它在電子商務和電子選舉等領域有著廣泛的應用。盲簽名一般分為盲化消息、簽名盲化消息、對消息進行脫盲三個階段。根據對消息的盲化程度又把盲簽名分為強盲簽名和弱盲簽名。

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

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

1 預備知識

1.1 離散對數難題（DLP）與計算Diffie-Hellman難題（CDHP）

假設G是一個加法群，在G上的2個數學難題分別為：

1.2 門限部分盲簽名

門限部分盲簽名系統是指一個由n個簽名者組成的群體，該群體有一個公、私密鑰對，群體內任意人數大于等于t個合法、誠實簽名者的子群體都可代表這個群體進行簽名，并且任意的第三方可利用該群體的公鑰進行簽名驗證。下面是門限部分盲簽名方案的主要實現過程：

1）在n個成員的系統中必須至少有t個成員達成協議，共同行使簽名權，并且商定共同消息c；

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

3）用戶將被簽名的消息m盲化并發送給每個簽名者；

4）每個簽名者分別用自己的私鑰對盲化的消息進行簽名，得到簽名s，再發送給用戶；

5）用戶收到簽名s后進行脫盲，得到簽名s'；

6）任何第三方可以進行驗證，并無法獲取有關于c的任何消息。

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

2.1 系統參數生成

可信中心CA選取定義在有限域F2p上的一條合適非超奇異的橢圓曲線E，其中，p為一個大素數，使得橢圓曲線群上的離散對數問題是難解的，且P為橢圓曲線E上q階的基點，公開參數p，q，E，P，接著

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

2.2 部分盲簽名方案

2.2.1 密鑰提取

密鑰管理中心隨機選擇t-1階多項式

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

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

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

對簽名者G，驗證

若式（1）成立，則簽名者G進行對消息簽名，否則拒絕簽名。

2.2.2 部分盲簽名

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

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

2.2.3 簽名驗證

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

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

2.3 門限部分盲簽名方案

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

2.3.1 密鑰共享協議［12］

密鑰管理中心隨機選擇t-1階多項式

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

其中：IDi是簽名者Gi的身份標識，且每個簽名者的身份標識是不同的，即當i≠j時，IDi≠IDj。

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

對每個參與者Gi，驗證

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

2.3.2 門限部分盲簽名生成協議

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

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

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

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

2.3.3 簽名驗證協議

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

3 安全性分析

3.1 穩定性

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

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

在新方案中，若后面有新的簽名者Gi想加入門限簽名協議，可信中心CA只需給新成員提供一個與其他成員人不同的公開身份，并計算簽名者的私鑰發送給他即可，無需改動系統及之前成員的相關參數。若某個成員想退出該協議，可信中心CA只需廣播該成員的ID無效。因此，該方案具有良好的穩定性。

3.2 正確性

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

3.3 部分盲性

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

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

3.4 不可偽造性

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

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

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

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

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

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

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

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

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

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

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

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

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

從而算法S解決了ECDLP。

在的計算時間方面，每次簽名詢問都是最多需要1次雙線性對逆運算。所以

其中：τ表示回答一個H提問所需要的時間。

然后，我們先給出一個等價定義：

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

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

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

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

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

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

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

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

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

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

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

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

4 效率分析

表1是將文獻［8］所提的方案與本方案的效率分析，通過通信量與計算量兩方面的指標進行了明確的對比。為方便敘述，給出以下標記：tH、tM、tE(?)、tE(+)、tI分別代表計算哈希函數的運算時間、模乘的運算時間、橢圓曲線上加法運算時間、橢圓曲線上點乘運算時間及求逆運算時間。至于一般的加減法運算，和一般的數乘運算所需時間表中忽略不計。

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

5 結束語

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

[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].通信學報,2001,22(9):1-6.

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

[5]陸洪文,鄭卓.基于雙線性對的門限部分盲簽名方案[J].計算機應用,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]余昭平,康斌.基于橢圓曲線的新型可驗證門限盲簽名方案[J].計算機工程,2007,33(23):161-162.

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

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

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

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

[13]周萍,何大可.一種CDH難題的強壯門限盲簽名方案設計[J].計算機應用研究,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

國家自然科學基金項目（11361024，11061014）；江西省教育廳科技項目（GJJ13339）；華東交通大學校立科研基金項目（11JC04）

湯鵬志（1961—），男，教授，主要研究方向為信息安全。

1005-0523（2014）06-0096-07