程亞歌 賈志娟 胡明生 公備 王利朋

摘 要：針對傳統(tǒng)的盲簽名、群簽名等簽名算法適用于區(qū)塊鏈異構(gòu)網(wǎng)絡(luò)時可能出現(xiàn)依賴可信中心、效率低等問題，提出了適用于區(qū)塊鏈電子投票場景的門限簽名方案。該方案基于Asmuth-Bloom秘密共享方案，無需可信中心。首先，由區(qū)塊鏈節(jié)點通過相互協(xié)作產(chǎn)生簽名，實現(xiàn)節(jié)點之間相互驗證功能，提升節(jié)點可信度;其次，建立節(jié)點加入和退出機(jī)制，以適應(yīng)區(qū)塊鏈節(jié)點流動性大等特點;最后，定期更新節(jié)點私鑰，以抵抗移動攻擊，使其具有前向安全性。安全性分析表明，該方案的安全性基于離散對數(shù)難題，能夠有效地抵御移動攻擊，滿足前向安全性;性能分析表明，與其他方案相比，該方案在簽名生成和驗證階段的計算復(fù)雜度較低，計算量較小。結(jié)果表明，所提方案能夠很好地適用于區(qū)塊鏈電子投票場景。

關(guān)鍵詞：區(qū)塊鏈;電子投票;秘密共享;門限簽名;中國剩余定理

中圖分類號：TP393.08

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

Threshold signature scheme suitable for blockchain electronic voting scenes

CHENG Yage1， JIA Zhijuan1*， HU Mingsheng1， GONG Bei2， WANG Lipeng1

1.College of Information Science and Technology， Zhengzhou Normal University， Zhengzhou Henan 450044， China;

2.College of Computer Sciences， Beijing University of Technology， Beijing 100124， China

Abstract：

When traditional signature algorithms such as blind signature and group signature applied to heterogeneous networks of blockchain， they might have problems like relying on trusted centers or low efficiency. Aiming at the problems， a threshold signature scheme suitable for blockchain electronic voting scenes was proposed. The proposed scheme was based on the Asmuth-Bloom secret sharing scheme and did not need a trusted center. Firstly， the signature was generated by the collaboration of blockchain nodes， implementing mutual verification between nodes and improving the node credibility. Secondly， a mechanism of nodes joining and exiting was established to adapt to the high mobility of the blockchain nodes. Finally， the node private keys were updated regularly to resist mobile attacks and make them forward-secure. Security analysis shows that the security of the scheme is based on the discrete logarithm problem， so that the scheme can effectively resist mobile attacks and is forward-secure. The performance analysis shows that compared with other schemes， this scheme has lower computational complexity in the signature generation and verification phases. The results show that the proposed scheme can be well applied to blockchain electronic voting scenes.

Key words：

blockchain; electronic voting; secret sharing; threshold signature; Chinese remainder theorem

0 引言

區(qū)塊鏈[1]是一種按照時間順序?qū)?shù)據(jù)塊以順序相連的方式組合成一種鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，并以密碼學(xué)的方式保證數(shù)據(jù)不可篡改和不可偽造的分布式賬本系統(tǒng)。作為電子貨幣交易的底層技術(shù)，區(qū)塊鏈具有去中心化、匿名化、不可篡改、公開透明等良好特性，解決了數(shù)據(jù)在傳輸過程中的可信性，其在金融、醫(yī)療、能源互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等領(lǐng)域發(fā)展迅速。

目前電子投票技術(shù)得到了廣泛應(yīng)用，然而大部分的電子投票簽名方案基于傳統(tǒng)的簽名算法，如群簽名、環(huán)簽名、盲簽名、代理簽名等不能適配到區(qū)塊鏈網(wǎng)絡(luò)中。當(dāng)前為人熟知的門限簽名方案，按照管理者的身份不同，主要分為兩種：有可信中心和無可信中心。有可信中心的門限簽名方案，主要有可信中心擔(dān)任管理者角色，承擔(dān)大部分的管理任務(wù)，勢必會影響到網(wǎng)絡(luò)的運行效率;而無可信中心的門前簽名方案無需考慮中心化存在的困擾。設(shè)計適用于區(qū)塊鏈的門限簽名方案，需要考慮區(qū)塊鏈去中心化的特性。此外區(qū)塊鏈節(jié)點流動性較大，當(dāng)有節(jié)點加入和退出時，要求簽名算法能夠支持節(jié)點的加入和退出。由于區(qū)塊鏈網(wǎng)絡(luò)的異構(gòu)性，存在計算資源需求量大的缺點，另外區(qū)塊鏈?zhǔn)窃诓话踩诺郎蟼鬏斝畔?，因此需要設(shè)計安全的身份認(rèn)證機(jī)制。針對區(qū)塊鏈網(wǎng)絡(luò)的獨有特性，如何設(shè)計一種安全的，適用于區(qū)塊鏈投票場景的門限簽名是本文的研究重點。

1979年，Shamir等[2]首次提出了基于拉格朗日插值多項式的秘密共享方案?；诖朔桨傅难芯咳缥墨I(xiàn)[3]方案，該方案無可信中心，且可動態(tài)增加或刪除參與者;文獻(xiàn)[4]方案利用聯(lián)合秘密共享技術(shù)，采用改進(jìn)的ElGamal簽名方案，解決了節(jié)點聯(lián)合攻擊造成其他節(jié)點私鑰泄漏的問題;文獻(xiàn)[5]方案經(jīng)過簽名后，惡意攻擊者可根據(jù)漏洞獲得節(jié)點私鑰和組私鑰，使得簽名信息不可信;文獻(xiàn)[6]方案是基于多證書認(rèn)證機(jī)構(gòu) （Certification Authority， CA）的公鑰認(rèn)證系統(tǒng)。以上方案計算量較大，適用于區(qū)塊鏈網(wǎng)絡(luò)時，會降低區(qū)塊鏈網(wǎng)絡(luò)的效率。文獻(xiàn)[7]方案具有可信中心;文獻(xiàn)[8]方案允許節(jié)點加入，但沒有考慮節(jié)點撤銷問題;因此，都不能適用于區(qū)塊連網(wǎng)絡(luò)應(yīng)用場景。

1983年，Asmuth 等[9]提出了基于中國剩余定理的秘密共享方案，與Shamir方案相比具有計算量小的優(yōu)點。文獻(xiàn)[10]方案假定節(jié)點集合固定不變，沒有考慮節(jié)點動態(tài)變化的情況;文獻(xiàn)[11]方案有可信中心;文獻(xiàn)[12]方案沒有考慮節(jié)點退出的情況;文獻(xiàn)[13]方案節(jié)點的秘密份額一經(jīng)分發(fā)就不再改變，難以抵抗移動攻擊;文獻(xiàn)[14]基于強RSA（Rivest，Shamir，Adleman）假設(shè)，實現(xiàn)了方案的前向安全性，但沒有考慮節(jié)點動態(tài)變化情況;文獻(xiàn)[15]方案需可信中心分發(fā)秘密份額，文獻(xiàn)[16]方案在驗證過程中也需要可信中心參與驗證過程;文獻(xiàn)[17]方案允許節(jié)點加入，但是攻擊者可根據(jù)廣播信息獲得老節(jié)點私鑰，存在安全隱患;文獻(xiàn)[18]方案將零知識證明協(xié)議和離散對數(shù)難題相結(jié)合，保證了信息傳輸?shù)陌踩?。文獻(xiàn)[19]中提出了基于中國剩余定理的區(qū)塊鏈門限簽名，該方案解決了上述方案適用于區(qū)塊鏈簽名的諸多問題，提高了效率，但是該方案不能抵抗移動攻擊，不具有前向安全性。以上方案適配于區(qū)塊鏈網(wǎng)絡(luò)應(yīng)用場景時有所欠缺，不盡完善。

本文在Asmuth-Bloom秘密共享方案的基礎(chǔ)上，提出了適用于區(qū)塊鏈電子投票場景的門限簽名方案。方案擯棄了可信中心，通過節(jié)點之間相互協(xié)作產(chǎn)生簽名，具有相互驗證功能;設(shè)計了節(jié)點加入和退出機(jī)制，解決了節(jié)點加入和退出問題;定期更新節(jié)點私鑰，可有效預(yù)防移動攻擊。

1 預(yù)備知識

1.1 離散對數(shù)難題

所謂離散對數(shù)難題[20]，是指給定有限域GF（p），當(dāng)模p有原根時，設(shè)g為模Zp的一個原根（也可以說是有限循環(huán)群Zp的生成元），任給元素y∈Z*P，求解唯一的x，滿足1≤x

gx≡y（mod p）

稱為以p為模，以g為y的離散對數(shù)。這里給定g和y，求解x是離散對數(shù)難題。

1.2 中國剩余定理

中國剩余定理也即孫子定理[21]，最早見于我國古代著作《孫子算經(jīng)》里面。具體描述如下：設(shè)m1，m2，…，mn是n個兩兩互質(zhì)的正整數(shù)，其中：

Mmi ei≡1（mod mi）; M=m1·m2·…·mn，i=1，2，…，n

給定一組正整數(shù)b1，b2，…，bn，則同余式組：

x≡b1（mod m1）

x≡b2（mod m2）

x≡bn（mod mn）

對于模m具有唯一解：

x≡Mm1 e1b1+Mm2 e2b2+…+Mmn enbn（mod m）

1.3 Asmuth-Bloom秘密共享方案

Asmuth-Bloom秘密共享方案由Asmuth和Bloom于1983年提出，與Shamir提出的基于拉格朗日插值多項式的秘密共享方案相比，Asmuth-Bloom秘密共享方案具有計算量小、效率高的優(yōu)點。其方案主要包括以下3個步驟：

1）初始化。

假設(shè)DC（Distribution Center）是秘密分發(fā)者，P={P1，P2，…，Pn}是n個節(jié)點組成的集合，門限值為t，秘密為s。DC選擇大素數(shù)q（q>s），整數(shù)A，以及嚴(yán)格遞增正整數(shù)序列d={d1，d2，…，dn}，且d滿足以下條件：

① 0≤A≤M/q-1。

② d1

③ gcd（di，dj）=1; i≠j。

④ gcd（di，q）=1; i=1，2，…，n。

⑤ M=∏ti=1di>q∏t-1i=1dn-t+1

2）秘密分發(fā)。

秘密分發(fā)者DC計算：

z=s+Aq

zi=z mod di; i=1，2，…，n

并將（zi，di）發(fā)送給Pi（i=1，2，…，n），作為Pi的秘密份額。

3）秘密恢復(fù)。

任意節(jié)點通過相互交換秘密份額恢復(fù)秘密s。任選t個節(jié)點P1，P2，…，Pi作為恢復(fù)秘密的一組節(jié)點。通過節(jié)點之間相互交換秘密后，任意節(jié)點Pi都可建立如下同余方程組：

z≡z1（mod d1）

z≡z2（mod d2）

z≡zt（mod dt）

由中國剩余定理，該同余方程組有唯一解：

z=∑ti=1Ddi eiXi mod D; i=1，2，…，t

因此，可求出共享秘密s=z -Aq，也即s=z mod q。

2 本文方案

2.1 區(qū)塊鏈門限簽名方案架構(gòu)圖

本文基于中國剩余定理，提出一種新的適用于區(qū)塊鏈電子投票場景的門限簽名方案。其方案構(gòu)思架構(gòu)如圖1所示。

如圖1所示，區(qū)塊鏈門限簽名方案通過節(jié)點之間相互協(xié)作產(chǎn)生秘密份額，并計算驗證信息的正確性，當(dāng)驗證結(jié)果正確時產(chǎn)生組公鑰、組私鑰及每個區(qū)塊鏈節(jié)點的個人密鑰。區(qū)塊鏈節(jié)點利用個人私鑰產(chǎn)生自己的部分簽名，由簽名合成者合成簽名，簽名驗證者進(jìn)行驗證。同時方案允許節(jié)點加入和退出，定期更新私鑰，確保方案的前向安全性。其具體實施步驟如下：

1）密鑰生成。

①系統(tǒng)初始化：區(qū)塊鏈門限簽名系統(tǒng)初始化，選取公共參數(shù);

②秘密分割：區(qū)塊鏈節(jié)點隨機(jī)選取秘密數(shù)，通過節(jié)點之間相互協(xié)作產(chǎn)生秘密份額;

③計算驗證：區(qū)塊鏈節(jié)點計算驗證信息，并校驗信息的正確性;

④產(chǎn)生節(jié)點密鑰及組密鑰：區(qū)塊鏈節(jié)點計算個人私鑰，并根據(jù)每個節(jié)點隨機(jī)選取的秘密數(shù)計算組公鑰和組私鑰。

2）生成簽名。

①產(chǎn)生部分簽名：每個節(jié)點產(chǎn)生自己的部分簽名;

②合成簽名：簽名合成者將t個部分簽名合成待簽名消息的最終簽名。

3）驗證簽名。

驗證簽名：驗證者驗證最終簽名的正確性。

4）節(jié)點加入。

①計算偽私鑰;

②產(chǎn)生新節(jié)點私鑰。

5）節(jié)點退出。

①計算組公鑰：重新計算組公鑰，并將前期組公鑰存放在區(qū)塊鏈網(wǎng)絡(luò)中，當(dāng)需查看前期簽名信息時，調(diào)用組公鑰即可;

②其他節(jié)點計算更新私鑰。

6）節(jié)點私鑰更新。

①計算更新因子;

②產(chǎn)生新私鑰。

2.2 區(qū)塊鏈門限簽名方案詳細(xì)算法設(shè)計

設(shè)S={Genkey，Sign，Verify}為一般的簽名算法，則有n人參與的（t，n）區(qū)塊鏈分布式門限簽名算法可表示為：TS={TGenkey，TSign，Verify}。其中：TGenkey表示密鑰生成算法;TSign表示簽名算法;Verify表示驗證算法。

2.2.1 TGenkey：密鑰生成

1）區(qū)塊鏈電子投票系統(tǒng)初始化。

選取公共參數(shù)P，t，g，p，q，d，s，n，M。其中P={P1，P2，…，Pn}是n個參與區(qū)塊鏈投票系統(tǒng)簽名的節(jié)點集合，t為門限值，g為有限域GF（p）上的生成元，p、q為兩個大素數(shù)且滿足q/（p-1），d={d1，d2，…，dn}是一組嚴(yán)格單調(diào)遞增的正整數(shù)序列，q和d滿足Asmuth-Bloom方案，待簽名消息為s，M=∏ti=1di，公開n，t，g，p，q，d和M。

2）區(qū)塊鏈節(jié)點之間相互協(xié)作產(chǎn)生秘密份額。

每個區(qū)塊鏈節(jié)點Pi隨機(jī)選取子秘密λi和整數(shù)Zi，滿足如下條件：

0<λi<[q/n]

0

節(jié)點Pi計算秘密份額Xij：

Xij=（λi+Ziq） mod dj（1）

Pi保留Xii，廣播gλi，gZi，并將 Xij（i≠j）發(fā)送給節(jié)點Pj。

這里，子秘密λi和整數(shù)Zi由區(qū)塊鏈節(jié)點秘密選取，且沒有通過通信信道發(fā)送，因此其他人無法獲得。

3）區(qū)塊鏈節(jié)點Pi計算驗證信息δi、 μij，并驗證信息的正確性。

δi=gλi+Ziq mod p（2）

θij=（λi+Ziq-Xij）/dj（3）

μij=gθij mod p（4）

并在區(qū)塊鏈網(wǎng)絡(luò)中廣播δi、 μij。另外，節(jié)點Pj根據(jù)廣播信息δi和Xij后;通過以下等式驗證秘密份額的正確性：

gλi·gZiq mod p = δi（5）

（（gXij mod p）（（μij）dj mod p）） mod p=δi（6）

4）產(chǎn)生區(qū)塊鏈節(jié)點密鑰及組密鑰。

根據(jù)第3）步的驗證，若驗證結(jié)果正確，則節(jié)點Pj計算自己的私鑰：

Kj=∑ni=1Xij mod dj（7）

則節(jié)點公鑰為Cj=gKj。

根據(jù)每個區(qū)塊鏈節(jié)點選取的秘密數(shù)，產(chǎn)生組公鑰和組私鑰。其中，組公鑰為：

ψ=∏ni=1gλi mod p

組私鑰為：

φ=∑ni=1λi

2.2.2 TSign：產(chǎn)生簽名

任意t個區(qū)塊鏈節(jié)點利用自己的私鑰，根據(jù)中國剩余定理產(chǎn)生自己的部分簽名，t個部分簽名合成消息s的簽名。

1）生成部分簽名。

①節(jié)點Pi選取隨機(jī)數(shù)hi∈Zp，計算并廣播：

li=ghi mod p

Pj收到li后，計算：

l=g∑ti=1hi mod p=∏ti=1ghi mod p=∏ti=1li mod p

② Pi計算Hi=Ddi eiKi mod D，用于生成部分簽名，其中：

D=∏ti=1di

ei滿足：

ei≡（D/di）-1 mod di; i=1，2，…，n

③ Pi計算部分簽名Wi：

Wi=l·hi·s+Hi mod D（8）

并將部分簽名（s，l，W）發(fā)送給簽名合成者。

2）合成簽名。

簽名合成者收到t個區(qū)塊鏈節(jié)點發(fā)送的部分簽名Wi后，合成簽名W：

W=（∑ti=1Wi mod D） mod q（9）

則消息 s的簽名為 （s，l，W）。

2.2.3 Verify：驗證簽名

驗證者收到簽名信息（s，l，W）后，根據(jù)如下等式，使用組公鑰ψ驗證簽名的有效性：

gW≡ls·l·ψ mod p（10）

若上述等式成立，則說明簽名有效，接受簽名。

2.2.4 節(jié)點加入

假設(shè)有新節(jié)點Pi+1加入?yún)^(qū)塊鏈網(wǎng)絡(luò)，其加入過程如下：

1）新加入節(jié)點Pi+1選擇模數(shù)dn+1，且使dn+1滿足Asmuth-Bloom秘密共享方案。

2）由t個區(qū)塊鏈節(jié)點Pi（i=1，2，…，t）協(xié)助新加入節(jié)點Pi計算偽私鑰。

節(jié)點Pi隨機(jī)選取t個隨機(jī)數(shù)εij∈Zp（j=1，2，…，t），計算εi=∑tj=1εij mod p，并將εij發(fā)送給Pj，Pj計算ε′j：

ε′j=∑ti=1εij mod p

Pi計算偽私鑰：

K′i=（Ddi eiKi mod D） mod dn+1+（εi-ε′i）dn+1

并將K′i發(fā)送給Pn+1。

3）Pn+1收到t份偽私鑰K′i后，計算自己的私鑰：

Kn+1=（∑ti=1K′i mod D） mod dn+1（11）

當(dāng)有新節(jié)點加入?yún)^(qū)塊鏈網(wǎng)絡(luò)時，由區(qū)塊鏈節(jié)點協(xié)助其產(chǎn)生偽私鑰，新加入節(jié)點在收到其他t個節(jié)點的偽私鑰后計算自己的私鑰。在整個過程中組公鑰、組私鑰和其他節(jié)點的私鑰均未發(fā)生變化，因此對整個簽名過程沒有影響。

2.2.5 節(jié)點退出

假設(shè)區(qū)塊鏈節(jié)點Pk決定離開區(qū)塊鏈網(wǎng)絡(luò)，Pk廣播其離開的消息，其他節(jié)點剔除節(jié)點dk，不再接受其發(fā)送的消息。節(jié)點Pk離開后，其他節(jié)點及時更新密鑰，更新后組公鑰為：

ψ′=ψ/gλk

組私鑰：

φ′=φ/λk

節(jié)點私鑰：

K′j=（∑ni=1Xij-Xkj） mod dj

由于節(jié)點密鑰由節(jié)點相互協(xié)作產(chǎn)生，當(dāng)有節(jié)點離開時，相應(yīng)的組公鑰、組私鑰、節(jié)點私鑰等都要發(fā)生變化，會因節(jié)點的離開而造成之前簽名信息不可用。為了保證節(jié)點的離開不會因組公鑰的改變而造成在此之前的簽名信息無效，將前期組公鑰ψ存儲到區(qū)塊鏈網(wǎng)絡(luò)中，當(dāng)需要查看之前的簽名信息時，可以在區(qū)塊鏈的歷史記錄中找到組公鑰ψ并啟用。這樣確保了節(jié)點退出后，仍然可以查閱之前簽名信息。

區(qū)塊鏈本質(zhì)上是一個去中心化的數(shù)據(jù)庫，同時作為比特幣的底層技術(shù)，是一串使用密碼學(xué)方法相關(guān)聯(lián)產(chǎn)生的數(shù)據(jù)塊，區(qū)塊鏈每一個數(shù)據(jù)塊中包含了一批次比特幣網(wǎng)絡(luò)交易的信息，區(qū)塊鏈網(wǎng)絡(luò)平均每10min產(chǎn)生一個合法區(qū)塊，區(qū)塊鏈節(jié)點在參與投票的同時維護(hù)區(qū)塊鏈投票系統(tǒng)的正常運行，節(jié)點在合法區(qū)塊產(chǎn)生時間段內(nèi)通過挖礦將在此過程中更新掉的組公鑰存儲在合法區(qū)塊中。

區(qū)塊鏈強大的計算力保證了區(qū)塊鏈網(wǎng)信息的安全，它公開透明，任何人都可以在區(qū)塊鏈網(wǎng)絡(luò)中查看存儲在上面的信息，而且可以檢驗信息的正確性。因此將組公鑰保存在區(qū)塊鏈網(wǎng)絡(luò)中，既確保了信息的安全可信，也保證了之前簽名信息的有效性，解決了節(jié)點退出時存在的之前簽名失效等問題。

當(dāng)區(qū)塊鏈網(wǎng)絡(luò)中同時離開的節(jié)點個數(shù)大于等于t時，由于t個節(jié)點合作即可重構(gòu)秘密份額，導(dǎo)致簽名算法不安全，因此需要系統(tǒng)重新初始化，重新執(zhí)行簽名步驟1）～3）的操作。

2.2.6 節(jié)點私鑰更新

若有某攻擊者成功入侵并控制了某節(jié)點，該攻擊者能夠?qū)⒐裟繕?biāo)成功轉(zhuǎn)移到系統(tǒng)中的另一節(jié)點上，該攻擊稱為移動攻擊。區(qū)塊鏈節(jié)點自動保存系統(tǒng)信息，并通過相互連接傳遞信息，若有某節(jié)點被成功入侵，則其他節(jié)點將存在極大風(fēng)險。因此，為避免移動攻擊，勢必對節(jié)點私鑰進(jìn)行定期更新，確保參與節(jié)點的安全性。

本文設(shè)計的（t，n）門限簽名，只有t個節(jié)點同時參與才能完成簽名。私鑰更新確保攻擊者即使在某時刻控制了某一節(jié)點也無法在有限時間內(nèi)同時入侵t個節(jié)點。

另外，私鑰更新，使得攻擊者即使獲得了T時間段內(nèi)的某節(jié)點的信息，也無法獲得在此之前的私鑰信息，避免攻擊者篡改簽名信息的可能性，保證簽名信息的前向安全性。

設(shè)節(jié)點私鑰更新周期為T，則更新算法如下：

1）節(jié)點Pi隨機(jī)選取整數(shù)ZTi，滿足初始條件;

2）節(jié)點Pi計算更新因子：

XTij=ZTiq mod dj

并將更新因子XTij發(fā)送給節(jié)點Pj，廣播gZTi;

3）節(jié)點Pi計算驗證信息及驗證公式：

δTi=gZTiq mod p

θTij=（ZTiq-XTij）/dj

μTij=gθTij mod p

并廣播 δTi和 μTij。

4）節(jié)點 Pi收到Pi發(fā)送的信息XTij，以及廣播信息δTi、 μTij和gZTi，由以下兩個等式驗證更新因子的正確性：

（gZTi）q mod p=δTi

（（gXTij mod p）（（μTij）dj mod p））mod p=δTi

5）若驗證等式成立，則Pj計算T時段的私鑰：

KTj=KT-1j+∑ni=1XTij mod dj

更新產(chǎn)生的新私鑰，仍然可以按照簽名過程進(jìn)行簽名和驗證。更新過程中組公鑰不變，因此更新前的簽名依然有效。

3 方案分析

3.1 正確性分析

定理1 節(jié)點Pi根據(jù)廣播信息gλi、gZi和δi ，證明式（5）成立。

證明 ?gλi·gZqi mod p

=gλi+Ziq mod p

=δi

等式（5）成立，則節(jié)點Pi發(fā)送的信息正確，Pi可信。

定理2 節(jié)點Pj收到其他n-1個節(jié)點發(fā)來的秘密份額Xij后，驗證其正確性，即證明式（6）成立。

證明 由式（2）、（3）和（4）

（（gXij mod p）（（μij）dj mod p）） mod p=

（（gXij mod p）（gθij）dj mod p） mod p

=

（（gXij mod p）（gλi+Ziq-Xijdj mod p）dj mod p） mod p=

（（gXij mod p）（gλi+Ziq-Xij） mod p） mod p=

（gXij+λi+Ziq-Xij mod p） mod p=gλi+Ziq mod p=δi

原式得證，等式（6）成立，則證明Pj收到的秘密份額正確，其他節(jié)點可信。

定理3 由t個部分簽名合成的最終簽名，需由驗證式（10）驗證其是否合法簽名，即證明等式（10）成立。

證明 由式（1）和式（7），節(jié)點私鑰：

Kj =∑ni=1Xij mod dj=∑ni=1λi+Ziq mod dj; j=1，2，…，n

令

Q =∑ni=1λi+Ziq（12）

則

Kj=Q mod dj; j=1，2，…，n（13）

根據(jù)中國剩余定理，解如下同余方程組：

K1≡Q mod d1

K2≡Q mod d2

Kt≡Q mod dt

可得唯一解：

Q=∑ti=1Ddi eiKi mod D（14）

由（13）和（14）式可得，

Kj=∑ti=1Ddi eiKi mod D mod dj

令：

Hi ?= Ddi ?ei Ki mod D

則：

Q=∑ti=1Hi mod D

當(dāng)t>2時，根據(jù)文獻(xiàn)[22]可知：

s·l·∑ti=1hi+Q

由式（8）和（9）：

W=∑ti=1Wi mod D mod q

=

[∑ti=1（l·hi·s+Q） mod D]mod q=

（l·s·∑ti=1hi+Q）mod q

由式（12）：

Q=∑ni=1λi+Ziq=∑ni=1λi mod q

因此：

W=l·s·∑ti=1hi+∑ni=1λi mod q

則有：

gW≡gl·s·∑ti=1hi+∑ni=1λi mod q

≡gl·s·∑ti=1hi·g∑ni=1λi mod p

≡

ls·l·ψ mod p

如果節(jié)點Pi提供真實的秘密份額，則兩個等式（5）、（6）一定成立;反之如果驗證結(jié)果表明等式不成立，則說明節(jié)點沒有提供真實的秘密份額。

證明結(jié)果顯示等式成立，故節(jié)點私鑰Kj產(chǎn)生的簽名（s，l，W）有效。

定理4 由區(qū)塊鏈節(jié)點協(xié)助新加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的節(jié)點產(chǎn)生的新私鑰有效，即證明式（11）成立。

證明

Kn+1=（∑ti=1K′i mod D） mod dn+1=

{∑ti=1 [（Ddi eiKi mod D） mod dn+1+

εi-ε′idn+1] mod D}mod dn+1=

{[∑ti=1（Ddi eiKi mod D） mod dn+1+

∑ti=1εidn+1-∑ti=1ε′idn+1] mod D} mod dn+1=

{[∑ti=1（Ddi eiKi mod D） mod dn+1+

∑ti=1εidn+1-∑ti=1∑tj=1εijdn+1]? mod D} mod dn+1=

{∑ti=1（Ddi eiKi mod D） mod dn+1+

（∑ti=1εidn+1-∑ti=1εidn+1 ） mod D} mod dn+1=

∑ti=1（Ddi eiKi mod D） mod dn+1

由此可得，原節(jié)點私鑰Kj=∑ti=1Ddi eiXi mod D mod dj與新加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的節(jié)點的私鑰Kn+1同構(gòu)，可以構(gòu)成同余方程組且只有唯一解。因此，新加入節(jié)點私鑰有效。

3.2 安全性分析

3.2.1 簽名算法安全性分析

本文設(shè)計的適用于區(qū)塊鏈的（t，n）門限簽名算法，根據(jù)中國剩余定理，求解同余式方程組至少需要t個方程，少于t個方程無法求解，因此在合成簽名時需要至少t個節(jié)點協(xié)作才能生成簽名。攻擊者只有在一個周期T內(nèi)同時攻破t個及以上的節(jié)點，才能對投票結(jié)果造成影響。

假設(shè)某攻擊者想要竊取區(qū)塊鏈節(jié)點的私鑰，由于區(qū)塊鏈節(jié)點私鑰計算公式為：

Kj=∑ti=1Xij mod dj=∑ni=1λi+Ziq mod dj

則攻擊者需要計算：

Xij=（λi+Ziq）? mod dj

然而，由于λi和Zi由參與區(qū)塊鏈投票的節(jié)點秘密選取并保存，并沒有通過通信通道傳輸，攻擊者無法獲得。

攻擊者可能通過攔截得到廣播消息δi、θij、 μij，并可求得：

gXij=δi/μij

然而通過gXij求解Xij是離散對數(shù)難題，因此攻擊者無法求得Xij，因此無法通過Xij計算節(jié)點私鑰。另外，基于中國剩余定理的秘密分享，是基于大模數(shù)分解難題，這里 Kj=∑ti=1Ddi eiXi mod D mod dj，其中dj、D公開，要通過dj、D求解ei屬于大模數(shù)分解難題。因此攻擊者也無法通過此方案獲得區(qū)塊鏈節(jié)點私鑰。

組公鑰ψ=∏ni=1gλk mod p和組私鑰φ=∏nk=1λk由參與投票的區(qū)塊鏈節(jié)點相互協(xié)作產(chǎn)生。組公鑰ψ屬于公知信息，攻擊者可能知曉此信息。假設(shè)攻擊者想通過組公鑰ψ獲得組私鑰φ=∑nk=1λk，由組公鑰ψ=∏ni=1gλk mod p可知，通過gλk 求解λk屬于離散對數(shù)難題不可解。另外組私鑰是由組節(jié)點隨機(jī)選取的子秘密產(chǎn)生的，子秘密被各節(jié)點秘密保存，并通過通信通道傳送，攻擊者無法攔截獲得。而且方案中的簽名W由部分簽名Wi合成，整個簽名過程沒有使用組私鑰，組私鑰沒有暴露，因此攻擊者無法獲得組私鑰。

在簽名生成階段，參與投票的區(qū)塊鏈節(jié)點秘密選取的隨機(jī)數(shù)hi沒有通過通信信道傳輸，攻擊者無法獲得。攻擊者可能攔截到l，而l=g∑ti=1hi mod p，通過l求hi，需要計算g∑ti=1hi，而通過g∑ti=1hi求解hi仍然是求解離散對數(shù)難題，攻擊者無法獲得。

在簽名合成階段，區(qū)塊鏈節(jié)點需將各自的部分簽名（s，l，W）發(fā)送給簽名合成者， 部分簽名（s，l，W）不包含私鑰內(nèi)容，即使攻擊者竊取該內(nèi)容，也沒有任何價值，不會影響投票結(jié)果。

新節(jié)點加入?yún)^(qū)塊鏈網(wǎng)絡(luò)時，其私鑰由t個區(qū)塊鏈節(jié)點相互協(xié)作產(chǎn)生，εij是由區(qū)塊鏈節(jié)點隨機(jī)選取并保存，攻擊者無法獲得。假設(shè)某攻擊者通過惡意攻擊獲得了隨機(jī)數(shù)εij，想通過計算得到新加入節(jié)點的私鑰Kn+1，根據(jù)新加入節(jié)點的私鑰計算公式：

Kn+1=∑ti=1K′i mod D mod dn+1

攻擊者不可避免地要計算∑ti=1K′i mod D，則攻擊者必須先獲得K′i，而：

K′i=Ddi eiKi mod D mod dn+1+（εi-ε′i）dn+1

攻擊者必須計算Ki，即攻擊者必須獲得區(qū)塊鏈節(jié)點私鑰，然而根據(jù)之前的分析，攻擊者不可能獲得節(jié)點私鑰，因此攻擊者無法獲得新加入?yún)^(qū)塊鏈網(wǎng)絡(luò)節(jié)點的私鑰。

方案對區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點的離開具有免疫功能。假設(shè)有某節(jié)點Pk要離開區(qū)塊鏈網(wǎng)絡(luò)，因為Pk只知道自己的子秘密λk和個人私鑰Kk， 而組公鑰ψ=∏ni=1gλk mod p和組私鑰φ=∑nk=1λk均有區(qū)塊鏈節(jié)點協(xié)作產(chǎn)生，節(jié)點Pk僅有自己的秘密數(shù)和私鑰，并不能對組私鑰和其他節(jié)點私鑰產(chǎn)生任何威脅。且根據(jù)秘密共享門限簽名方案的原則，至少需要t個節(jié)點合作才能打開秘密。因此，少于t個節(jié)點的離開并不影響系統(tǒng)的安全性，該方案對于節(jié)點的離開不具有敏感性。

3.2.2 不可偽造性分析

不可偽造性是指任意惡意節(jié)點都不能偽造區(qū)塊鏈網(wǎng)絡(luò)中的合法節(jié)點生成簽名信息。

若有某惡意節(jié)點i想替代區(qū)塊鏈節(jié)點j產(chǎn)生秘密份額，則該惡意節(jié)點i隨機(jī)選取秘密數(shù)λi′和Zi′，由于λi′≠λi，Zi′≠Zi則λi′+Zi′q≠λi+Ziq，所以有X′ij≠Xij，其他節(jié)點收到惡意節(jié)點i的廣播信息λi′，Zi′，通過驗證很容易發(fā)現(xiàn)gλi′·gZi′q mod p≠gλi ·gZiq mod p≠δi，即等式不成立，其他節(jié)點不接受此節(jié)點的信息和簽名，因此節(jié)點i無法替代其他區(qū)塊鏈節(jié)點偽造λi，Zi。

假設(shè)惡意節(jié)點i想替代區(qū)塊鏈節(jié)點j生成區(qū)塊鏈節(jié)點私鑰，惡意節(jié)點可能截獲其他n-1個節(jié)點發(fā)送的信息Xij來構(gòu)造區(qū)塊鏈節(jié)點的私鑰。但是其他節(jié)點各自保留了Xii，攻擊者無法獲得。由Xii=（λi+Ziq） mod di，攻擊者可能通過截獲gλi、gZi試圖求得λi和Zi，從而計算Xii，但通過gλi、gZi求解λi和Zi是離散對數(shù)難題，攻擊者無法通過計算得到，因此攻擊者無法偽造區(qū)塊鏈節(jié)點私鑰。

若有惡意節(jié)點要偽造簽名信息，則攻擊者隨機(jī)選取hi′，計算li′、l′和部分簽名Wi′，合成者合成簽名W′但是在簽名驗證階段，由于W′≠W，所以gW′≠ls·l·ψ mod p，無法通過驗證，簽名無效，因此攻擊者無法偽造簽名。

3.3 效率分析

本文基于中國剩余定理的秘密共享方案，提出的適用于區(qū)塊鏈的（t，n）門限簽名算法，其計算難度等價于求解離散對數(shù)難題，與拉格朗日插值定理相比，具有較小的計算量。

為了與之前已有的簽名算法進(jìn)行比較，本文定義了如表1符號說明。

與模指數(shù)運算和模乘運算相比，模加法、模減法運算的計算量可忽略不計，因此本文只通過模指數(shù)和模乘運算來比較。

表2是本文方案與其他方案的計算復(fù)雜度對比結(jié)果。文獻(xiàn)[4]方案基于中國剩余定理，文獻(xiàn)[8]方案基于零知識證明協(xié)議，文獻(xiàn)[10]和[16]方案均基于拉格朗日插值多項式。

從表2可以看出，文獻(xiàn)[4]方案在算法上和本文效率相當(dāng)。在簽名生成階段，本文方案明顯優(yōu)于文獻(xiàn)[8]、[10]和[16]中的方案，這是由于文獻(xiàn)[10]和[16]方案是基于拉格朗日插值多項式的門限簽名算法，而多項式階數(shù)較高，計算復(fù)雜，所以導(dǎo)致執(zhí)行效率較低。

在簽名驗證階段，文獻(xiàn)[10]和[16]方案均優(yōu)于本文方案，但是區(qū)塊鏈?zhǔn)且环N異構(gòu)網(wǎng)絡(luò)，其計算資源相對有限，對算法的執(zhí)行效率要求較高。門限簽名算法的計算量主要在于簽名生成階段，不是驗證階段，因此提高簽名生成階段的效率比提高驗證階段的效率更為重要。

本文適用于區(qū)塊鏈電子投票場景的方案，設(shè)計了節(jié)點加入和退出機(jī)制;而文獻(xiàn)[8]、[10]和[16]方案均不支持節(jié)點加入和退出，文獻(xiàn)[4]方案建立了節(jié)點加入機(jī)制，但沒有設(shè)計節(jié)點退出算法，因此，以上方案均不能適配區(qū)塊鏈投票場景。

區(qū)塊鏈作為一個去中心化的應(yīng)用平臺，其參與節(jié)點集合處于動態(tài)變化之中，因此要求簽名算法不僅要去中心化，還需要允許節(jié)點自由加入和退出。與其他方案相比，本文設(shè)計的簽名算法能夠更好地適配到區(qū)塊鏈網(wǎng)絡(luò)投票場景。

4 結(jié)語

本文設(shè)計的門限簽名方案，擯棄了可信中心，參與區(qū)塊鏈投票的節(jié)點之間相互協(xié)作產(chǎn)生簽名，實現(xiàn)了節(jié)點之間實現(xiàn)相互驗證功能，除非大于t個節(jié)點合謀，否則無法獲得簽名信息。方案允許外部節(jié)點加入?yún)^(qū)塊鏈網(wǎng)絡(luò)參與投票，且保持組公鑰不變。在節(jié)點退出時，組公鑰發(fā)生變化，此時將前期組公鑰存放在區(qū)塊鏈網(wǎng)絡(luò)中，同時生成新的組公鑰，如需驗證前期簽名，可從區(qū)塊鏈網(wǎng)絡(luò)系統(tǒng)中調(diào)用組公鑰，解決了節(jié)點退出區(qū)塊鏈網(wǎng)絡(luò)時引起的組公鑰改變問題。另外，定期更新節(jié)點，避免了因移動攻擊造的成節(jié)點信息泄露問題，確保方案具有前向安全性。

本文提出的適用于區(qū)塊鏈投票場景的門限簽名方案，與其他方案相比，本方案基于中國剩余定理，計算簡單，效率較高。

參考文獻(xiàn)

[1]楊保華，陳昌.區(qū)塊鏈原理、設(shè)計與應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2017：9-19.（YANG B H， CHEN C. Blockchain Principle， Design and Application [M]. Beijing： China Machine Press， 2017：9-19.）

[2]SHAMIR A. How to share a secret [J]. Communications of the ACM， 1979， 22（11）： 612-613.

[3]張毅，侯整風(fēng)，胡東輝.一種動態(tài)的無可信中心（t，n）門限簽名認(rèn)證方案[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2011，34（9）：1341-1344.（ZHANG Y， HOU Z F， HU D H. A dynamic （t，n） threshold signature authentication scheme without a trusty party [J]. Journal of Hefei University of Technology （Natural Science Edition）， 2011， 34（9）： 1341-1344.）

[4]王斌，李建華.無可信中心的（t，n）門限簽名方案[J].計算機(jī)學(xué)報，2003，26（11）：1581-1584.（WANG B， LI J H. A （t，n） threshold signature scheme without a trusted party [J]. Chinese Journal of Computers， 2003，26（11）：1581-1584.）

[5]HARN L. Group-oriented （t，n） threshold digital signature scheme and digital multisignature [J]. IEEE Proceedings—Computers and Digital Techniques， 1994， 141（5）：307-313.

[6]何二慶， 侯整風(fēng)， 朱曉玲. 一種無可信中心動態(tài)秘密共享方案[J]. 計算機(jī)應(yīng)用研究， 2013，30（2）：491-493.（HE E Q， HOU Z F， ZHU X L. Proactive secret sharing scheme without trusted party [J]. Application Research of Computers， 2013 30（2）： 491-493.）

[7]殷鳳梅，濮光寧.允許新成員加入的無可信中心秘密共享方案分析[J].重慶科技學(xué)院學(xué)報（自然科學(xué)版），2011，13（6）：173-182.（YIN F M， PU G N. New member joining in a secret sharing scheme without a trusted party [J]. Journal of Chongqing University of Science and Technology （Natural Science Edition）， 2011，13（6）： 173-182.）

[8]徐甫.基于多項式秘密共享的前攝性門限RSA簽名方案[J]. 電子與信息學(xué)報， 2016， 38（9）：2280-2286.（XU F. Proactive threshold RSA signature scheme based on polynomial secret sharing[J]. Journal of Electronics & Information Technology， 2016， 38（9）：2280-2286.）

[9]ASMUTH C， BLOOM J. A modular approach to key safeguarding[J]. IEEE Transactions on Information Theory， 1983，29（2）：208-210.

[10]楊陽，朱曉玲，丁涼.基于中國剩余定理的無可信中心可驗證秘密共享研究[J].計算機(jī)工程，2015，41（2）：122-128.（YANG Y， ZHU X L， DING L. Research on verifiable secret sharing without trust center based on Chinese remainder theorem [J].Computer Engineering， 2015， 41（2）：122-128.）

[11]程宇，劉煥平.可驗證的Asmuth-Bloom門限秘密共享方案[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報，2011，27（3）：35-38.（CHENG Y， LIU H P. The Asmuth-Bloom verifiable threshold sharing scheme [J]. Natural Science Journal of Harbin Normal University， 2011， 27（3）：35-38.）

[12]王巖，侯整風(fēng)，章雪琪，等. 基于中國剩余定理的動態(tài)門限簽名方案[J]. 計算機(jī)應(yīng)用， 2018， 38（4）：1041-1045.（WANG Y， HOU Z F， ZHANG X Q， et al. Dynamic threshold signature scheme based on Chinese remainder theorem [J]. Journal of Computer Applications， 2018， 38（4）： 1041-1045.）

[13]徐甫，馬靜謹(jǐn).基于中國剩余定理的門限RSA簽名方案的改進(jìn)[J].電子與信息學(xué)報，2015，37（10）：2495-2500.（XU F， MA J J. Improvement of threshold RSA signature scheme based on Chinese remainder theorem [J]. Journal of Electronics & Information Technology， 2015，37（10）：2495-2500.）

[14]李潔平， 韋性佳. 基于中國剩余定理的秘密共享方案[J]. 通信技術(shù)，2018，51（3）：671-675.（LI J P， WEI X J. Secret sharing scheme based on Chinese remainder theorem [J]. Communications Technology， 2018， 51（3）： 671-675.）

[15]LI Q， WANG Z， NIU X， et al. A non-interactive modular verifiable secret sharing scheme [C]// Proceedings of the 2005 International Conference on Communications， Circuits and Systems. Piscataway， NJ： IEEE， 2005，1：84-87.

[16]KAYA K， SELCUK A A. A verifiable secret sharing scheme based on the Chinese remainder theorem [C]// Proceedings of the 2008 International Conference on Cryptology in India， LNCS 5365. Berlin： Springer， 2008： 414-425.

[17]董攀，況曉輝，盧錫城.一種秘密共享新個體加入?yún)f(xié)議[J]. 軟件學(xué)報，2005， 16（1）：116-120.（DONG P， KUANG X H， LU X C. A non-interactive protocol for member expansion in a secret sharing scheme[J]. Journal of Software， 2005， 16（1）：116-120.）

[18]曹陽.基于秘密共享的數(shù)字簽名方案[J].重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2015，27（3）：418-421.（CAO Y. Digital signature scheme based on secret sharing [J]. Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition）， 2015， 27（3）： 418-421.）

[19]王利朋，胡明生，賈志娟，等.基于中國剩余定理的區(qū)塊鏈投票場景簽名方案[J].計算機(jī)應(yīng)用研究， 2020， 37（2）：1-8.（WANG L P， HU M S， JIA Z J，et al. Signature scheme applying on blockchain voting scene based on Chinese remainder theorem [J]. Application Research of Computers， 2020， 37（2）：1-8.）

[20]BLAHUT R E.現(xiàn)代密碼學(xué)及其應(yīng)用[M].黃玉劃，薛明福，徐娟，譯.北京：機(jī)械工業(yè)出版社，2018：67-68.（BLAHUT R E. Cryptography and Secure Communication [M]. HUANG Y H， XUE M F， XU J， translated. Beijing： China Mechine Press， 2018： 67-68.

[21]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].3版.北京：高等教育出版社，2003：76-79.（MIN S H， YAN S J. Elementary Number Theory [M]. 3rd edition. Beijing： Higher Education Press， 2003： 76-79.）

[22]HOU Z， TAN M. A CRT-based （t，n） threshold signature scheme without a dealer [J]. Journal of Computational Information Systems， 2015，11（3）： 975-986.

This work is partially supported by the General Subject of the 13th Five-Year Plan for Education Science in Henan Province （（2018）-JKGHYB-0279）.

CHENG Yage， born in 1987， M. S.， assistant. Her research interests include cryptography， industrial Internet of things.

JIA Zhijuan， born in 1973， M. S.， professor. Her research interests include software engineering.

HU Mingsheng， born in 1973， Ph. D.， professor. His research interests include software engineering.

GONG Bei， born in 1984， Ph. D.， professor. His research interests include information security， trusted computing.

WANG Lipeng， born in 1987， M. S.， assistant. His research interests include virtualization security， cloud storage， parallel computing.