安全高效的两方协同ECDSA 签名方案

王婧，吴黎兵,，罗敏，何德彪

（1.武汉大学计算机学院，湖北 武汉 430070；2.武汉大学国家网络安全学院，湖北 武汉 430070）

1 引言

椭圆曲线数字签名算法（ECDSA,elliptic curve digital signature algorithm）是椭圆曲线加密（ECC,elliptic curve cryptography）与数字签名算法（DSA,digital signature algorithm）的结合，于1999 年成为美国国家标准学会（ANSI,America National Standards Institute）标准，并于2000 年成为电气和电子工程师协会（IEEE,Institute of Electrical and Electronics Engineers）、美国国家标准与技术研究院（NIST,National Institute of Standards and Technology）标准[1]。与DSA 和RSA（Rivest-Shamir-Adleman）相比，ECDSA 具有计算量小、处理速度快、存储空间占用小、带宽要求低等特点，适用于计算能力、存储空间、带宽与功耗受限的应用场景。因此，ECDSA 被广泛应用于电子商务系统[2]和其他网络领域，如安全传输层（TLS,transport layer security）协议[3]和域名系统安全扩展（DNSSEC,domain name system security extension）协议[4]，用于提供身份认证、数据完整性验证、不可否认性等安全服务。随着比特币系统的成功部署与应用，ECDSA 受到更广泛的关注，并逐渐成为当前主流区块链平台及项目的默认签名机制，如以太坊和Hyperledger Fabric。

众所周知，数字签名方案的安全性依赖于签名者私钥的安全性。在区块链系统中，私钥是用户掌控其密码货币的关键，也是实施隐私保护方案的基础。用户发布交易时，需要先使用签名私钥对交易进行签名，只有被共识节点验证通过的交易才能成功上链，实现密码货币的转移或信息发布。恶意攻击者一旦非法窃取了区块链用户的签名私钥，就可以任意转移该用户的密码货币或冒充该用户发布非法交易信息。近年来，密码货币被盗事件频发，造成严重的经济损失[5-6]。与传统银行电子交易系统不同，一旦区块链密码货币被转移，就无法追回。即使用户已知私钥被滥用，成功上链的交易也无法撤回。2019 年2 月，加拿某平台误将102 枚比特币发送到私钥仅被已去世的首席执行官所知的冷钱包，导致这些比特币被永久锁死[7]。因此，防止私钥泄露并避免签名权利过度集中是当前基于签名技术的网络交易系统和区块链系统亟待解决的问题。

为了解决这一问题，常见的解决方法有多重签名、基于Shamir 秘密共享的(t,n)−门限签名和基于安全两方/多方计算的签名。其中，多重签名通常发生在区块链上，区块链需要引入一种对多重签名进行编码的方法，并对区块链进行重塑以完成基于多重签名交易的发布与验证，现有区块链难以支持这种技术。此外，不同签名者在区块链上进行多次签名，访问结构（签名者的身份、数量）容易暴露在区块链上，从而可能导致用户隐私泄露，且签名长度随签名者数量呈线性增长，签名验签时需要多个公钥参与验证，开销较高[8]。基于Shamir 秘密共享的(t,n)−门限签名往往需要借助一个可信中心为预先选定的签名群体分发私钥份额，并且需要至少t个签名方重构出完整的私钥才能完成签名。在实际情况下，颁发私钥的中心和签名时重构的私钥持有者便成为系统的安全瓶颈[9]。基于安全两方/多方计算的签名可在区块链下实施，不需要在链上执行所有过程，而且两方/多方计算签名中签名者信息被折叠成常规的区块链交易格式，因而能够兼容现有区块链系统并降低开销，并在一定程度上保证用户隐私。

MacKenzie 等[10]首次提出了针对DSA 的两方协同签名方案，可以使2 个签名参与方对给定的公钥生成有效的DSA 签名，而任何一方都不能单独完成签名，签名过程中不需要重构私钥。Gennaro等[11]针对比特币钱包安全提出了一种基于门限加法同态加密技术的(t,n)−门限DSA/ECDSA 签名方案，并在恶意模型下证明了其安全性。Boneh 等[12]对文献[11]方案进行了性能优化，提出了基于level-1 全同态加密的门限DSA/ECDSA 签名方案。然而，这些方案均使用了分布式同态加密密钥生成技术，签名参与方的通信开销和计算开销都非常高，难以实际应用于处理能力受限的比特币钱包服务或计算能力受限的区块链客户端。

Lindell[13]提出了基于Paillier 同态加密算法的两方协同ECDSA 签名方案，与上述方案不同的是，该方案不需要执行分布式Paillier 密钥算法，直接利用Paillier 同态属性即可完成两方协同签名，提高了两方协同签名的运行效率。为了满足用户对安全的差异性需求，Doerner 等[14]提出了基于秘密共享和不经意传输技术的(2,n)−门限ECDSA 签名方案，该方案不需要引入计算开销较高的Paillier 同态加密及其相关的零知识证明，从而大大提高了协同签名的计算性能。但是Doerner 方案引入了不经意传输协议[15-16]，与Lindell 方案[13]相比，增加了近千倍的通信开销，且不能应用于带宽受限的区块链客户端。Castagnos 等[17]使用哈希证明系统技术代替Lindell 方案[13]中的Paillier 同态加密技术，设计了一种新的两方协同ECDSA 签名方案，进而完善了Lindell 方案[13]的安全性证明。然而，对于128 bit安全的ECDSA 签名方案，Castagnos 方案[17]的运行效率比Lindell 方案[13]更低。

除两方协同的ECDSA 签名方案之外，多方门限ECDSA 签名方案也陆续被提出。Lindell 等[18]设计了一种安全隐私乘法协议，用于将原始的两方协同签名方案扩展成多方门限签名方案。Doerner 等[19]同样将Lindell[13]原始的两方门限ECDSA 签名方案扩展成了多方门限ECDSA 签名方案。Gennaro 等[20]设计了一种基于Paillier 同态加密的MtA 协议，该协议可以将基于乘法的共享份额转换为基于加法的共享份额，进而基于该协议提出一种新的多方门限ECDSA 协同签名方案。但是，这些方案仍然沿用了两方协同签名方案中所使用的同态加密算法或不经意传输协议，因而计算开销和通信开销非常高。

除ECDSA 之外，国内外学者还提出了对其他密码算法的私钥保护安全解决方案。针对基于身份的数字签名，He 等[21]和Feng 等[22]分别提出针对IEEE P1363 标准的两方协同签名方案和多方协同签名方案。侯红霞等[9]针对我国商用密码算法SM2，结合Lindell 方案[13]的思想设计了一种两方协同SM2 签名方案。Zhang 等[23]同样基于Paillier 同态加密算法，设计了一种新的两方协同SM2 签名方案。Mu 等[24]针对我国商用密码算法SM9，设计了基于Paillier 的两方协同SM9 签名方案。然而，这些方案一方面计算开销或通信开销较高，难以适用于计算能力或带宽受限的客户端；另一方面，难以兼容现有的区块链系统。

因此，为了提高协同签名的运行效率、降低签名过程的通信开销、保证签名私钥安全并兼容当前区块链系统，对两方/多方协同ECDSA 签名方案进行进一步研究具有非常重要的理论意义和现实意义。针对这一目标，并考虑到两方签名对客户端的友好性与便捷性，本文设计了一种新的安全高效两方协同ECDSA 签名方案。本文的主要贡献可分为以下3 个方面。

1)设计了一种安全高效的两方协同ECDSA 签名方案，通过预计算Beaver 三元组[25]，避免使用计算开销高昂的Paillier 同态加密和通信开销高昂的不经意传输技术，2 个参与方在不暴露各自私钥的情况下共同完成签名。

2)对本文所提方案提供了完整的安全性证明，结果表明，所提方案在不同时腐化2 个签名方的情况下能够有效保护ECDSA 签名私钥。

3)从理论分析和模拟验证2 个方面对本文所提方案进行了评估，并与2 个相关的两方协同签名进行了比较，结果表明，本文所提方案在计算开销和通信开销上都具有明显优势。

2 预备知识

2.1 ECDSA 数字签名算法

系统建立输入安全参数，输出算法公开参数param={E,G,P,p,q,h}，其中，E为定义在有限域Fp上的椭圆曲线，p为一个素数，G为椭圆曲线上所有整数点构成的加法群，P和q分别为群G的生成元和素数阶，h为输入映射到域的杂凑函数，即域由整数集合{1,2,…,q−1}构成。

密钥生成输入算法公开参数param，输出签名私钥d和验证公钥Q，其中d∈为随机秘密值，公钥Q=dP可公开发布。

签名生成输入算法公开参数param、用户私钥d和待签名消息m，输出签名σ=(r,s)。具体步骤如下。

1)选择一个随机数k∈，计算R=k⋅P=(rx,ry)，其中rx和ry分别为椭圆曲线上点R的横坐标和纵坐标。

2)计算r=rxmodq，若r=0，则返回步骤1)；否则，执行步骤3)。

3)计算s′=k−1(e+dr)modq，其中，e=h(m)为消息摘要。

4)输出签名信息σ=(r,s)，其中s=min{s′,q−s′}，min{}函数表示取集合中较小的数值。

签名验证输入待验证的消息m和签名σ，输出验证结果“1”或“0”。具体步骤如下。

1)解析签名σ获得(r,s)，计算摘要e=h(m)。

2)计算Rv=s−1(eP+rQ)=(xv,yv)。

3)若r=xvmodq，输出1；否则输出0。

2.2 Beaver 三元组乘法技术

Beaver 三元组乘法技术由Beaver[25]于1991 年首次提出，通过完全随机地设置电路中每个门的输入，然后进行校正的方法实现安全多方乘法计算。该方法避免了标准的安全两方或多方乘法协议中涉及的零知识证明或进一步秘密值共享等操作/协议，只需要进行简单的消息随机秘密值广播和重构即可实现安全两方或多方乘法计算。为了简便，本文将在后续描述中省略整数运算涉及的“modq”符号。

假设参与方U1和参与方U2已分别存有各自的秘密共享份额{ai,bi,Δai,Δbi,Δci}，i∈{1,2}，其中Δai和Δbi是完全随机的整数，整数Δc1和Δc2满足条件Δc1+Δc2=(Δa1+Δa2)(Δb1+Δb2)，U1和U2的目标为安全计算c=c1+c2=(a1+a2)(b1+b2)。基于Beaver 三元组的安全两方乘法协议步骤如下。

U1先分别计算其盲化数据u1=a1−Δa1和，再发送(u1,v1)给U2。U2先分别计算其盲化数据u2=a2−Δa2和v2=b2−Δb2，再发送(u2,v2)给U1。

U1进而可计算中间数据u=u1+u2、v=v1+v2和c1=Δc1+Δa1v+Δb1u。U2同理可计算中间数据u=u1+u2、v=v1+v2和c2=Δc2+Δa2v+Δb2u+uv。

最后，U1和U2交换各自的信息c1和c2，从而两方均可计算结果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，进一步地，通过以上步骤可得

因此，利用Beaver 三元组可以进行两方乘法计算。

安全性文献[25]指出{Δai,Δbi}是随机选取的，且每组数据仅使用一次，相当于独立且均匀分布的一次一密随机值，允许通信方在公开信道上发送具有完全隐私性的任意消息。此外，Beaver 分别证明了该方法在消息被篡改（详见文献[25]的安全性证明引理4 和引理6）和参与方被腐化（详见文献[25]的引理5 和引理7）情况下的安全性。因此，本文认为该方案在不需要引入承诺与零知识证明等额外密码原语的情况下，满足半诚实模型和恶意模型下的安全性。

一次性表Beaver[25]提出了一次性表的概念，用以描述一系列支持安全两方或多方计算的三元组对集合，如SETtri={(Δa1i,Δb1i,Δc1i),(Δa2i,Δb2i,Δc2i)}，其中i={1,2,…,N}，N表示集合大小。其中U1将获得大小为N的三元组集合 SETt1ri=，对称地，U2将获得大小为N的三元组集合此外，为了提高计算效率与安全性，Beaver 建议通过离线预计算的方式来获取 SETtri。

安全离线预计算协议Fp re在三元组构造过程中，(Δa1,Δb1)和(Δa2,Δb2)分别由U1和U2随机选取，然后通过交互计算得到c1和c2，可以观察到

其中，Δa1Δb1和Δa2Δb2可分别由U1和U2本地计算，因此构建三元组的难点在于如何计算Δa1Δb2和Δa2Δb1。Feng 等[26]基于现有成果列举了3 种生成Beaver 三元组的安全预计算方法。①首先基于加法同态加密技术构造一个乘法共享转加法共享的协议，再基于此计算Δa1Δb2和Δa2Δb1。以基于Paillier同态加密的方法为例：U1首先生成Paillier 的公私钥对(sk,pk)，计算密文x1=Encpk(Δa1)，将x1和公钥pk 发送给U2；U2收到消息后选取一个随机数η，计算密文，再将密文x2发送给U1；U1可解密获得y1=Δa1Δb2−η；类似地，重复上述步骤，U1可获得y1′=Δa2Δb1−η′，进而可以计算出Δc1=Δa1Δb1+y1+y1′；U2根据计算过程中选取的随机数可计算Δc2=Δa2Δb2+η+η′。该方法首次在文献[20]中被应用，并且其安全性也得到了证明。②与第一种方法类似，先计算Δa1Δb2和Δa2Δb1，再计算Δc1和Δc2，不同点在于用不经意传输协议代替加法同态加密技术以节约计算开销，具体实施方案可参考文献[14]。③基于可信第三方颁发有效的Beaver 三元组，如利用一个可信的服务器为U1和U2生成匹配的三元组，该方法在文献[27]中被应用。后文为了简便，令 Fpre表示安全的三元组离线预计算协议。

3 安全模型和设计目标

3.1 安全性定义

本节主要描述数字签名方案与两方协同数字签名方案的安全性定义。

1)标准数字签名安全性定义

与文献[13]类似，出于完整性和参考性目的，本文首先针对标准数字签名方案π=(Gen,Sign,Verify)给出一个基于游戏的安全性定义。游戏GameSignA,π(1λ)中共2 个角色，即概率多项式时间（PPT,probabilistic polynomial time）敌手A 和模拟器C。其中，C 为PPT 敌手A 提供方案相关的公开参数，包括签名验证公钥Q，同时提供对A 的签名查询应答；PPT 敌手A 的目标是在进行若干消息−签名对查询后，伪造消息m*的签名σ*；若伪造成功，则游戏输出“1”，否则游戏输出“0”。A 和C 的游戏流程如算法1 所示。

算法1标准数字签名

游戏1GameSignA,π(1λ)

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

② A 将消息m∈{01}*发送给C 进行签名询问CSignd(⋅)，C 返回m的合法签名σ；/*该步骤执行次数在多项式范围内，所有查询过的消息m构成集合Ω*/

③(m*,σ*)←ASignd(⋅)(1λ,Q)；/*敌手A 进行签名伪造*/

④ 当且仅当 Verify(m*,σ*)=1 且m*∉Ω时，游戏输出“1”；否则游戏输出“0”

定义1如果对于任意的PPT 敌手A，在游戏1中输出“1”的概率是可忽略的，即

其中，ε为一个可忽略概率阈值，λ为签名方案π的安全参数，则认为签名方案π满足选择消息攻击下的存在不可伪造性安全（EU-CMA,existential unforgeability against chosen-message attack）。

2)两方协同签名安全性定义

两方协同签名可视为标准数字签名的一种分布式表现形式，其输出的签名仍能通过算法Verify的验证，因此，本文采用类似于签名方案π的方式定义π衍生的两方协同签名方案Π=(DistGen,DistSign,Verify)的安全性。

与标准数字签名安全定义不同的是，本文假设PPT 敌手A 可以控制其中一个签名参与方Ui(i∈{1,2})，并且知道Ui的所有秘密值。因此，A和被腐化的Ui被认为是一体的，在后续描述中称Ui为腐化方或直接用A 代替Ui来描述游戏模拟过程。在模拟过程中，A 选择要签名的任意信息，与诚实参与方Uj(j≠i)进行交互生成签名。同时，A可以选择遵循协议设置或任意偏离协议设置，即敌手是恶意的。此外，敌手A 是静态的，即在协议初始化之前，敌手A 便确定被控制的参与方为Ui，且在一个游戏结束之前不会转换为参与方Uj。

算法2两方协同数字签名

游戏2GameDistSignA,Π(1λ)

①Q←Πi(1λ)；/*诚实参与方输出签名验证公钥，Ui被敌手控制*/

② A 选择m∈{01}*作为待签名的消息，与Πi(.)进行交互输出签名σ；/*该步骤执行次数在多项式范围内，所有査询过的消息m构成集合Ω*/

④ 当且仅当Verify(m*,σ*)=1 且m*∉Ω时，游戏输出“1”；否则游戏输出“0”

定义2如果对于任意的PPT 敌手A 以及被A 腐化的任意参与方Ui(i∈{1,2})，在游戏2 中输出“1”的概率是可忽略的，即

其中，ε为一个可忽略概率阈值，则认为签名方案Π满足选择消息攻击下的存在不可伪造性安全。

3.2 安全模型

通用可组合（UC,universally composable）安全是由Canetti[28]提出的一种根据协议现实执行环境和协议理想执行环境不可区分方法来定义密码协议安全性的框架。该框架的显著特点是：当一个组合协议的各个子协议被证明是UC 安全的，那么该组合协议是安全的。因此，可以模块化地选取或设计可证明安全的子协议，进而运用组合原理构造更复杂的安全密码协议。

在UC 框架下，理想函数F 是重要的组成部分，代表一个不可腐化的可信方，用于完成协议所需的理想功能与执行过程。PPT 敌手A 与协议参与方的交互用于模拟协议的现实执行过程，即协议现实执行环境。协议参与方（包括可视为理想敌手的模拟器C ）与理想函数的交互用于模拟协议的理想执行过程，即协议理想执行环境。本文提出的两方协同ECDSA签名方案是基于理想函数和组合的混合模型构造的。同时，本文方案的安全性也是基于此模型进行证明的。其中，分布式密钥生成模拟只需执行一次，两方协同签名模拟可执行多项式次数。值得注意的是，如果承诺与零知识证明协议是UC 安全的，那么在混合模型下协议模拟执行的输出和协议现实执行的输出在计算上是不可区分的。接下来，本文将对这几个理想函数进行简单介绍。

1)承诺理想函数 Fcom

在随机预言机模型下，Fcom可通过简单地定义函数Com(x)=h(x,r)←{0,1}λ来实现静态安全，且任意满足通用可组合安全的承诺函数h都满足 Fcom的形式化定义[13]，具体流程如下。

①当收到参与方Ui的消息(commit,sid,x)后，如果已经存储会话序号 sid 相关的承诺消息(commit,sid,∗)，则忽略此消息；否则，记录消息(sid,i,x)，并且将(receipt,sid)发送给参与方Uj。

② 当收到参与方Ui的消息(decommit,sid)后，如果已经存储消息(sid,i,x)，则将消息(decommit,sid,x)发送给参与方Uj。

根据文献[13,18]可知，标准零知识理想函数可形式化定义为

其中，str 表示空字符串，R 表示秘密信息x和证据ω之间的关系。在安全两方计算场景下，非交互式零知识证明理想函数与2 个参与方Ui、Uj的形式化交互流程如下。

当收到参与方Ui的消息(prove,sid,x,ω)后，如果会话序号sid 已被使用过或秘密信息x和证据ω之间不满足关系R，即(x,ω)∉R，则忽略本次的消息；否则，将(proof,sid,x)发送给参与方Uj。

①当收到参与方Ui的消息(com-prove,sid,x,ω)后，如果会话序号 sid 已被使用过或(x,ω)∉R，则忽略本次的消息；否则，将(proofreceive,sid)发送给参与方Uj。

② 当收到参与方Ui的消息(decom-proof,sid)后，如果已存储了(sid,i,x)，则将(decom-proof,sid,x)发送给参与方Uj。

在本文的方案设计中，R 为椭圆曲线上的离散对数关系，定义为RDL={(G,P,q,Q,x)|Q=xP}。对于关系RDL的零知识证明，本文可以采用经典的Schnorr 证明[29]来实现。

3.3 设计目标

本文提出的两方协同ECDSA 签名方案应满足以下4 个属性。

①隐私性。除协议的计算输出和协议本身所泄露的内容外，2 个签名参与方中的任何一方都不能从协议执行过程中获取其他任何信息，包括另一方的私有输入。

② 正确性。2 个签名参与方诚实地执行该协议时，协议输出合法的ECDSA 签名。

③兼容性。协议输出的正确签名仍能通过原签名方案验证算法的检测，即使用2.1 节描述的签名验证算法时，签名验证结果为“1”。

④ 高效性。充分考虑参与方的计算能力以及协同签名过程中的在线时延，签名过程应保证计算开销和通信开销尽可能小。

4 方案设计

本文提出的两方协同ECDSA 签名方案共包括4 个阶段，分别为系统建立、分布式密钥生成、两方协同签名和签名验证。系统建立和签名验证与2.1节中的描述一致，因此本节不再重复描述。分布式密钥生成和两方协同签名协议由2 个签名参与方U1和U2协同完成，其中分布式密钥生成算法只需运行一次，两方协同签名算法可运行多次。

在本文方案中，假设在运行分布式密钥生成和协同签名协议之前，系统已执行过（如第2.2 节所描述的）安全离线预计算协议 Fpre，并安全输出了签名参与方U1和U2所需的Beaver 三元组集合。换句话说，U1和U2在签名之前已秘密保存了配对的三元组集合，从而降低了在线协同签名的通信开销与计算开销。Beaver 三元组的离线预计算理念已在多个方案中被应用，如文献[26-27,30]。根据文献[25]的定义，为了保证协议在UC 框架下的安全性，Beaver 三元组应为一次一密随机值。因此，本文可根据实际应用场景需求，选择定期执行安全预计算协议来更新集合，以获得足够使用的三元组数量，或者一次性预计算出足够多的三元组。下面，将具体介绍本文提出的两方协同ECDSA 签名方案的分布式密钥生成协议与两方协同签名协议。

4.1 分布式密钥生成

分布式密钥生成协议由签名参与方U1和U2共同完成，输出签名验证公钥Q和各自的部分私钥d1,d2。

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

①U1选取一个随机数d1∈Zq*作为U1的部分私钥，计算对应的部分公钥Q1=d1P。

②U1发送消息(com-prove,1,Q1,d1)给理想函数（即U1发送关于Q1及其离散对数的零知识证明π1的承诺com 给U2）。

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

①当U2接收到的消息(proof-receipt,1)后，U2选取一个随机数作为U2的部分私钥，计算对应的部分公钥Q2=d2P。

②U2发送消息(prove,2,Q2,d2)给理想函数（即U2发送Q2和关于Q2的离散对数零知识证明π2给U1）。

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

当U1接收到的消息(proof,2,Q2)后，U1验证proof 的有效性，若无效则协议终止；否则，打开承诺并发送消息(decom-proof,1)给（即U1发送Q1和关于Q1的离散对数零知识证明π1给U2）。

4)U1和U2输出签名验证公钥Q，并安全存储各自的隐私信息

①U1计算签名验证公钥，并安全存储

② 当U2接收到理想函数的消息(decom-proof,1,Q1)后，U2验证proof 的有效性，若无效则协议终止；否则，计算签名验证公钥Q=Q1+Q2，并安全存储

4.2 两方协同签名

给定待签名的消息m，两方协同签名协议必须由参与方U1和U2共同完成，输出ECDSA 签名σ=(r,s)。

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

①U1选取一个随机数，计算R1=k1P。

②U1发送消息(com-prove,sid||1,R1,k1)给理想函数（即U1发送关于R1及其离散对数的零知识证明π3的承诺com 给U2）。

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

①当U2接 收 到的 消 息(proof-receipt,sid||1)后，U2选取一个随机数，计算R2=k2P。

②U2发送消息(prove,sid||2,R2,k2)给理想函数（即U2发送R2和关于R2的离散对数零知识证明π4给U1）。

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

①当U1接收到的消息(proof,sid||2,R2)后，U1验证proof 的有效性，若无效则协议终止；否则，打开承诺并发送消息(decom-proof,sid||1)给（即U1发送R1和关于R1的离散对数零知识证明π3给U2）。②U1依次计算R=R1+R2=(rx,ry)、r=rxmodq、，其中，e=h(m)，如果e为奇数，U1进一步计算，令δ1=δ1+1。

③U1先选择一个随机数，再按顺序选择中前2 个三元组(Δa11,Δb11,Δc11)和(Δa12,Δb12,Δc12)，进而分别计算数据u1=k1−Δa11、v1=ρ1−Δb11、w1=δ1−Δa12和t1=ρ1−Δb12。

④U1发送消息{u1,v1,w1,t1}给U2。

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

①当U2接收到理想函数的消息(decom-proof,sid||1,R1)后，U2验证proof 的有效性，若无效则协议终止；否则，依次计算R=R1+R2=(rx,ry)、r=rxmodq和消息杂凑值e=h(m)，并且计算

② 当U2接收到U1的消息(u1,v1,w1,t1)后，U2先选择一个随机数，再按顺序选择中前2 个三元组(Δa21,Δb21,Δc21)和(Δa22,Δb22,Δc22)，进而分别计算数据u2=k2−Δa21、v2=ρ2−Δb21、w2=δ2−Δa22和t2=ρ2−Δb22。

③U2先分别计算数据u=u1+u2、v=v1+v2、w=w1+w2、t=t1+t2，接着计算数据α2=k2v+ρ2u+Δc21、β2=δ2t+ρ2w+Δc22。

④U2删除当前中的三元组(Δa21,Δb21,Δc21)和(Δa22,Δb22,Δc22)，然后将消息{(u2,v2,w2,t2),(α2,β2)}发送给U1。

5)U1输出签名σ=(r,s)

①当U1收到U2的消息{(u2,v2,w2,t2),(α2,β2)}后，U1先计算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计 算，令s=min{s′,q−s′}，输出ECDSA 签名σ=(r,s)

若应用场景需要U2也输出签名，U1可将消息(α1,β1)给U2，则U2也可按照步骤5)计算获得签名σ=(r,s)。由于在Beaver 三元组乘法技术中，三元组必须遵循一次一密的原则才能满足多方计算的完美隐私性，因此U1和U2在每次签名之后删除已使用的三元组，避免签名过程中重复使用三元组。此外，当应用场景安全要求较低时，可删除方案涉及的所有承诺协议和零知识证明协议，即构成半诚实模型[31]下的安全两方协同ECDSA 签名方案，从而进一步提高协同签名的效率。

4.3 正确性分析

根据分布式密钥生成算法可得，签名验证公钥为

根据两方协同签名算法可得

此外，同理于2.2 节中Beaver 三元组乘法技术的正确性分析，即式(1)，可得

由此可知，本文所提两方协同ECDSA 签名方案输出的签名(r,s)和签名验证公钥Q与2.1 节描述的ECDSA 公钥签名(r,s)和验签公钥Q一致。因此，本文所提方案满足设计目标要求的正确性和兼容性。

5 安全性证明

引理1假设ECDSA 签名方案满足EU-CMA安全性，那么本文所提两方协同ECDSA 签名方案满足EU-CMA 安全性。

证明假设任意PPT 敌手A 在腐化任意一个协同签名参与方Ui(i∈{1,2})的情况下，能够以不可忽略的概率ε 在游戏中成功伪造消息−签名对(m*,σ*=(r*,s*))，那么本文可以构造一个模拟器C 作为游戏GameSignC,π(1λ)的概率多项式敌手，使C 能够以与ε 几乎相等的概率在GameSignC,π(1λ)中成功伪造消息−签名对(m*,σ*=(r*,s*))。同理于文献[13]，本文将考虑敌手腐化U1和敌手腐化U2这2 种情况，分别论述本文方案的安全性。其中，分布式密钥生成协议仅需模拟一次，两方协同签名协议可进行多次模拟。假设U1和U2在分布式密钥生成前已通过安全方式获得对应的由于Beaver 三元组已被证明是安全的且满足完美隐私性[25]，因此，为了满足UC 框架的安全模拟规则（即参与方之间、参与方与敌手间不直接交互），本文在模拟过程中引入一个Beaver 三元组乘法理想函数 FBT，用于接收/发送与Beaver 三元组直接相关的消息。

当i=1时，PPT 敌手A 腐化参与方U1。本文构造一个针对游戏的模拟器C，同时作为游戏GameSignC,π(1λ)的PPT 敌手。本质上，C 在协议模拟过程产生一个令A 不可区分的执行环境，然后利用A 在游戏中输出的伪造签名作为游戏GameSignC,π(1λ)的输出，以此攻击原始ECDSA 签名方案。

1)分布式密钥生成协议模拟

2)两方协同签名协议模拟

①在游戏GameSignC,π(1λ)中，C 向预言机FECDSA进行签名查询，获得σ=(r,s)，并根据签名验证算法进一步计算得到R。

不可区分性分析。在分布式密钥生成模拟过程中，可以观察到协同签名协议的现实执行环境与理想模拟执行环境仅有一个区别。在协议现实执行环境中，Q2是由诚实参与方U2选择一个随机数后计算Q2=d2P得来的；在协议模拟执行环境中，C 计算Q2=Q−Q1=Q−d1P，其中公钥Q是在游戏GameSignC,π(1λ)中查询预言机获取的。由于Q是随机选取的，因此d2P和Q−d1P是同分布的。此外，若U2不退出协议模拟，敌手A 可在该协议模拟结束后输出公钥Q=Q1+Q2=Q1+(Q−Q1)，与在协议现实执行环境中的输出相同；现实执行环境中的零知识证明与验证也同分布于()−混合模型。因此，在分布式密钥生成协议模拟过程中，A对模拟执行环境的视图和对现实执行环境中的视图是不可区分的。

在两方协同签名模拟过程中，可以观察到协议现实执行环境与理想模拟执行环境主要有2 个区别。一是计算R2的过程，同理于上述分析，对于A来说，模拟执行过程中的R2=R−k1P和现实执行过程中的R2=k2P是同分布且不可区分的。二是(u2,v2,w2,t2,α2,β2)的构造，在协议模拟环境中，u2,v2,w2,t2,α2均是C 选取的随机数，而β2是通过计算式β2=s(α1+α2)−β1获得的；在现实执行环境中，(u2,v2,w2,t2,α2,β2)是通过计算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均为独立分布的随机数，故C 随机选取的(u2,v2,w2,t2,α2)分别与现实执行环境中诚实参与方U2计算的(k2−Δa21，ρ2−Δb21，δ2−Δa22，ρ2−Δb22，k2v+ρ2u+Δc21)同分布；又因为α2和ρ2是随机的，所以s(α1+α2)−β1与β2也是同分布的。此外，在模拟协议不终止的情况下，A 可在游戏中输出当前模拟实例的签名r=rxmodq和s=(α1+α2)−1⋅[β1+(s(α1+α2)−β1)]，这与协议现实执行环境中的输出相同。因此，在U1被腐化时的两方协同签名协议模拟的过程中，A 对模拟执行环境的视图和对现实执行环境的视图是不可区分的。

签名伪造。通过上述分析可知，在分布式密钥生成模拟和两方协同签名模拟过程中，A 在腐化参与方U1时无法区分协议现实执行环境和协议模拟执行环境，故C 可以调用A 的伪造签名攻击原始ECDSA 方案。

由于在模拟过程中，A 生成的签名验证公钥Q是通过游戏GameSignC,π(1λ)中预言机 FECDSA获得的，故A 在游戏中的成功伪造(m*,σ*)也可作为C 在游戏GameSignC,π(1λ)中的成功伪造，即A 在游戏输出一个伪造的消息签名对(m*,σ*=(r*,s*))，C 可随之在游戏GameSignC,π(1λ)中输出(m*,σ*=(r*,s*))。

当i=2时，PPT 敌手A 腐化参与方U2。类似地，本文构造一个针对游戏GameSignC,π(1λ)的PPT敌手C，同时作为游戏的模拟器，能够利用A 的伪造签名攻击原始ECDSA 签名方案。

1)分布式密钥生成协议模拟

①在游戏GameSignC,π(1λ)中，C 向预言机FECDSA进行密钥生成查询，获得(1λ,Q)。其中，λ为安全参数，Q为ECDSA 的签名验证公钥。

2)两方协同签名协议模拟

①在游戏GameSignC,π(1λ)中，C 向预言机FECDSA进行签名查询，获得σ=(r,s)，并根据签名验证算法进一步计算得到R。

④ 当收到 A 发送给FBT的消息(sid,(u2,v2,w2,t2,α2,β2))后，C 验证A 的消息是否按照4.1 节中步骤4)计算所得，若不是，则终止协议，否则C 输出σ=(r,s)。

不可区分性分析。在U2被腐化时的分布式密钥生成模拟过程中，A 对模拟执行环境的视图和对现实执行环境中的视图是不可区分的，其原理与U1被腐化时相同，所以本文不再重复描述。

对于U2被腐化时的两方协同签名模拟过程，可以观察到协议现实执行环境与理想模拟执行环境同样有2 个区别。一是计算R2的过程，同理于上述分析，对于A 来说，模拟执行过程中的R1=R−k2P和现实执行过程中的R1=k1P是同分布且不可区分的。二是(u1,v1,w1,t1)的构造，在协议理想模拟环境中，u1,v1,w1,t1均为C 选取的随机数；在现实执行环境中，(u1,v1,w1,t1)则通过计算u1=k1−Δa11、v1=ρ1−Δb11、w1=δ1−Δa12、t1=ρ1−Δb12获得。由于ρ1、Δa11、Δb11和Δa12、Δb12均为独立分布的随机数，故C 随机选取的(u1,v1,w1,t1)分别与现实执行环境中诚实参与方U2计算的(k1−Δa11，ρ1−Δb11，δ1−Δa12，ρ1−Δb12)同分布。此外，在模拟协议不终止的情况下，C 可在游戏中输出签名σ=(r,s)。由于σ=(r,s)是向预言机 FECDSA进行查询而获得的，故与协议现实执行环境中的输出相同。因此，在U2被腐化的两方协同签名协议模拟过程中，A 对模拟执行环境的视图和对现实执行环境中的视图是不可区分的。

签名伪造。类似地，A 在腐化参与方U2时无法区分协议现实执行环境和协议理想执行环境，C 可以调用A 的伪造签名攻击原始ECDSA 方案。由于模拟过程中A 生成的签名验证公钥Q是通过游戏GameSignC,π(1λ)中预言机 FECDSA获得的，故A 在游戏中的成功伪造(m*,σ*)也为C 在游戏GameSignC,π(1λ)中的成功伪造。因此，若敌手A 能够以概率ε 赢得游戏那么C 同样能够以概率ε 赢得游戏GameSignC,π(1λ)。而原始ECDSA 签名方案被证明是安全的（满足定义1）[1]，即概率ε 被认为是可忽略不计的，从而推导出A 赢得游戏的概率可忽略不计（即满足定义2）。因此，本文提出两方协同ECDSA 签名方案在腐化U2时是安全的。

证毕。

综上所述，本文所提两方协同ECDSA 签名方案是可证明安全的。换句话说，在仅一个签名参与方私钥泄露的情况下，攻击者无法完成签名，这保证了另一签名参与方的私钥隐私性，即满足设计目标的隐私性要求。

6 性能分析

本节将从理论分析与实验仿真2 个方面对本文所提方案（以下简称本文方案）进行性能评估，并与Lindell 方案[13]、Doerner 方案[14]进行比较。由于本文方案和Lindell 方案[13]均为两方协同ECDSA 签名方案，故在与Doerner 方案[14]比较时，仅考虑门限为(2,2)时的性能。

6.1 理论分析

首先，通过统计协议执行过程中使用的密码运算操作个数和网络传输的元素个数，对Lindell方案[13]、Doerner 方案[14]和本文方案的计算开销和通信开销进行了理论分析与比较。由于分布式密钥生成协议只需在系统中执行一次，因此本文主要分析与比较两方协同签名协议的计算开销和通信开销。

与Paillier 加密、Paillier 解密、Paillier 同态乘、椭圆曲线点乘操作的时间相比，椭圆曲线点加操作的时间可忽略不计，且在方案中使用次数较少，因此对该操作不予统计。令Enc、Dec、HM 分别表示Paillier 算法的加密、解密、同态乘法操作，PM 和h 分别表示椭圆曲线点乘操作和一般哈希操作，N和λ分别表示Paillier 公钥长度和域上元素长度。此外，为了不失一般性，令输出签名的一方为U1，另一方为U2。

由于不同应用环境对方案的安全需求不同，因此，本文分别考虑了方案在半诚实模型下和恶意模型下的计算开销和通信开销。半诚实模型下，敌手企图获取额外的秘密信息，但在执行过程中不会偏移协议的设置。从方案设计角度，在半诚实模型下，本文方案与Lindell 方案[13]中的参与方不需要执行关于离散对数的零知识证明协议，Doerner 方案[14]中的参与方不需要执行一致性检测协议。

表1 和表2 分别为恶意模型下和半诚实模型下的计算开销与通信开销统计结果。其中，Doerner 方案[14]中哈希操作h 的总个数是在安全参数为256 的情况下进行统计计算的。安全级别越高，Doerner 方案[14]中哈希操作的总数越高，这对计算开销有一定影响；同时Lindell 方案[13]中的Paillier 加密操作和解密操作的计算效率也会降低。

从表1 可知，在计算开销方面，与Lindell 方案[13]比较，本文方案在U1端少一个椭圆曲线点乘操作和一个Paillier 解密操作，在U2端少一个Paillier 加密操作、一个同态乘法操作和一个椭圆曲线点乘操作；与Doerner 方案[14]比较，本文方案在U1端和U2端分别少一个和2 个点乘操作，以及数千个哈希操作。因此，在恶意敌手模型下，本文方案的计算开销最低。

在通信开销方面，显然Doerner 方案[14]是最高的；按照NIST 的密钥长度建议[32]，对于同一安全级别的协议，基于大整数分解的协议密钥长度约为椭圆曲线密钥长度的8 倍以上，即N＞8λ，从而可得本文方案的通信开销比Lindell 方案[13]低。因此，本文方案的通信开销也是最低的。

从表2 可知，去掉零知识证明协议或一致性检测协议后，即在半诚实模型下，本文方案由于没有开销较高的Paillier 加解密操作和大量的哈希操作，因此在用户U1端和U2端的计算开销和通信开销仍然比其他2 种方案低。

表1 恶意模型下两方签名协议计算开销与通信开销理论比较

表2 半诚实模型下两方签名协议计算开销与通信开销理论比较

6.2 实验仿真

在仿真测试中，本文以 NIST 标准化的secp256k1 椭圆曲线为基准，即安全参数λ=256，杂凑函数则采用SHA-256，Paillier 算法的密钥长度N=2 048。测试程序基于开源密码学库RELIC[33]，并使用C 语言编写。测试环境为一台配置为64 位Windows10 专业版操作系统、Intel(R)Core(TM)i5-6300U CPU @ 2.40 GHz 处理器、16.0 GB 内存的惠普笔记本电脑。

在不考虑网络时延的情况下，本文在局域网内分别对3 种方案的两方协同签名协议运行10 000 次，以平均运行时间和通信带宽为实验数据。图1 和图2 分别为各方案在恶意模型和半诚实模型下的运行时间。

图1 恶意模型下两方协同签名方案的运行时间比较

图2 半诚实模型下两方协同签名方案运行时间比较

从图1 和图2 可知，与Lindell 方案[13]和Doerner方案[14]相比，本文方案在两方协同签名计算开销上具有显著优势。其中，在恶意模型下，本文方案的签名运行效率比Lindell 方案快97.42%，比Lindell方案快76.84%。值得注意的是，由于Doerner 方案签名过程需要参与方进行多次交互，因此，若充分考虑网络时延，Doerner 方案的实际运行效率将比当前测试结果更低。

表3 为恶意模型和半诚实模型下的通信开销统计结果。由表3 可知，与Lindell 方案和Doerner 方案相比，本文方案的通信开销最小。其中，在恶意模型下，本文方案的通信开销比Lindell 方案小21.74%，比Doerner 方案小99.3%。

表3 恶意模型和半诚实模型下的通信开销比较

综上所述，本文所提两方协同ECDSA 方案在计算开销和通信开销上均具有明显的优势，满足设计目标中的高效性要求。

7 结束语

由于签名私钥丢失和签名权利集中都可能损害区块链系统合法用户的权益，分布式安全计算ECDSA 签名的研究应运而生。然而现有的两方或多方协同ECDSA 签名算法存在计算开销或通信开销过高的问题，导致难以广泛应用于资源受限的用户端。为了降低签名私钥泄露风险并同时保证协同签名效率，本文提出一种安全高效的ECDSA 两方协同签名方案，主要通过引入Beaver三元组预计算技术，避免在协同签名过程中使用计算繁重的同态加密和通信开销较大的不经意传输等操作，从而实现对签名私钥的隐私保护并极大地提高协同签名的效率。方案的安全性在通用可组合框架下被证明，仿真实验结果表明，本文方案在签名计算开销和通信开销方面优于现有的两方协同ECDSA 签名算法。因此，本文的算法是可行且高效的。