高效的两方ECDSA门限方案

颜 萌， 马昌社

(华南师范大学计算机学院, 广州 510631)

在公钥密码技术领域中，密钥对于密码算法来说至关重要，私钥的安全决定着系统以及敏感信息的安全，一旦公钥系统中的私钥被泄露或者丢失，不仅会造成系统出现单点故障，而且在恶意攻击者获得用户私钥之后就可以轻松地获取并篡改敏感信息。由此，SHAMIR[1]提出门限方案，又名秘密共享方案，该方案利用密码技术将需要保护的明文信息进行分割并安全地由不同的参与者存储。随后，DESMEDT和FRANKEL[2]正式提出门限签名的概念。随着云计算以及区块链技术的高速发展，系统终端更容易遭受恶意攻击。为了防止权力过度集中，提升计算系统抵抗安全风险的能力，学者们针对不同的应用场景提出了不同的门限签名方案[3-5]。

1992年，JOHNSON等[6]为了响应NIST对数字签名标准的要求而提出了椭圆曲线数字签名算法(Elliptic Curve Digital Signature Algorithm，ECDSA)。随后，ECDSA算法作为数字签名算法的一种，被广泛用于移动电子商务领域。由于网上交易为现在的主流消费方式，基于ECDSA算法设计出高效率的门限方案势在必行。

现阶段，围绕ECDSA算法的门限化签名工作出现了大量研究。1996年，GENNRAO等[7]提出(t,q)门限ECDSA签名方案，该方案的门限值t≤q/2，且签名的计算和通信开销高。2001年，MACKENZIE和REITER[8]提出了第1个两方ECDSA门限签名方案，该方案在密钥生成过程中利用乘法秘密分享以及Paillier加法同态加密技术来解决ECDSA门限化工作中的难点，使得2个签名参与方能协同生成有效签名。GENNARO等[5]为了解决比特币钱包安全的问题，设计了基于门限加法同态加密技术的(t,q)门限方案，并在恶意模型下给出了安全证明。随后，BONEH等[9]优化了文献[5]的方案，提出了le-vel-1全同态加密的门限签名方案。但是，这些方案都采用了计算开销和通信开销都非常高的分布式同态加密密钥生成技术，在实际应用中受限。

LINDELL[10]提出的两方方案由于不需要执行分布式Paillier密钥算法，减少了部分的计算开销，与以前普通的DSA签名的门限方案相比，效率有一定的提升。相反，DOERNER等[11]没有采取同态加密方案而引入了不经意传输技术，提出了满足安全差异性需求的(2,n)门限ECDSA签名方案。虽然文献[11]的方案未利用同态加密技术，提高了协同签名的计算性能，但是该方案引入了不经意传输技术[12-13]，与文献[10]的方案相比，增加了近千倍的通信开销。近些年，国内学者在ECDSA门限化的研究上也取得了一些进展，如：王婧等[14]利用了Beaver三元组，提出了一种安全高效的两方协同ECDSA签名方案。

为了进一步提升两方ECDSA门限方案[10]的效率，本文提出了一个高效的两方ECDSA门限方案。该方案主要有以下优势：(1)在每一次对消息M进行签名时，签名双方在保证不泄露自己签名私钥份额的前提下共同生成有效签名；(2)不依赖待签名消息完成签名预处理，减少了签名过程中所产生的计算量，提升了签名效率。

1 预备知识

1.1 ECDSA算法标准

ECDSA算法是DSA算法的变体，利用了椭圆曲线加密算法(Elliptic Curve Cryptography,ECC)对DSA算法进行模拟。与普通的离散对数问题和大整数分解问题相比，因为椭圆曲线密码是目前唯一无法用亚指数算法破解的公钥密码，所以椭圆曲线密码的单位比特强度高于其他公钥密码体制。1999年，ECDSA算法成为ANSI标准，是目前应用最广泛的签名算法之一。以下给出对ECDSA算法的形式化定义。

定义1[6](ECDSA)设H(·)为哈希杂凑函数，待签名消息为M，所采用的椭圆曲线参数D=(E,G,P,p,q,h)，对应的密钥对为(x,Q)，其中，Q=x·P为公钥，x为私钥。

签名步骤：

(1)选择一个随机数k←Zq;

(2)计算R←k·P，并令R=(rx,ry);

(3)计算r=rxmodq，若r=0，则重新从第(1)步开始执行;

(4)计算待签名消息M的哈希值H(M);

(5)计算签名s=k-1(H(M)+xr)modq，若s=0，则重新从第(1)步开始执行;

(6)输出对消息M的签名(r,s)。

验证步骤：验证方在接收到消息M和签名(r,s)之后，进行如下运算：

(1)计算sP+H(M)Q=(x1,y1);

(2)当且仅当x1modq==r时，验证成功。

1.2 Paillier同态加密方案

Paillier同态加密方案PC=(PK,PE,PD)是基于复合剩余类的困难问题来保证加密方案的安全性的概率公钥加密算法[15]。该方案的描述如下：

(1)密钥生成算法PK：任选2个长度相同且满足gcd(pq,(p-1)(q-1))=1的大素数p和q，然后计算N=pq，令λ(N)=lcm(p-1,q-1)为N的卡迈可尔函数，并且任意选择整数g令L(x)=(x-1)∕N，计算生成Paillier加密方案的公钥ppk=(N,g)，私钥psk=(λ(N),μ)。

(2)加密算法PE：选择随机数r然后计算密文C=E(m,r)=gmrNmodN2，其中mN为待加密信息。

(3)解密算法PD：针对密文C，对其进行解密得到明文m=L(CλmodN2)×μmodN。

Paillier加密方案满足加法同态加密性质。对于任意2个明文a,bN，其对应的密文分别为ea=PE(ppk,a)=gar1NmodN2和eb=PE(ppk,b)=gbr2NmodN2，其中随机数r1,r2*n。定义则ea⊗eb为a+b的密文。定义

1.3 门限签名算法

1991年，DESMEDT和FRANKEL[16]提出了第一个真正的门限加密以及签名方案。一个(t,n)门限签名方案中有n个成员参与分布式签名，至少需要t+1(t+1≤n)个成员共同参与来生成签名，如成员人数少于或者等于门限数量t则无法生成有效签名。该方案通过将私钥信息分割并由多个用户分散保存，提高了系统的鲁棒性及安全性。1个(t,n)门限方案可以分为如下3个子协议：

(1)分布式密钥生成协议Thresh-KeyGen。该协议通过输入安全参数1λ，每个参与签名的成员Pi会获得公钥Pk以及对应的私钥份额ski，则sk1,sk2,…,skn是关于私钥sk的(t,n)门限秘密共享。

(2)分布式签名协议Thresh-Sig。此协议将待签名的信息M作为公共输入，同时将参与签名成员的私钥份额ski作为私有输入，σi为每个签名成员对信息M的签名。该协议结束后，将所有的签名份额σi合并后输出签名σ{Sig(sk,m)}。

(3)中心化验证算法Ver。输入待签名消息M、公钥Pk和签名σ，以检查σ是否正确。若验证算法Ver输出1，则签名验证成功。

1.4 安全模型和定义

1.4.1 敌手模型 根据GENNARO等[7]对敌手模型进行的描述可知，假定恶意敌手在(t,n)门限方案签名阶段至少可以攻击n个成员P1,P2,…,Pn中的t个成员，然后根据攻击能力的大小将敌手分为以下3种类型：

(1)窃听敌手：能够获取被攻击成员所存储的信息以及接收其通信信道的广播信息。

(2)中止敌手：不但拥有窃听敌手的能力，而且可以促使被攻击成员在每轮签名开始时停止发送消息。

(3)恶意敌手：不但拥有窃听敌手的能力，而且可以促使被攻击成员修改协议。

1.4.2 安全定义 本文定义的门限签名方案的安全性仅考虑不可伪造性，其定义如下：

定义2((t,n)门限签名方案的不可伪造性)令ε=(Thresh-KeyGen,Thresh-Sig,Ver)为(t,n)门限签名方案，称其是不可伪造的，如果敌手可以自适应地选择k次待签名信息M1,M2,…,Mk进行门限签名查询之后，能够在新的待签名信息M′(M′{M1,M2,…,Mk})上伪造有效的门限签名的概率是可忽略的。

2 高效的两方ECDSA门限方案

本文提出的高效的两方ECDSA数字签名方案共包括3个部分，分别为密钥生成算法TPKG、两方签名算法TPsign和签名验证。

2.1 密钥生成算法TPKG

在密钥生成阶段，由两方共同生成数字签名算法中用于验证签名的公钥和各方的部分签名私钥片，同时用户1调用同态加密方案，将其私钥的密文发送给用户2。如图1所示，令U1、U2分别表示为用户1、用户2，两方分别执行以下步骤：

图1 密钥生成算法TPKG

Step 1. 首先，用户U1选择随机数x1←Zq作为子私钥，并且计算子公钥片P1=x1·P，其中P是ECDSA椭圆曲线的基点； 然后，用户U1调用1.3节Paillier同态加密方案PC=(PK,PE,PD)，该同态加密方案的公钥、私钥分别为ppk、psk，将其所拥有的子私钥利用Paillier同态加密方案进行加密，其表示为ex1=PE(ppk,x1)。

Step 2. 用户U1将子公钥片P1和子私钥同态加密密文ex1发送给用户U2。

Step 3.U2同样随机选择x2←Zq作为子私钥，并计算子公钥片P2=x2·P。

Step 4. 用户U2将子公钥片P2发送给用户U1。

Step 5. 用户U1在收到用户U2发送的公钥份额P2后，计算公钥Pk=P2+P1，并存储参数{Pk,P2,ppk,psk}。

Step 6. 用户U2在收到用户U1发送的公钥份额P1后，计算公钥Pk=P1+P2，并存储参数{Pk,P1,ppk,ex1}。

2.2 两方签名算法TPsign

签名生成阶段包括2个步骤：离线预处理过程和在线签名过程(图2、图3)。离线预处理过程不依赖待签名消息，在正式签名之前就可以生成所必需的数据，从而提高签名效率。正式签名时，一旦接收到待签名消息M，签名者可以高效地生成对消息M的签名。两方签名算法TPsign的详细过程如算法1和算法2。

图2 签名离线预处理步骤图

图3 在线签名步骤图

算法1离线阶段的预处理算法

Step 1. 用户U1生成随机数k1←Zq，并计算R1=k1·P;

Step 2. 用户U1将R1发送给用户U2;

Step 3. 用户U2选择随机数k1←Zq，b←Zq和ρ←Zq2;

Step 4. 用户U2计算R2=k2·P;

Step 6. 用户U2利用在密钥生成阶段从用户U1获得的同态加密公钥来计算eb=PE(ppk,b+ρq)，此处为了让传递的信息更加安全，用户U2将ρ·q与b一起进行同态加密;

Step 8. 用户U2利用从用户U1获得的R1计算(x,y)=k2·R1;

Step 9. 计算r=xmodq;

Step 11. 用户U1利用从用户U2获得的R2计算(x,y)=k1·R2;

Step 12. 计算r=xmodq;

Step 15. 用户U2存储参数{x2,Pk,ppk,ex1,k2,r,b}。

算法2 在线签名算法

Step 1. 用户U2收到待签名消息M后，计算待签名消息M的哈希值h=H(M);

Step 3. 用户U2将ps发送给用户U1;

Step 5. 用户U1输出签名σ=(r,s)。

2.3 签名验证

本方案的签名验证过程详细表述如下：

Step 1. 用户U1利用签名验证算法对得到的签名σ=(r,s)进行验证：通过计算sP+H(M)Pk=(x,y)来验证是否满足xmodq==r。若验证失败，则终止协议。

Step 2. 用户U2收到签名σ=(r,s)后，采用与用户U1相同的计算方式来验证签名。如果2个通信方的验证都通过，则表明此次两方ECDSA签名有效，正常退出，否则终止操作。

3 方案分析

3.1 正确性分析

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

Pk=P1+P2=x1·P+x2·G=(x1+x2)·P。

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

R=R1·k2=R2·k1=k1·k2·P。

此外,sk=x1+x2，k=k1·k2,可得

Pk=sk·P，R=k·P=(x,y)，r=xmodq，

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

3.2 安全性分析

引理1[7]若签名方案是不可伪造的，并且它的门限签名方案是可模拟的，则该门限签名方案也是不可伪造的。

下面给出可模拟的概念。

定义3一个(t,n)门限签名方案需要满足以下条件才可以说是可模拟的：

(1)门限签名方案的密钥生成协议Thresh-KeyGen是可模拟的。保证在输入公钥Pk和被破坏的t-1个成员的私钥份额sk1,sk2,…,skt-1的条件下，存在一个能够模拟其他人在Thresh-KeyGen协议输出公钥Pk的交互视图的模拟器。

(2)门限签名方案的分布式签名协议Thresh-Sig是可模拟的。在输入公钥Pk，待签名消息M以及对它的数字签名σ，还有t-1个成员的私钥份额sk1,sk2,…,skt-1的条件下，存在一个能够模拟其他人在Thresh-Sig协议中输出数字签名σ的交互视图的模拟器。

定理1如果ECDSA是EUF-CMA安全的，则本文的两方ECDSA签名方案是不可伪造的。

证明根据引理1，只需要证明两方ECDSA门限签名方案是可模拟的。由于本方案只存在2个用户U1和U2，所以，仅考虑用户U1被攻击和用户U2被攻击2种情况，并分别展示如何模拟密钥生成和签名生成协议。

情形1:用户U1被攻击。假设敌手1攻击并控制了用户U1，再构造模拟器im1来模拟用户U2，通过提取用户U1的输入，生成一个敌手不可区分的交互视图。

(2)模拟签名生成。

③若第1条会话信息被解析为验证R1=k1·P，则模拟器im1令否则模拟器im1随机地选取R2;

情形2:用户U2被攻击。假设敌手2攻击并控制了用户U2，现在构造模拟器im2来模拟用户U1，通过提取用户U2的输入，生成一个敌手不可区分的交互视图。

(1)模拟密钥生成。与用户U1被攻击的情况相同，假设敌手2破坏了用户U2，那么由于模拟器知道用户U2的私钥份额x2和系统的公钥Pk，则模拟器可以通过计算P1=Pk-x2·P来模拟用户U1在密钥生成算法TPKG中输出公钥Pk的视图。所以，密钥生成算法TPKG是可模拟的。

(2)模拟签名生成。

综上所述，根据引理1，无论是用户U1还是用户U2被攻击，都可以构造相应的模拟器来模拟其协议的整个运行过程，即可证明ECDSA门限签名方案具有不可伪造性。证毕。

3.3 效率分析

在现有的两方ECDSA方案中，LINDELL提出的方案[10]比DOERNER提出的方案[11](下文分别简称为LINDELL方案、DOERNER方案)的效率更高，究其原因为：DOERNER方案采用OT(Oblivious Transfer)技术来替代Paillier同态加密技术，在实际应用中，一次k比特的OT运算需要O(k)次公钥密码操作，与同态加密技术相比，其计算量更大。由于本文提出的方案与LINDELL方案[10]相类似，所以接下来将与LINDELL方案进行效率对比。

本文提出的方案暂为一个基础的两方ECDSA门限方案，其安全性只达到被动安全级别，但同样可以利用LINDELL方案中所采取的理想函数实现主动安全。在进行效率分析时，忽略零知识证明，在半诚实模型下与本文方案进行比较，并列举出2个方案的指数运算次数。

表1 2种方案的计算效率

4 结论

现有的两方ECDSA签名方案不是存在计算开销过大的问题就是交互轮数过多，导致在实际应用中的效率并不高。为了提高协同签名效率，本文提出了一种高效的两方ECDSA门限签名方案，主要是将两方签名算法拆分为离线预计算算法和在线签名算法，并且证明了其不可伪造性。与文献[10]的两方ECDSA方案相比，本文提出的方案计算效率高，其离线预计算阶段完成了大部分的计算量，从而在线签名阶段仅仅需要简单的操作。本文方案虽然只具有被动安全，但是在通用可组合安全框架下可以实现主动安全。