王婧，吳黎兵,，羅敏，何德彪

（1.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430070；2.武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430070）

1 引言

橢圓曲線數(shù)字簽名算法（ECDSA,elliptic curve digital signature algorithm）是橢圓曲線加密（ECC,elliptic curve cryptography）與數(shù)字簽名算法（DSA,digital signature algorithm）的結(jié)合，于1999 年成為美國國家標(biāo)準(zhǔn)學(xué)會（ANSI,America National Standards Institute）標(biāo)準(zhǔn)，并于2000 年成為電氣和電子工程師協(xié)會（IEEE,Institute of Electrical and Electronics Engineers）、美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST,National Institute of Standards and Technology）標(biāo)準(zhǔn)[1]。與DSA 和RSA（Rivest-Shamir-Adleman）相比，ECDSA 具有計(jì)算量小、處理速度快、存儲空間占用小、帶寬要求低等特點(diǎn)，適用于計(jì)算能力、存儲空間、帶寬與功耗受限的應(yīng)用場景。因此，ECDSA 被廣泛應(yīng)用于電子商務(wù)系統(tǒng)[2]和其他網(wǎng)絡(luò)領(lǐng)域，如安全傳輸層（TLS,transport layer security）協(xié)議[3]和域名系統(tǒng)安全擴(kuò)展（DNSSEC,domain name system security extension）協(xié)議[4]，用于提供身份認(rèn)證、數(shù)據(jù)完整性驗(yàn)證、不可否認(rèn)性等安全服務(wù)。隨著比特幣系統(tǒng)的成功部署與應(yīng)用，ECDSA 受到更廣泛的關(guān)注，并逐漸成為當(dāng)前主流區(qū)塊鏈平臺及項(xiàng)目的默認(rèn)簽名機(jī)制，如以太坊和Hyperledger Fabric。

眾所周知，數(shù)字簽名方案的安全性依賴于簽名者私鑰的安全性。在區(qū)塊鏈系統(tǒng)中，私鑰是用戶掌控其密碼貨幣的關(guān)鍵，也是實(shí)施隱私保護(hù)方案的基礎(chǔ)。用戶發(fā)布交易時(shí)，需要先使用簽名私鑰對交易進(jìn)行簽名，只有被共識節(jié)點(diǎn)驗(yàn)證通過的交易才能成功上鏈，實(shí)現(xiàn)密碼貨幣的轉(zhuǎn)移或信息發(fā)布。惡意攻擊者一旦非法竊取了區(qū)塊鏈用戶的簽名私鑰，就可以任意轉(zhuǎn)移該用戶的密碼貨幣或冒充該用戶發(fā)布非法交易信息。近年來，密碼貨幣被盜事件頻發(fā)，造成嚴(yán)重的經(jīng)濟(jì)損失[5-6]。與傳統(tǒng)銀行電子交易系統(tǒng)不同，一旦區(qū)塊鏈密碼貨幣被轉(zhuǎn)移，就無法追回。即使用戶已知私鑰被濫用，成功上鏈的交易也無法撤回。2019 年2 月，加拿某平臺誤將102 枚比特幣發(fā)送到私鑰僅被已去世的首席執(zhí)行官所知的冷錢包，導(dǎo)致這些比特幣被永久鎖死[7]。因此，防止私鑰泄露并避免簽名權(quán)利過度集中是當(dāng)前基于簽名技術(shù)的網(wǎng)絡(luò)交易系統(tǒng)和區(qū)塊鏈系統(tǒng)亟待解決的問題。

為了解決這一問題，常見的解決方法有多重簽名、基于Shamir 秘密共享的(t,n)?門限簽名和基于安全兩方/多方計(jì)算的簽名。其中，多重簽名通常發(fā)生在區(qū)塊鏈上，區(qū)塊鏈需要引入一種對多重簽名進(jìn)行編碼的方法，并對區(qū)塊鏈進(jìn)行重塑以完成基于多重簽名交易的發(fā)布與驗(yàn)證，現(xiàn)有區(qū)塊鏈難以支持這種技術(shù)。此外，不同簽名者在區(qū)塊鏈上進(jìn)行多次簽名，訪問結(jié)構(gòu)（簽名者的身份、數(shù)量）容易暴露在區(qū)塊鏈上，從而可能導(dǎo)致用戶隱私泄露，且簽名長度隨簽名者數(shù)量呈線性增長，簽名驗(yàn)簽時(shí)需要多個(gè)公鑰參與驗(yàn)證，開銷較高[8]?；赟hamir 秘密共享的(t,n)?門限簽名往往需要借助一個(gè)可信中心為預(yù)先選定的簽名群體分發(fā)私鑰份額，并且需要至少t個(gè)簽名方重構(gòu)出完整的私鑰才能完成簽名。在實(shí)際情況下，頒發(fā)私鑰的中心和簽名時(shí)重構(gòu)的私鑰持有者便成為系統(tǒng)的安全瓶頸[9]?；诎踩珒煞?多方計(jì)算的簽名可在區(qū)塊鏈下實(shí)施，不需要在鏈上執(zhí)行所有過程，而且兩方/多方計(jì)算簽名中簽名者信息被折疊成常規(guī)的區(qū)塊鏈交易格式，因而能夠兼容現(xiàn)有區(qū)塊鏈系統(tǒng)并降低開銷，并在一定程度上保證用戶隱私。

MacKenzie 等[10]首次提出了針對DSA 的兩方協(xié)同簽名方案，可以使2 個(gè)簽名參與方對給定的公鑰生成有效的DSA 簽名，而任何一方都不能單獨(dú)完成簽名，簽名過程中不需要重構(gòu)私鑰。Gennaro等[11]針對比特幣錢包安全提出了一種基于門限加法同態(tài)加密技術(shù)的(t,n)?門限D(zhuǎn)SA/ECDSA 簽名方案，并在惡意模型下證明了其安全性。Boneh 等[12]對文獻(xiàn)[11]方案進(jìn)行了性能優(yōu)化，提出了基于level-1 全同態(tài)加密的門限D(zhuǎn)SA/ECDSA 簽名方案。然而，這些方案均使用了分布式同態(tài)加密密鑰生成技術(shù)，簽名參與方的通信開銷和計(jì)算開銷都非常高，難以實(shí)際應(yīng)用于處理能力受限的比特幣錢包服務(wù)或計(jì)算能力受限的區(qū)塊鏈客戶端。

Lindell[13]提出了基于Paillier 同態(tài)加密算法的兩方協(xié)同ECDSA 簽名方案，與上述方案不同的是，該方案不需要執(zhí)行分布式Paillier 密鑰算法，直接利用Paillier 同態(tài)屬性即可完成兩方協(xié)同簽名，提高了兩方協(xié)同簽名的運(yùn)行效率。為了滿足用戶對安全的差異性需求，Doerner 等[14]提出了基于秘密共享和不經(jīng)意傳輸技術(shù)的(2,n)?門限ECDSA 簽名方案，該方案不需要引入計(jì)算開銷較高的Paillier 同態(tài)加密及其相關(guān)的零知識證明，從而大大提高了協(xié)同簽名的計(jì)算性能。但是Doerner 方案引入了不經(jīng)意傳輸協(xié)議[15-16]，與Lindell 方案[13]相比，增加了近千倍的通信開銷，且不能應(yīng)用于帶寬受限的區(qū)塊鏈客戶端。Castagnos 等[17]使用哈希證明系統(tǒng)技術(shù)代替Lindell 方案[13]中的Paillier 同態(tài)加密技術(shù)，設(shè)計(jì)了一種新的兩方協(xié)同ECDSA 簽名方案，進(jìn)而完善了Lindell 方案[13]的安全性證明。然而，對于128 bit安全的ECDSA 簽名方案，Castagnos 方案[17]的運(yùn)行效率比Lindell 方案[13]更低。

除兩方協(xié)同的ECDSA 簽名方案之外，多方門限ECDSA 簽名方案也陸續(xù)被提出。Lindell 等[18]設(shè)計(jì)了一種安全隱私乘法協(xié)議，用于將原始的兩方協(xié)同簽名方案擴(kuò)展成多方門限簽名方案。Doerner 等[19]同樣將Lindell[13]原始的兩方門限ECDSA 簽名方案擴(kuò)展成了多方門限ECDSA 簽名方案。Gennaro 等[20]設(shè)計(jì)了一種基于Paillier 同態(tài)加密的MtA 協(xié)議，該協(xié)議可以將基于乘法的共享份額轉(zhuǎn)換為基于加法的共享份額，進(jìn)而基于該協(xié)議提出一種新的多方門限ECDSA 協(xié)同簽名方案。但是，這些方案仍然沿用了兩方協(xié)同簽名方案中所使用的同態(tài)加密算法或不經(jīng)意傳輸協(xié)議，因而計(jì)算開銷和通信開銷非常高。

除ECDSA 之外，國內(nèi)外學(xué)者還提出了對其他密碼算法的私鑰保護(hù)安全解決方案。針對基于身份的數(shù)字簽名，He 等[21]和Feng 等[22]分別提出針對IEEE P1363 標(biāo)準(zhǔn)的兩方協(xié)同簽名方案和多方協(xié)同簽名方案。侯紅霞等[9]針對我國商用密碼算法SM2，結(jié)合Lindell 方案[13]的思想設(shè)計(jì)了一種兩方協(xié)同SM2 簽名方案。Zhang 等[23]同樣基于Paillier 同態(tài)加密算法，設(shè)計(jì)了一種新的兩方協(xié)同SM2 簽名方案。Mu 等[24]針對我國商用密碼算法SM9，設(shè)計(jì)了基于Paillier 的兩方協(xié)同SM9 簽名方案。然而，這些方案一方面計(jì)算開銷或通信開銷較高，難以適用于計(jì)算能力或帶寬受限的客戶端；另一方面，難以兼容現(xiàn)有的區(qū)塊鏈系統(tǒng)。

因此，為了提高協(xié)同簽名的運(yùn)行效率、降低簽名過程的通信開銷、保證簽名私鑰安全并兼容當(dāng)前區(qū)塊鏈系統(tǒng)，對兩方/多方協(xié)同ECDSA 簽名方案進(jìn)行進(jìn)一步研究具有非常重要的理論意義和現(xiàn)實(shí)意義。針對這一目標(biāo)，并考慮到兩方簽名對客戶端的友好性與便捷性，本文設(shè)計(jì)了一種新的安全高效兩方協(xié)同ECDSA 簽名方案。本文的主要貢獻(xiàn)可分為以下3 個(gè)方面。

1)設(shè)計(jì)了一種安全高效的兩方協(xié)同ECDSA 簽名方案，通過預(yù)計(jì)算Beaver 三元組[25]，避免使用計(jì)算開銷高昂的Paillier 同態(tài)加密和通信開銷高昂的不經(jīng)意傳輸技術(shù)，2 個(gè)參與方在不暴露各自私鑰的情況下共同完成簽名。

2)對本文所提方案提供了完整的安全性證明，結(jié)果表明，所提方案在不同時(shí)腐化2 個(gè)簽名方的情況下能夠有效保護(hù)ECDSA 簽名私鑰。

3)從理論分析和模擬驗(yàn)證2 個(gè)方面對本文所提方案進(jìn)行了評估，并與2 個(gè)相關(guān)的兩方協(xié)同簽名進(jìn)行了比較，結(jié)果表明，本文所提方案在計(jì)算開銷和通信開銷上都具有明顯優(yōu)勢。

2 預(yù)備知識

2.1 ECDSA 數(shù)字簽名算法

系統(tǒng)建立輸入安全參數(shù)，輸出算法公開參數(shù)param={E,G,P,p,q,h}，其中，E為定義在有限域Fp上的橢圓曲線，p為一個(gè)素?cái)?shù)，G為橢圓曲線上所有整數(shù)點(diǎn)構(gòu)成的加法群，P和q分別為群G的生成元和素?cái)?shù)階，h為輸入映射到域的雜湊函數(shù)，即域由整數(shù)集合{1,2,…,q?1}構(gòu)成。

密鑰生成輸入算法公開參數(shù)param，輸出簽名私鑰d和驗(yàn)證公鑰Q，其中d∈為隨機(jī)秘密值，公鑰Q=dP可公開發(fā)布。

簽名生成輸入算法公開參數(shù)param、用戶私鑰d和待簽名消息m，輸出簽名σ=(r,s)。具體步驟如下。

1)選擇一個(gè)隨機(jī)數(shù)k∈，計(jì)算R=k?P=(rx,ry)，其中rx和ry分別為橢圓曲線上點(diǎn)R的橫坐標(biāo)和縱坐標(biāo)。

2)計(jì)算r=rxmodq，若r=0，則返回步驟1)；否則，執(zhí)行步驟3)。

3)計(jì)算s′=k?1(e+dr)modq，其中，e=h(m)為消息摘要。

4)輸出簽名信息σ=(r,s)，其中s=min{s′,q?s′}，min{}函數(shù)表示取集合中較小的數(shù)值。

簽名驗(yàn)證輸入待驗(yàn)證的消息m和簽名σ，輸出驗(yàn)證結(jié)果“1”或“0”。具體步驟如下。

1)解析簽名σ獲得(r,s)，計(jì)算摘要e=h(m)。

2)計(jì)算Rv=s?1(eP+rQ)=(xv,yv)。

3)若r=xvmodq，輸出1；否則輸出0。

2.2 Beaver 三元組乘法技術(shù)

Beaver 三元組乘法技術(shù)由Beaver[25]于1991 年首次提出，通過完全隨機(jī)地設(shè)置電路中每個(gè)門的輸入，然后進(jìn)行校正的方法實(shí)現(xiàn)安全多方乘法計(jì)算。該方法避免了標(biāo)準(zhǔn)的安全兩方或多方乘法協(xié)議中涉及的零知識證明或進(jìn)一步秘密值共享等操作/協(xié)議，只需要進(jìn)行簡單的消息隨機(jī)秘密值廣播和重構(gòu)即可實(shí)現(xiàn)安全兩方或多方乘法計(jì)算。為了簡便，本文將在后續(xù)描述中省略整數(shù)運(yùn)算涉及的“modq”符號。

假設(shè)參與方U1和參與方U2已分別存有各自的秘密共享份額{ai,bi,Δai,Δbi,Δci}，i∈{1,2}，其中Δai和Δbi是完全隨機(jī)的整數(shù)，整數(shù)Δc1和Δc2滿足條件Δc1+Δc2=(Δa1+Δa2)(Δb1+Δb2)，U1和U2的目標(biāo)為安全計(jì)算c=c1+c2=(a1+a2)(b1+b2)?；贐eaver 三元組的安全兩方乘法協(xié)議步驟如下。

U1先分別計(jì)算其盲化數(shù)據(jù)u1=a1?Δa1和，再發(fā)送(u1,v1)給U2。U2先分別計(jì)算其盲化數(shù)據(jù)u2=a2?Δa2和v2=b2?Δb2，再發(fā)送(u2,v2)給U1。

U1進(jìn)而可計(jì)算中間數(shù)據(jù)u=u1+u2、v=v1+v2和c1=Δc1+Δa1v+Δb1u。U2同理可計(jì)算中間數(shù)據(jù)u=u1+u2、v=v1+v2和c2=Δc2+Δa2v+Δb2u+uv。

最后，U1和U2交換各自的信息c1和c2，從而兩方均可計(jì)算結(jié)果c=c1+c2=(a1+a2)(b1+b2)。

正確性令c=c1+c2，a=a1+a2，b=b1+b2，Δc=Δc1+Δc2，Δa=Δa1+Δa2，Δb=Δb1+Δb2，則u=a?Δa，v=b?Δb，進(jìn)一步地，通過以上步驟可得

因此，利用Beaver 三元組可以進(jìn)行兩方乘法計(jì)算。

安全性文獻(xiàn)[25]指出{Δai,Δbi}是隨機(jī)選取的，且每組數(shù)據(jù)僅使用一次，相當(dāng)于獨(dú)立且均勻分布的一次一密隨機(jī)值，允許通信方在公開信道上發(fā)送具有完全隱私性的任意消息。此外，Beaver 分別證明了該方法在消息被篡改（詳見文獻(xiàn)[25]的安全性證明引理4 和引理6）和參與方被腐化（詳見文獻(xiàn)[25]的引理5 和引理7）情況下的安全性。因此，本文認(rèn)為該方案在不需要引入承諾與零知識證明等額外密碼原語的情況下，滿足半誠實(shí)模型和惡意模型下的安全性。

一次性表Beaver[25]提出了一次性表的概念，用以描述一系列支持安全兩方或多方計(jì)算的三元組對集合，如SETtri={(Δa1i,Δb1i,Δc1i),(Δa2i,Δb2i,Δc2i)}，其中i={1,2,…,N}，N表示集合大小。其中U1將獲得大小為N的三元組集合 SETt1ri=，對稱地，U2將獲得大小為N的三元組集合此外，為了提高計(jì)算效率與安全性，Beaver 建議通過離線預(yù)計(jì)算的方式來獲取 SETtri。

安全離線預(yù)計(jì)算協(xié)議Fp re在三元組構(gòu)造過程中，(Δa1,Δb1)和(Δa2,Δb2)分別由U1和U2隨機(jī)選取，然后通過交互計(jì)算得到c1和c2，可以觀察到

其中，Δa1Δb1和Δa2Δb2可分別由U1和U2本地計(jì)算，因此構(gòu)建三元組的難點(diǎn)在于如何計(jì)算Δa1Δb2和Δa2Δb1。Feng 等[26]基于現(xiàn)有成果列舉了3 種生成Beaver 三元組的安全預(yù)計(jì)算方法。①首先基于加法同態(tài)加密技術(shù)構(gòu)造一個(gè)乘法共享轉(zhuǎn)加法共享的協(xié)議，再基于此計(jì)算Δa1Δb2和Δa2Δb1。以基于Paillier同態(tài)加密的方法為例：U1首先生成Paillier 的公私鑰對(sk,pk)，計(jì)算密文x1=Encpk(Δa1)，將x1和公鑰pk 發(fā)送給U2；U2收到消息后選取一個(gè)隨機(jī)數(shù)η，計(jì)算密文，再將密文x2發(fā)送給U1；U1可解密獲得y1=Δa1Δb2?η；類似地，重復(fù)上述步驟，U1可獲得y1′=Δa2Δb1?η′，進(jìn)而可以計(jì)算出Δc1=Δa1Δb1+y1+y1′；U2根據(jù)計(jì)算過程中選取的隨機(jī)數(shù)可計(jì)算Δc2=Δa2Δb2+η+η′。該方法首次在文獻(xiàn)[20]中被應(yīng)用，并且其安全性也得到了證明。②與第一種方法類似，先計(jì)算Δa1Δb2和Δa2Δb1，再計(jì)算Δc1和Δc2，不同點(diǎn)在于用不經(jīng)意傳輸協(xié)議代替加法同態(tài)加密技術(shù)以節(jié)約計(jì)算開銷，具體實(shí)施方案可參考文獻(xiàn)[14]。③基于可信第三方頒發(fā)有效的Beaver 三元組，如利用一個(gè)可信的服務(wù)器為U1和U2生成匹配的三元組，該方法在文獻(xiàn)[27]中被應(yīng)用。后文為了簡便，令 Fpre表示安全的三元組離線預(yù)計(jì)算協(xié)議。

3 安全模型和設(shè)計(jì)目標(biāo)

3.1 安全性定義

本節(jié)主要描述數(shù)字簽名方案與兩方協(xié)同數(shù)字簽名方案的安全性定義。

1)標(biāo)準(zhǔn)數(shù)字簽名安全性定義

與文獻(xiàn)[13]類似，出于完整性和參考性目的，本文首先針對標(biāo)準(zhǔn)數(shù)字簽名方案π=(Gen,Sign,Verify)給出一個(gè)基于游戲的安全性定義。游戲GameSignA,π(1λ)中共2 個(gè)角色，即概率多項(xiàng)式時(shí)間（PPT,probabilistic polynomial time）敵手A 和模擬器C。其中，C 為PPT 敵手A 提供方案相關(guān)的公開參數(shù)，包括簽名驗(yàn)證公鑰Q，同時(shí)提供對A 的簽名查詢應(yīng)答；PPT 敵手A 的目標(biāo)是在進(jìn)行若干消息?簽名對查詢后，偽造消息m*的簽名σ*；若偽造成功，則游戲輸出“1”，否則游戲輸出“0”。A 和C 的游戲流程如算法1 所示。

算法1標(biāo)準(zhǔn)數(shù)字簽名

游戲1GameSignA,π(1λ)

①(d,Q)←Gen(1λ)

② A 將消息m∈{01}*發(fā)送給C 進(jìn)行簽名詢問CSignd(?)，C 返回m的合法簽名σ；/*該步驟執(zhí)行次數(shù)在多項(xiàng)式范圍內(nèi)，所有查詢過的消息m構(gòu)成集合Ω*/

③(m*,σ*)←ASignd(?)(1λ,Q)；/*敵手A 進(jìn)行簽名偽造*/

④ 當(dāng)且僅當(dāng) Verify(m*,σ*)=1 且m*?Ω時(shí)，游戲輸出“1”；否則游戲輸出“0”

定義1如果對于任意的PPT 敵手A，在游戲1中輸出“1”的概率是可忽略的，即

其中，ε為一個(gè)可忽略概率閾值，λ為簽名方案π的安全參數(shù)，則認(rèn)為簽名方案π滿足選擇消息攻擊下的存在不可偽造性安全（EU-CMA,existential unforgeability against chosen-message attack）。

2)兩方協(xié)同簽名安全性定義

兩方協(xié)同簽名可視為標(biāo)準(zhǔn)數(shù)字簽名的一種分布式表現(xiàn)形式，其輸出的簽名仍能通過算法Verify的驗(yàn)證，因此，本文采用類似于簽名方案π的方式定義π衍生的兩方協(xié)同簽名方案Π=(DistGen,DistSign,Verify)的安全性。

與標(biāo)準(zhǔn)數(shù)字簽名安全定義不同的是，本文假設(shè)PPT 敵手A 可以控制其中一個(gè)簽名參與方Ui(i∈{1,2})，并且知道Ui的所有秘密值。因此，A和被腐化的Ui被認(rèn)為是一體的，在后續(xù)描述中稱Ui為腐化方或直接用A 代替Ui來描述游戲模擬過程。在模擬過程中，A 選擇要簽名的任意信息，與誠實(shí)參與方Uj(j≠i)進(jìn)行交互生成簽名。同時(shí)，A可以選擇遵循協(xié)議設(shè)置或任意偏離協(xié)議設(shè)置，即敵手是惡意的。此外，敵手A 是靜態(tài)的，即在協(xié)議初始化之前，敵手A 便確定被控制的參與方為Ui，且在一個(gè)游戲結(jié)束之前不會轉(zhuǎn)換為參與方Uj。

算法2兩方協(xié)同數(shù)字簽名

游戲2GameDistSignA,Π(1λ)

①Q(mào)←Πi(1λ)；/*誠實(shí)參與方輸出簽名驗(yàn)證公鑰，Ui被敵手控制*/

② A 選擇m∈{01}*作為待簽名的消息，與Πi(.)進(jìn)行交互輸出簽名σ；/*該步驟執(zhí)行次數(shù)在多項(xiàng)式范圍內(nèi)，所有査詢過的消息m構(gòu)成集合Ω*/

④ 當(dāng)且僅當(dāng)Verify(m*,σ*)=1 且m*?Ω時(shí)，游戲輸出“1”；否則游戲輸出“0”

定義2如果對于任意的PPT 敵手A 以及被A 腐化的任意參與方Ui(i∈{1,2})，在游戲2 中輸出“1”的概率是可忽略的，即

其中，ε為一個(gè)可忽略概率閾值，則認(rèn)為簽名方案Π滿足選擇消息攻擊下的存在不可偽造性安全。

3.2 安全模型

通用可組合（UC,universally composable）安全是由Canetti[28]提出的一種根據(jù)協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境和協(xié)議理想執(zhí)行環(huán)境不可區(qū)分方法來定義密碼協(xié)議安全性的框架。該框架的顯著特點(diǎn)是：當(dāng)一個(gè)組合協(xié)議的各個(gè)子協(xié)議被證明是UC 安全的，那么該組合協(xié)議是安全的。因此，可以模塊化地選取或設(shè)計(jì)可證明安全的子協(xié)議，進(jìn)而運(yùn)用組合原理構(gòu)造更復(fù)雜的安全密碼協(xié)議。

在UC 框架下，理想函數(shù)F 是重要的組成部分，代表一個(gè)不可腐化的可信方，用于完成協(xié)議所需的理想功能與執(zhí)行過程。PPT 敵手A 與協(xié)議參與方的交互用于模擬協(xié)議的現(xiàn)實(shí)執(zhí)行過程，即協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境。協(xié)議參與方（包括可視為理想敵手的模擬器C ）與理想函數(shù)的交互用于模擬協(xié)議的理想執(zhí)行過程，即協(xié)議理想執(zhí)行環(huán)境。本文提出的兩方協(xié)同ECDSA簽名方案是基于理想函數(shù)和組合的混合模型構(gòu)造的。同時(shí)，本文方案的安全性也是基于此模型進(jìn)行證明的。其中，分布式密鑰生成模擬只需執(zhí)行一次，兩方協(xié)同簽名模擬可執(zhí)行多項(xiàng)式次數(shù)。值得注意的是，如果承諾與零知識證明協(xié)議是UC 安全的，那么在混合模型下協(xié)議模擬執(zhí)行的輸出和協(xié)議現(xiàn)實(shí)執(zhí)行的輸出在計(jì)算上是不可區(qū)分的。接下來，本文將對這幾個(gè)理想函數(shù)進(jìn)行簡單介紹。

1)承諾理想函數(shù) Fcom

在隨機(jī)預(yù)言機(jī)模型下，F(xiàn)com可通過簡單地定義函數(shù)Com(x)=h(x,r)←{0,1}λ來實(shí)現(xiàn)靜態(tài)安全，且任意滿足通用可組合安全的承諾函數(shù)h都滿足 Fcom的形式化定義[13]，具體流程如下。

①當(dāng)收到參與方Ui的消息(commit,sid,x)后，如果已經(jīng)存儲會話序號 sid 相關(guān)的承諾消息(commit,sid,?)，則忽略此消息；否則，記錄消息(sid,i,x)，并且將(receipt,sid)發(fā)送給參與方Uj。

② 當(dāng)收到參與方Ui的消息(decommit,sid)后，如果已經(jīng)存儲消息(sid,i,x)，則將消息(decommit,sid,x)發(fā)送給參與方Uj。

根據(jù)文獻(xiàn)[13,18]可知，標(biāo)準(zhǔn)零知識理想函數(shù)可形式化定義為

其中，str 表示空字符串，R 表示秘密信息x和證據(jù)ω之間的關(guān)系。在安全兩方計(jì)算場景下，非交互式零知識證明理想函數(shù)與2 個(gè)參與方Ui、Uj的形式化交互流程如下。

當(dāng)收到參與方Ui的消息(prove,sid,x,ω)后，如果會話序號sid 已被使用過或秘密信息x和證據(jù)ω之間不滿足關(guān)系R，即(x,ω)?R，則忽略本次的消息；否則，將(proof,sid,x)發(fā)送給參與方Uj。

①當(dāng)收到參與方Ui的消息(com-prove,sid,x,ω)后，如果會話序號 sid 已被使用過或(x,ω)?R，則忽略本次的消息；否則，將(proofreceive,sid)發(fā)送給參與方Uj。

② 當(dāng)收到參與方Ui的消息(decom-proof,sid)后，如果已存儲了(sid,i,x)，則將(decom-proof,sid,x)發(fā)送給參與方Uj。

在本文的方案設(shè)計(jì)中，R 為橢圓曲線上的離散對數(shù)關(guān)系，定義為RDL={(G,P,q,Q,x)|Q=xP}。對于關(guān)系RDL的零知識證明，本文可以采用經(jīng)典的Schnorr 證明[29]來實(shí)現(xiàn)。

3.3 設(shè)計(jì)目標(biāo)

本文提出的兩方協(xié)同ECDSA 簽名方案應(yīng)滿足以下4 個(gè)屬性。

①隱私性。除協(xié)議的計(jì)算輸出和協(xié)議本身所泄露的內(nèi)容外，2 個(gè)簽名參與方中的任何一方都不能從協(xié)議執(zhí)行過程中獲取其他任何信息，包括另一方的私有輸入。

② 正確性。2 個(gè)簽名參與方誠實(shí)地執(zhí)行該協(xié)議時(shí)，協(xié)議輸出合法的ECDSA 簽名。

③兼容性。協(xié)議輸出的正確簽名仍能通過原簽名方案驗(yàn)證算法的檢測，即使用2.1 節(jié)描述的簽名驗(yàn)證算法時(shí)，簽名驗(yàn)證結(jié)果為“1”。

④ 高效性。充分考慮參與方的計(jì)算能力以及協(xié)同簽名過程中的在線時(shí)延，簽名過程應(yīng)保證計(jì)算開銷和通信開銷盡可能小。

4 方案設(shè)計(jì)

本文提出的兩方協(xié)同ECDSA 簽名方案共包括4 個(gè)階段，分別為系統(tǒng)建立、分布式密鑰生成、兩方協(xié)同簽名和簽名驗(yàn)證。系統(tǒng)建立和簽名驗(yàn)證與2.1節(jié)中的描述一致，因此本節(jié)不再重復(fù)描述。分布式密鑰生成和兩方協(xié)同簽名協(xié)議由2 個(gè)簽名參與方U1和U2協(xié)同完成，其中分布式密鑰生成算法只需運(yùn)行一次，兩方協(xié)同簽名算法可運(yùn)行多次。

在本文方案中，假設(shè)在運(yùn)行分布式密鑰生成和協(xié)同簽名協(xié)議之前，系統(tǒng)已執(zhí)行過（如第2.2 節(jié)所描述的）安全離線預(yù)計(jì)算協(xié)議 Fpre，并安全輸出了簽名參與方U1和U2所需的Beaver 三元組集合。換句話說，U1和U2在簽名之前已秘密保存了配對的三元組集合，從而降低了在線協(xié)同簽名的通信開銷與計(jì)算開銷。Beaver 三元組的離線預(yù)計(jì)算理念已在多個(gè)方案中被應(yīng)用，如文獻(xiàn)[26-27,30]。根據(jù)文獻(xiàn)[25]的定義，為了保證協(xié)議在UC 框架下的安全性，Beaver 三元組應(yīng)為一次一密隨機(jī)值。因此，本文可根據(jù)實(shí)際應(yīng)用場景需求，選擇定期執(zhí)行安全預(yù)計(jì)算協(xié)議來更新集合，以獲得足夠使用的三元組數(shù)量，或者一次性預(yù)計(jì)算出足夠多的三元組。下面，將具體介紹本文提出的兩方協(xié)同ECDSA 簽名方案的分布式密鑰生成協(xié)議與兩方協(xié)同簽名協(xié)議。

4.1 分布式密鑰生成

分布式密鑰生成協(xié)議由簽名參與方U1和U2共同完成，輸出簽名驗(yàn)證公鑰Q和各自的部分私鑰d1,d2。

1)U1→U2:{com(Q1,π1)}

①U1選取一個(gè)隨機(jī)數(shù)d1∈Zq*作為U1的部分私鑰，計(jì)算對應(yīng)的部分公鑰Q1=d1P。

②U1發(fā)送消息(com-prove,1,Q1,d1)給理想函數(shù)（即U1發(fā)送關(guān)于Q1及其離散對數(shù)的零知識證明π1的承諾com 給U2）。

2)U2→U1:{Q2,π2}

①當(dāng)U2接收到的消息(proof-receipt,1)后，U2選取一個(gè)隨機(jī)數(shù)作為U2的部分私鑰，計(jì)算對應(yīng)的部分公鑰Q2=d2P。

②U2發(fā)送消息(prove,2,Q2,d2)給理想函數(shù)（即U2發(fā)送Q2和關(guān)于Q2的離散對數(shù)零知識證明π2給U1）。

3)U1→U2:{Q1,π1}

當(dāng)U1接收到的消息(proof,2,Q2)后，U1驗(yàn)證proof 的有效性，若無效則協(xié)議終止；否則，打開承諾并發(fā)送消息(decom-proof,1)給（即U1發(fā)送Q1和關(guān)于Q1的離散對數(shù)零知識證明π1給U2）。

4)U1和U2輸出簽名驗(yàn)證公鑰Q，并安全存儲各自的隱私信息

①U1計(jì)算簽名驗(yàn)證公鑰，并安全存儲

② 當(dāng)U2接收到理想函數(shù)的消息(decom-proof,1,Q1)后，U2驗(yàn)證proof 的有效性，若無效則協(xié)議終止；否則，計(jì)算簽名驗(yàn)證公鑰Q=Q1+Q2，并安全存儲

4.2 兩方協(xié)同簽名

給定待簽名的消息m，兩方協(xié)同簽名協(xié)議必須由參與方U1和U2共同完成，輸出ECDSA 簽名σ=(r,s)。

1)U1→U2:{com(R1,π3)}

①U1選取一個(gè)隨機(jī)數(shù)，計(jì)算R1=k1P。

②U1發(fā)送消息(com-prove,sid||1,R1,k1)給理想函數(shù)（即U1發(fā)送關(guān)于R1及其離散對數(shù)的零知識證明π3的承諾com 給U2）。

2)U2→U1:{R2,π4}

①當(dāng)U2接 收 到的 消 息(proof-receipt,sid||1)后，U2選取一個(gè)隨機(jī)數(shù)，計(jì)算R2=k2P。

②U2發(fā)送消息(prove,sid||2,R2,k2)給理想函數(shù)（即U2發(fā)送R2和關(guān)于R2的離散對數(shù)零知識證明π4給U1）。

3)U1→U2:{R1,π3,(u1,v1,w1,t1)}

①當(dāng)U1接收到的消息(proof,sid||2,R2)后，U1驗(yàn)證proof 的有效性，若無效則協(xié)議終止；否則，打開承諾并發(fā)送消息(decom-proof,sid||1)給（即U1發(fā)送R1和關(guān)于R1的離散對數(shù)零知識證明π3給U2）。②U1依次計(jì)算R=R1+R2=(rx,ry)、r=rxmodq、，其中，e=h(m)，如果e為奇數(shù)，U1進(jìn)一步計(jì)算，令δ1=δ1+1。

③U1先選擇一個(gè)隨機(jī)數(shù)，再按順序選擇中前2 個(gè)三元組(Δa11,Δb11,Δc11)和(Δa12,Δb12,Δc12)，進(jìn)而分別計(jì)算數(shù)據(jù)u1=k1?Δa11、v1=ρ1?Δb11、w1=δ1?Δa12和t1=ρ1?Δb12。

④U1發(fā)送消息{u1,v1,w1,t1}給U2。

4)U2→U1:{(u2,v2,w2,t2),(α2,β2)}

①當(dāng)U2接收到理想函數(shù)的消息(decom-proof,sid||1,R1)后，U2驗(yàn)證proof 的有效性，若無效則協(xié)議終止；否則，依次計(jì)算R=R1+R2=(rx,ry)、r=rxmodq和消息雜湊值e=h(m)，并且計(jì)算

② 當(dāng)U2接收到U1的消息(u1,v1,w1,t1)后，U2先選擇一個(gè)隨機(jī)數(shù)，再按順序選擇中前2 個(gè)三元組(Δa21,Δb21,Δc21)和(Δa22,Δb22,Δc22)，進(jìn)而分別計(jì)算數(shù)據(jù)u2=k2?Δa21、v2=ρ2?Δb21、w2=δ2?Δa22和t2=ρ2?Δb22。

③U2先分別計(jì)算數(shù)據(jù)u=u1+u2、v=v1+v2、w=w1+w2、t=t1+t2，接著計(jì)算數(shù)據(jù)α2=k2v+ρ2u+Δc21、β2=δ2t+ρ2w+Δc22。

④U2刪除當(dāng)前中的三元組(Δa21,Δb21,Δc21)和(Δa22,Δb22,Δc22)，然后將消息{(u2,v2,w2,t2),(α2,β2)}發(fā)送給U1。

5)U1輸出簽名σ=(r,s)

①當(dāng)U1收到U2的消息{(u2,v2,w2,t2),(α2,β2)}后，U1先計(jì)算u=u1+u2、v=v1+v2、w=w1+w2、t=t1+t2、α1=k1v+ρ1u+Δc11?uv和β1=δ1t+ρ1w+Δc12?tw，然后刪除SETt1ri中的三元組(Δa11,Δb11,Δc11)和(Δa12,Δb12,Δc12)。

②U2計(jì) 算，令s=min{s′,q?s′}，輸出ECDSA 簽名σ=(r,s)

若應(yīng)用場景需要U2也輸出簽名，U1可將消息(α1,β1)給U2，則U2也可按照步驟5)計(jì)算獲得簽名σ=(r,s)。由于在Beaver 三元組乘法技術(shù)中，三元組必須遵循一次一密的原則才能滿足多方計(jì)算的完美隱私性，因此U1和U2在每次簽名之后刪除已使用的三元組，避免簽名過程中重復(fù)使用三元組。此外，當(dāng)應(yīng)用場景安全要求較低時(shí)，可刪除方案涉及的所有承諾協(xié)議和零知識證明協(xié)議，即構(gòu)成半誠實(shí)模型[31]下的安全兩方協(xié)同ECDSA 簽名方案，從而進(jìn)一步提高協(xié)同簽名的效率。

4.3 正確性分析

根據(jù)分布式密鑰生成算法可得，簽名驗(yàn)證公鑰為

根據(jù)兩方協(xié)同簽名算法可得

此外，同理于2.2 節(jié)中Beaver 三元組乘法技術(shù)的正確性分析，即式(1)，可得

由此可知，本文所提兩方協(xié)同ECDSA 簽名方案輸出的簽名(r,s)和簽名驗(yàn)證公鑰Q與2.1 節(jié)描述的ECDSA 公鑰簽名(r,s)和驗(yàn)簽公鑰Q一致。因此，本文所提方案滿足設(shè)計(jì)目標(biāo)要求的正確性和兼容性。

5 安全性證明

引理1假設(shè)ECDSA 簽名方案滿足EU-CMA安全性，那么本文所提兩方協(xié)同ECDSA 簽名方案滿足EU-CMA 安全性。

證明假設(shè)任意PPT 敵手A 在腐化任意一個(gè)協(xié)同簽名參與方Ui(i∈{1,2})的情況下，能夠以不可忽略的概率ε 在游戲中成功偽造消息?簽名對(m*,σ*=(r*,s*))，那么本文可以構(gòu)造一個(gè)模擬器C 作為游戲GameSignC,π(1λ)的概率多項(xiàng)式敵手，使C 能夠以與ε 幾乎相等的概率在GameSignC,π(1λ)中成功偽造消息?簽名對(m*,σ*=(r*,s*))。同理于文獻(xiàn)[13]，本文將考慮敵手腐化U1和敵手腐化U2這2 種情況，分別論述本文方案的安全性。其中，分布式密鑰生成協(xié)議僅需模擬一次，兩方協(xié)同簽名協(xié)議可進(jìn)行多次模擬。假設(shè)U1和U2在分布式密鑰生成前已通過安全方式獲得對應(yīng)的由于Beaver 三元組已被證明是安全的且滿足完美隱私性[25]，因此，為了滿足UC 框架的安全模擬規(guī)則（即參與方之間、參與方與敵手間不直接交互），本文在模擬過程中引入一個(gè)Beaver 三元組乘法理想函數(shù) FBT，用于接收/發(fā)送與Beaver 三元組直接相關(guān)的消息。

當(dāng)i=1時(shí)，PPT 敵手A 腐化參與方U1。本文構(gòu)造一個(gè)針對游戲的模擬器C，同時(shí)作為游戲GameSignC,π(1λ)的PPT 敵手。本質(zhì)上，C 在協(xié)議模擬過程產(chǎn)生一個(gè)令A(yù) 不可區(qū)分的執(zhí)行環(huán)境，然后利用A 在游戲中輸出的偽造簽名作為游戲GameSignC,π(1λ)的輸出，以此攻擊原始ECDSA 簽名方案。

1)分布式密鑰生成協(xié)議模擬

2)兩方協(xié)同簽名協(xié)議模擬

①在游戲GameSignC,π(1λ)中，C 向預(yù)言機(jī)FECDSA進(jìn)行簽名查詢，獲得σ=(r,s)，并根據(jù)簽名驗(yàn)證算法進(jìn)一步計(jì)算得到R。

不可區(qū)分性分析。在分布式密鑰生成模擬過程中，可以觀察到協(xié)同簽名協(xié)議的現(xiàn)實(shí)執(zhí)行環(huán)境與理想模擬執(zhí)行環(huán)境僅有一個(gè)區(qū)別。在協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境中，Q2是由誠實(shí)參與方U2選擇一個(gè)隨機(jī)數(shù)后計(jì)算Q2=d2P得來的；在協(xié)議模擬執(zhí)行環(huán)境中，C 計(jì)算Q2=Q?Q1=Q?d1P，其中公鑰Q是在游戲GameSignC,π(1λ)中查詢預(yù)言機(jī)獲取的。由于Q是隨機(jī)選取的，因此d2P和Q?d1P是同分布的。此外，若U2不退出協(xié)議模擬，敵手A 可在該協(xié)議模擬結(jié)束后輸出公鑰Q=Q1+Q2=Q1+(Q?Q1)，與在協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境中的輸出相同；現(xiàn)實(shí)執(zhí)行環(huán)境中的零知識證明與驗(yàn)證也同分布于()?混合模型。因此，在分布式密鑰生成協(xié)議模擬過程中，A對模擬執(zhí)行環(huán)境的視圖和對現(xiàn)實(shí)執(zhí)行環(huán)境中的視圖是不可區(qū)分的。

在兩方協(xié)同簽名模擬過程中，可以觀察到協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境與理想模擬執(zhí)行環(huán)境主要有2 個(gè)區(qū)別。一是計(jì)算R2的過程，同理于上述分析，對于A來說，模擬執(zhí)行過程中的R2=R?k1P和現(xiàn)實(shí)執(zhí)行過程中的R2=k2P是同分布且不可區(qū)分的。二是(u2,v2,w2,t2,α2,β2)的構(gòu)造，在協(xié)議模擬環(huán)境中，u2,v2,w2,t2,α2均是C 選取的隨機(jī)數(shù)，而β2是通過計(jì)算式β2=s(α1+α2)?β1獲得的；在現(xiàn)實(shí)執(zhí)行環(huán)境中，(u2,v2,w2,t2,α2,β2)是通過計(jì)算u2=k2?Δa21、v2=ρ2?Δb21、w2=δ2?Δa22、t2=ρ2?Δb22、α2=k2v+ρ2u+Δc21、β2=δ2t+ρ2w+Δc22獲得的。由于ρ2、Δa21、Δb21、Δa22、Δb22均為獨(dú)立分布的隨機(jī)數(shù)，故C 隨機(jī)選取的(u2,v2,w2,t2,α2)分別與現(xiàn)實(shí)執(zhí)行環(huán)境中誠實(shí)參與方U2計(jì)算的(k2?Δa21，ρ2?Δb21，δ2?Δa22，ρ2?Δb22，k2v+ρ2u+Δc21)同分布；又因?yàn)棣?和ρ2是隨機(jī)的，所以s(α1+α2)?β1與β2也是同分布的。此外，在模擬協(xié)議不終止的情況下，A 可在游戲中輸出當(dāng)前模擬實(shí)例的簽名r=rxmodq和s=(α1+α2)?1?[β1+(s(α1+α2)?β1)]，這與協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境中的輸出相同。因此，在U1被腐化時(shí)的兩方協(xié)同簽名協(xié)議模擬的過程中，A 對模擬執(zhí)行環(huán)境的視圖和對現(xiàn)實(shí)執(zhí)行環(huán)境的視圖是不可區(qū)分的。

簽名偽造。通過上述分析可知，在分布式密鑰生成模擬和兩方協(xié)同簽名模擬過程中，A 在腐化參與方U1時(shí)無法區(qū)分協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境和協(xié)議模擬執(zhí)行環(huán)境，故C 可以調(diào)用A 的偽造簽名攻擊原始ECDSA 方案。

由于在模擬過程中，A 生成的簽名驗(yàn)證公鑰Q是通過游戲GameSignC,π(1λ)中預(yù)言機(jī) FECDSA獲得的，故A 在游戲中的成功偽造(m*,σ*)也可作為C 在游戲GameSignC,π(1λ)中的成功偽造，即A 在游戲輸出一個(gè)偽造的消息簽名對(m*,σ*=(r*,s*))，C 可隨之在游戲GameSignC,π(1λ)中輸出(m*,σ*=(r*,s*))。

當(dāng)i=2時(shí)，PPT 敵手A 腐化參與方U2。類似地，本文構(gòu)造一個(gè)針對游戲GameSignC,π(1λ)的PPT敵手C，同時(shí)作為游戲的模擬器，能夠利用A 的偽造簽名攻擊原始ECDSA 簽名方案。

1)分布式密鑰生成協(xié)議模擬

①在游戲GameSignC,π(1λ)中，C 向預(yù)言機(jī)FECDSA進(jìn)行密鑰生成查詢，獲得(1λ,Q)。其中，λ為安全參數(shù)，Q為ECDSA 的簽名驗(yàn)證公鑰。

2)兩方協(xié)同簽名協(xié)議模擬

①在游戲GameSignC,π(1λ)中，C 向預(yù)言機(jī)FECDSA進(jìn)行簽名查詢，獲得σ=(r,s)，并根據(jù)簽名驗(yàn)證算法進(jìn)一步計(jì)算得到R。

④ 當(dāng)收到 A 發(fā)送給FBT的消息(sid,(u2,v2,w2,t2,α2,β2))后，C 驗(yàn)證A 的消息是否按照4.1 節(jié)中步驟4)計(jì)算所得，若不是，則終止協(xié)議，否則C 輸出σ=(r,s)。

不可區(qū)分性分析。在U2被腐化時(shí)的分布式密鑰生成模擬過程中，A 對模擬執(zhí)行環(huán)境的視圖和對現(xiàn)實(shí)執(zhí)行環(huán)境中的視圖是不可區(qū)分的，其原理與U1被腐化時(shí)相同，所以本文不再重復(fù)描述。

對于U2被腐化時(shí)的兩方協(xié)同簽名模擬過程，可以觀察到協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境與理想模擬執(zhí)行環(huán)境同樣有2 個(gè)區(qū)別。一是計(jì)算R2的過程，同理于上述分析，對于A 來說，模擬執(zhí)行過程中的R1=R?k2P和現(xiàn)實(shí)執(zhí)行過程中的R1=k1P是同分布且不可區(qū)分的。二是(u1,v1,w1,t1)的構(gòu)造，在協(xié)議理想模擬環(huán)境中，u1,v1,w1,t1均為C 選取的隨機(jī)數(shù)；在現(xiàn)實(shí)執(zhí)行環(huán)境中，(u1,v1,w1,t1)則通過計(jì)算u1=k1?Δa11、v1=ρ1?Δb11、w1=δ1?Δa12、t1=ρ1?Δb12獲得。由于ρ1、Δa11、Δb11和Δa12、Δb12均為獨(dú)立分布的隨機(jī)數(shù)，故C 隨機(jī)選取的(u1,v1,w1,t1)分別與現(xiàn)實(shí)執(zhí)行環(huán)境中誠實(shí)參與方U2計(jì)算的(k1?Δa11，ρ1?Δb11，δ1?Δa12，ρ1?Δb12)同分布。此外，在模擬協(xié)議不終止的情況下，C 可在游戲中輸出簽名σ=(r,s)。由于σ=(r,s)是向預(yù)言機(jī) FECDSA進(jìn)行查詢而獲得的，故與協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境中的輸出相同。因此，在U2被腐化的兩方協(xié)同簽名協(xié)議模擬過程中，A 對模擬執(zhí)行環(huán)境的視圖和對現(xiàn)實(shí)執(zhí)行環(huán)境中的視圖是不可區(qū)分的。

簽名偽造。類似地，A 在腐化參與方U2時(shí)無法區(qū)分協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境和協(xié)議理想執(zhí)行環(huán)境，C 可以調(diào)用A 的偽造簽名攻擊原始ECDSA 方案。由于模擬過程中A 生成的簽名驗(yàn)證公鑰Q是通過游戲GameSignC,π(1λ)中預(yù)言機(jī) FECDSA獲得的，故A 在游戲中的成功偽造(m*,σ*)也為C 在游戲GameSignC,π(1λ)中的成功偽造。因此，若敵手A 能夠以概率ε 贏得游戲那么C 同樣能夠以概率ε 贏得游戲GameSignC,π(1λ)。而原始ECDSA 簽名方案被證明是安全的（滿足定義1）[1]，即概率ε 被認(rèn)為是可忽略不計(jì)的，從而推導(dǎo)出A 贏得游戲的概率可忽略不計(jì)（即滿足定義2）。因此，本文提出兩方協(xié)同ECDSA 簽名方案在腐化U2時(shí)是安全的。

證畢。

綜上所述，本文所提兩方協(xié)同ECDSA 簽名方案是可證明安全的。換句話說，在僅一個(gè)簽名參與方私鑰泄露的情況下，攻擊者無法完成簽名，這保證了另一簽名參與方的私鑰隱私性，即滿足設(shè)計(jì)目標(biāo)的隱私性要求。

6 性能分析

本節(jié)將從理論分析與實(shí)驗(yàn)仿真2 個(gè)方面對本文所提方案（以下簡稱本文方案）進(jìn)行性能評估，并與Lindell 方案[13]、Doerner 方案[14]進(jìn)行比較。由于本文方案和Lindell 方案[13]均為兩方協(xié)同ECDSA 簽名方案，故在與Doerner 方案[14]比較時(shí)，僅考慮門限為(2,2)時(shí)的性能。

6.1 理論分析

首先，通過統(tǒng)計(jì)協(xié)議執(zhí)行過程中使用的密碼運(yùn)算操作個(gè)數(shù)和網(wǎng)絡(luò)傳輸?shù)脑貍€(gè)數(shù)，對Lindell方案[13]、Doerner 方案[14]和本文方案的計(jì)算開銷和通信開銷進(jìn)行了理論分析與比較。由于分布式密鑰生成協(xié)議只需在系統(tǒng)中執(zhí)行一次，因此本文主要分析與比較兩方協(xié)同簽名協(xié)議的計(jì)算開銷和通信開銷。

與Paillier 加密、Paillier 解密、Paillier 同態(tài)乘、橢圓曲線點(diǎn)乘操作的時(shí)間相比，橢圓曲線點(diǎn)加操作的時(shí)間可忽略不計(jì)，且在方案中使用次數(shù)較少，因此對該操作不予統(tǒng)計(jì)。令Enc、Dec、HM 分別表示Paillier 算法的加密、解密、同態(tài)乘法操作，PM 和h 分別表示橢圓曲線點(diǎn)乘操作和一般哈希操作，N和λ分別表示Paillier 公鑰長度和域上元素長度。此外，為了不失一般性，令輸出簽名的一方為U1，另一方為U2。

由于不同應(yīng)用環(huán)境對方案的安全需求不同，因此，本文分別考慮了方案在半誠實(shí)模型下和惡意模型下的計(jì)算開銷和通信開銷。半誠實(shí)模型下，敵手企圖獲取額外的秘密信息，但在執(zhí)行過程中不會偏移協(xié)議的設(shè)置。從方案設(shè)計(jì)角度，在半誠實(shí)模型下，本文方案與Lindell 方案[13]中的參與方不需要執(zhí)行關(guān)于離散對數(shù)的零知識證明協(xié)議，Doerner 方案[14]中的參與方不需要執(zhí)行一致性檢測協(xié)議。

表1 和表2 分別為惡意模型下和半誠實(shí)模型下的計(jì)算開銷與通信開銷統(tǒng)計(jì)結(jié)果。其中，Doerner 方案[14]中哈希操作h 的總個(gè)數(shù)是在安全參數(shù)為256 的情況下進(jìn)行統(tǒng)計(jì)計(jì)算的。安全級別越高，Doerner 方案[14]中哈希操作的總數(shù)越高，這對計(jì)算開銷有一定影響；同時(shí)Lindell 方案[13]中的Paillier 加密操作和解密操作的計(jì)算效率也會降低。

從表1 可知，在計(jì)算開銷方面，與Lindell 方案[13]比較，本文方案在U1端少一個(gè)橢圓曲線點(diǎn)乘操作和一個(gè)Paillier 解密操作，在U2端少一個(gè)Paillier 加密操作、一個(gè)同態(tài)乘法操作和一個(gè)橢圓曲線點(diǎn)乘操作；與Doerner 方案[14]比較，本文方案在U1端和U2端分別少一個(gè)和2 個(gè)點(diǎn)乘操作，以及數(shù)千個(gè)哈希操作。因此，在惡意敵手模型下，本文方案的計(jì)算開銷最低。

在通信開銷方面，顯然Doerner 方案[14]是最高的；按照NIST 的密鑰長度建議[32]，對于同一安全級別的協(xié)議，基于大整數(shù)分解的協(xié)議密鑰長度約為橢圓曲線密鑰長度的8 倍以上，即N＞8λ，從而可得本文方案的通信開銷比Lindell 方案[13]低。因此，本文方案的通信開銷也是最低的。

從表2 可知，去掉零知識證明協(xié)議或一致性檢測協(xié)議后，即在半誠實(shí)模型下，本文方案由于沒有開銷較高的Paillier 加解密操作和大量的哈希操作，因此在用戶U1端和U2端的計(jì)算開銷和通信開銷仍然比其他2 種方案低。

表1 惡意模型下兩方簽名協(xié)議計(jì)算開銷與通信開銷理論比較

表2 半誠實(shí)模型下兩方簽名協(xié)議計(jì)算開銷與通信開銷理論比較

6.2 實(shí)驗(yàn)仿真

在仿真測試中，本文以 NIST 標(biāo)準(zhǔn)化的secp256k1 橢圓曲線為基準(zhǔn)，即安全參數(shù)λ=256，雜湊函數(shù)則采用SHA-256，Paillier 算法的密鑰長度N=2 048。測試程序基于開源密碼學(xué)庫RELIC[33]，并使用C 語言編寫。測試環(huán)境為一臺配置為64 位Windows10 專業(yè)版操作系統(tǒng)、Intel(R)Core(TM)i5-6300U CPU @ 2.40 GHz 處理器、16.0 GB 內(nèi)存的惠普筆記本電腦。

在不考慮網(wǎng)絡(luò)時(shí)延的情況下，本文在局域網(wǎng)內(nèi)分別對3 種方案的兩方協(xié)同簽名協(xié)議運(yùn)行10 000 次，以平均運(yùn)行時(shí)間和通信帶寬為實(shí)驗(yàn)數(shù)據(jù)。圖1 和圖2 分別為各方案在惡意模型和半誠實(shí)模型下的運(yùn)行時(shí)間。

圖1 惡意模型下兩方協(xié)同簽名方案的運(yùn)行時(shí)間比較

圖2 半誠實(shí)模型下兩方協(xié)同簽名方案運(yùn)行時(shí)間比較

從圖1 和圖2 可知，與Lindell 方案[13]和Doerner方案[14]相比，本文方案在兩方協(xié)同簽名計(jì)算開銷上具有顯著優(yōu)勢。其中，在惡意模型下，本文方案的簽名運(yùn)行效率比Lindell 方案快97.42%，比Lindell方案快76.84%。值得注意的是，由于Doerner 方案簽名過程需要參與方進(jìn)行多次交互，因此，若充分考慮網(wǎng)絡(luò)時(shí)延，Doerner 方案的實(shí)際運(yùn)行效率將比當(dāng)前測試結(jié)果更低。

表3 為惡意模型和半誠實(shí)模型下的通信開銷統(tǒng)計(jì)結(jié)果。由表3 可知，與Lindell 方案和Doerner 方案相比，本文方案的通信開銷最小。其中，在惡意模型下，本文方案的通信開銷比Lindell 方案小21.74%，比Doerner 方案小99.3%。

表3 惡意模型和半誠實(shí)模型下的通信開銷比較

綜上所述，本文所提兩方協(xié)同ECDSA 方案在計(jì)算開銷和通信開銷上均具有明顯的優(yōu)勢，滿足設(shè)計(jì)目標(biāo)中的高效性要求。

7 結(jié)束語

由于簽名私鑰丟失和簽名權(quán)利集中都可能損害區(qū)塊鏈系統(tǒng)合法用戶的權(quán)益，分布式安全計(jì)算ECDSA 簽名的研究應(yīng)運(yùn)而生。然而現(xiàn)有的兩方或多方協(xié)同ECDSA 簽名算法存在計(jì)算開銷或通信開銷過高的問題，導(dǎo)致難以廣泛應(yīng)用于資源受限的用戶端。為了降低簽名私鑰泄露風(fēng)險(xiǎn)并同時(shí)保證協(xié)同簽名效率，本文提出一種安全高效的ECDSA 兩方協(xié)同簽名方案，主要通過引入Beaver三元組預(yù)計(jì)算技術(shù)，避免在協(xié)同簽名過程中使用計(jì)算繁重的同態(tài)加密和通信開銷較大的不經(jīng)意傳輸?shù)炔僮鳎瑥亩鴮?shí)現(xiàn)對簽名私鑰的隱私保護(hù)并極大地提高協(xié)同簽名的效率。方案的安全性在通用可組合框架下被證明，仿真實(shí)驗(yàn)結(jié)果表明，本文方案在簽名計(jì)算開銷和通信開銷方面優(yōu)于現(xiàn)有的兩方協(xié)同ECDSA 簽名算法。因此，本文的算法是可行且高效的。