Loading [MathJax]/jax/output/SVG/jax.js

高效的两方ECDSA门限方案

颜萌, 马昌社

颜萌, 马昌社. 高效的两方ECDSA门限方案[J]. 华南师范大学学报(自然科学版), 2022, 54(4): 121-128. DOI: 10.6054/j.jscnun.2022066
引用本文: 颜萌, 马昌社. 高效的两方ECDSA门限方案[J]. 华南师范大学学报(自然科学版), 2022, 54(4): 121-128. DOI: 10.6054/j.jscnun.2022066
YAN Meng, MA Changshe. An Efficient Threshold Scheme for Two-party ECDSA[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 121-128. DOI: 10.6054/j.jscnun.2022066
Citation: YAN Meng, MA Changshe. An Efficient Threshold Scheme for Two-party ECDSA[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 121-128. DOI: 10.6054/j.jscnun.2022066

高效的两方ECDSA门限方案

基金项目: 

国家自然科学基金项目 61672243

详细信息
    通讯作者:

    马昌社,chsma@163.com

  • 中图分类号: TP309

An Efficient Threshold Scheme for Two-party ECDSA

  • 摘要: 针对现有的门限ECDSA方案存在的计算开销过大、签名效率不高以及通信开销过大的问题,提出了一种高效的两方ECDSA门限方案。该方案将签名私钥拆分成2个部分,分别由两方保管; 利用同态加密技术,每一次协同签名都需要双方用户同时参与签名过程,其中任意一方都无法掌握完整的签名私钥; 将签名阶段分为了离线预计算阶段以及在线签名阶段,在离线预计算阶段提前完成了绝大部分计算量,在线签名阶段高效且快速,提高了签名效率。随后,对该方案给出正确性分析、安全证明及效率对比。研究结果表明:高效的两方ECDSA门限方案的在线签名阶段有效地避免了花销高昂的同态操作,具有签名效率高、通信代价低和交互轮数少等优势,实用性更高。
    Abstract: An efficient two-party ECDSA threshold scheme is proposed to fix the problems of existing threshold ECDSA schemes, e.g., some signature protocols having too much computation overhead or too many interaction rounds, leading to low signature efficiency, and some signature protocols having OT (oblivious transfer) to replace the Paillier homomorphic encryption technology, increasing the communication cost by thousands of times. The scheme divides the signature private key into two parts to be kept by two parties respectively. Using the homomorphic encryption technology, each collaborative signature requires both users to participate in the signature process at the same time. In addition, the signature phase is divided into the offline precomputation phase and the online signature phase. Most of the computation is completed in advance in the offline precomputation phase. The online signature phase is efficient and fast, which improves the signature efficiency. The correctness analysis and security proof of the scheme are given, and the two ECDSA schemes proposed by Lindell and this current scheme are compared in terms of theoretical analysis. The results show that the scheme avoids the expensive homomorphic operation in the online signature phase and has the advantages of high signature efficiency, low communication cost, less interaction rounds and higher practicability.
  • 在公钥密码技术领域中,密钥对于密码算法来说至关重要,私钥的安全决定着系统以及敏感信息的安全,一旦公钥系统中的私钥被泄露或者丢失,不仅会造成系统出现单点故障,而且在恶意攻击者获得用户私钥之后就可以轻松地获取并篡改敏感信息。由此,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签名方案,该方案的门限值tq/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)不依赖待签名消息完成签名预处理,减少了签名过程中所产生的计算量,提升了签名效率。

    在本文中,循环群G的阶为素数q,有限域Fpp个元素,由其中的元素可定义有限域Fp上的一条椭圆曲线EP为椭圆曲线E上的一个基点; xX表示从集合X中(或者是从X分布中)随机均匀采样x; H(·)表示哈希杂凑函数,其表现形式为H: {0, 1}*Zq; 对于一个整数N,ZN={1,2,,N1}, ZN={x0<x<Ngcd(x,N)=1}

    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) 选择一个随机数kZq;

    (2) 计算Rk·P,并令R=(rx, ry);

    (3) 计算r=rx mod q,若r=0,则重新从第(1)步开始执行;

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

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

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

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

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

    (2) 当且仅当x1mod q==r时,验证成功。

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

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

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

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

    Paillier加密方案满足加法同态加密性质。对于任意2个明文a,bZN,其对应的密文分别为ea= PE(ppk,a)=garN1modN2eb=PE(ppk,b)=gbrN2modN2,其中随机数r1,r2Zn。定义eaeb=(ea× eb)modN2=ga(r1)Ngb(r2)N=ga+b(r1r2)NmodN2= PE(a+b),则eaeba+b的密文。定义(ea)b=eaeaeab

    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,则签名验证成功。

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

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

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

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

    假设敌手A的计算能力是可以被概率多项式时间(Probabilistic Polynomial Time,P.P.T)图灵机所模拟的,这就意味着敌手解决椭圆曲线上的离散对数困难问题是不可行的。敌手类型又可分为静态敌手和自适应敌手,二者的区别在于在不同的时间点选择要攻击的用户。下面在讨论本文门限签名方案时,只考虑静态敌手,即在协议开始执行前就选择好要攻击的用户,在协议执行中角色不会转变。

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

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

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

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

    图  1  密钥生成算法TPKG
    Figure  1.  The key generation algorithm TPKG

    Step 1. 首先,用户U1选择随机数x1Zq作为子私钥,并且计算子公钥片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同样随机选择x2Zq作为子私钥,并计算子公钥片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图 3)。离线预处理过程不依赖待签名消息,在正式签名之前就可以生成所必需的数据,从而提高签名效率。正式签名时,一旦接收到待签名消息M,签名者可以高效地生成对消息M的签名。两方签名算法TPsign的详细过程如算法1和算法2。

    图  2  签名离线预处理步骤图
    Figure  2.  Step diagram of signature offline preprocessing
    图  3  在线签名步骤图
    Figure  3.  The steps of online signature

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

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

    Step 2. 用户U1R1发送给用户U2;

    Step 3. 用户U2选择随机数k1ZqbZqρZq2;

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

    Step 5. 用户U2计算t=k2-1 mod q;

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

    Step 7. 用户U2进行同态操作¯ex1=(ebx1)t;

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

    Step 9. 计算r=x mod q;

    Step 10. 用户U2¯ex1R2发送给用户U1;

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

    Step 12. 计算r=x mod q;

    Step 13. 用户U1利用同态加密方案中的私钥进行解密,获得ˉx=PD(psk, ¯ex1);

    Step 14. 用户U1存储参数{x1, Pk, ppk, psk, r, ˉx, k1};

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

    算法2   在线签名算法

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

    Step 2. 用户U2在本地计算部分签名片ps=k2-1(h+x2·r-b·r) mod q;

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

    Step 4. 用户U1计算对消息的正式签名s=k1-1(ps+ˉx·r)mod q;

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

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

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

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

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

    Pk=P1+P2=x1P+x2G=(x1+x2)P

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

    R=R1k2=R2k1=k1k2P

    此外, sk=x1+x2k=k1·k2, 可得

    Pk=skP,R=kP=(x,y),r=xmodq,s=k11(ps+ˉxr+ρq)modq=k1(h+skr)

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

    引理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个用户U1U2,所以,仅考虑用户U1被攻击和用户U2被攻击2种情况,并分别展示如何模拟密钥生成和签名生成协议。

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

    (1) 模拟密钥生成。假设敌手A1破坏了用户U1,则由于模拟器Sim1知道用户U1的私钥份额x1及系统的公钥Pk,模拟器可以通过计算P2=Pk-x1·P,模拟出用户U2在密钥生成算法TPKG中输出公钥Pk的视图。由于模拟器知道私钥份额x1,所以也可以计算出ex1=PE(ppk, x1)。因此,密钥生成算法TPKG是可模拟的。

    (2) 模拟签名生成。

    ① 模拟器Sim1接受一个关于消息M的ECDSA签名σ=(r, s);

    ② 模拟器Sim1使用ECDSA验证算法来计算R=s·P+r·Pk;

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

    ④ 第2条会话信息被解析为R2¯ex1、ps。模拟器Sim1随机选取ps的值并计算ˉx=s·k1-ps,则可以由计算出传递的信息¯ex1=PE(ppk,ˉx);

    ⑤ 模拟器Sim1输出正确的ECDSA签名σ=(r, s)并终止模拟签名过程。

    观察以上模拟的交互过程可知,敌手A1的视图分布与真实协议执行环境下的输出是不可区分的。究其原因为:在交互过程中计算公钥Pk时,真实协议执行中,是由诚实用户U2随机选择私钥份额x2,计算公钥片P2=x2·P; 在模拟过程中,模拟器Sim1计算公钥片P2=Pk-x1·P。由于Pk是随机选择的,故x2·P和Pk-x1·P是同分布的。因此,模拟器Sim1的输出与诚实用户U2的输出分布是相同的。

    在签名阶段, 敌手A1的视图分布与真实协议执行环境下的不同之处在于ex1¯ex1和ps的生成方式。具体来说:(1)在模拟执行环境中,R2= k1-1·R,其中k1是随机数。但是在真实环境中R2=k2·P,其中,k2是随机数。因为敌手无法获取k2的信息,所以二者都满足均匀随机分布,敌手无法有效区分这2种情况。(2)在真实环境下计算¯ex1=(ebex1)t,其中t=k2-1 mod q,而模拟器Sim1使用随机选取的ps,然后计算ˉx=(s·k1-ps),便可以得到传递的信息¯ex1= PE(ppk, ˉx)。显然,真实环境与模拟执行环境下生成的签名都为σ=(r, s),敌手无法做出区分。综上所述,对于敌手A1来说,真实的签名协议执行过程和模拟的执行过程是无法区分的。

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

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

    (2) 模拟签名生成。

    ① 模拟器Sim2接受一个关于消息M的ECDSA签名σ=(r, s)。

    ② 模拟器Sim2使用ECDSA算法来计算点R=s·P+r·Pk,并向敌手A2发送指令,指示其开始执行签名协议。

    ③ 第1条会话消息被解析为敌手A2向模拟器Sim2发送R2,模拟器Sim2验证是否满足R2=k2·P,且判断R2是否为椭圆曲线上的非零点。若不成立,模拟器Sim2中止协议; 否则,模拟器Sim2计算R1=k2-1·R并发送给敌手A2

    ④ 第2条会话信息被解析为:模拟器Sim2计算ps=k2-1(h+x2·r-b·r) mod q¯ex1=(ebex1)t

    ⑤ 第3条会话消息被解析为和ps,模拟器Sim2设置给敌手A2的预言机回答为s

    若敌手A2诚实执行协议,则会输出正确的ECDSA签名σ=(r, s)。

    观察以上模拟的交互过程可知,敌手A2的视图分布与真实协议执行环境下密钥生成阶段的输出是不可区分的,与用户U2被攻击的情况相似,由于Pk是随机选择的,故x1·P和Pk-x2·P是同分布的。因此,其密钥生成协议是可模拟的。

    在签名过程中,具体来说:(1)在模拟执行环境中,R1= k2-1 ·R; 在真实环境中, R1=k1·P, 其中k1为随机数。因为敌手无法获取k1的信息,所以二者都满足均匀随机分布,敌手无法有效区分这2种情况。因此,其签名生成协议是可模拟的。(2)在真实环境中,¯ex1=(ebex1)t,其中,ex1=PE(ppk, x1),t=k2-1 mod q。而在模拟环境中, 由于用户U2的信息都被暴露,包括bk2x2,所以与真实环境下的执行结果是一样的。由于签名预言机生成的(r, s)一定满足随机均匀的特性,且k1也是随机选择的,两者的执行结果对于敌手A2来说都是一样的。

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

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

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

    在分析计算量时,本文只讨论点乘运算、Paillier加密及解密计算的计算量,而忽略其他计算量,并且把一次椭圆曲线上的点乘运算的时间记为Td、Paillier加密或解密计算时间记为Tp。由2个方案的效率对比结果(表 1)可知本文方案的在线签名效率远远优于LINDELL方案:(1)在密钥生成阶段:在本文方案中,用户U1计算P1=x1·P和ex1=PE(ppk, x1),计算时间为1·Td+1·Tp; 用户U2计算P2=x2·P,计算时间仅为1·Td。而在LINDELL方案中,用户U1计算Q1= x1·PQ=x1·Q2和Paillier加密操作ckey=Encpk(x1),计算时间为2·Td+1·Tp; 用户U2计算Q2=x2·PQ=x2·Q1,计算时间仅为2·Td。(2)在离线预计算阶段:在本文方案中,用户U1计算R1=k1·Px, y=k1·R2,并对¯ex1进行解密ˉx=PD(psk, ¯ex1),计算时间为2·Td+1· Tp; 用户U2计算R2=k2·P和(x, y)=k2· R1,并进行Paillier加密操作eb=PE(ppk, b+ρq)和Paillier同态操作¯ex1=(ebex1)t,计算时间为2·Td+2· Tp。在LINDELL方案中,用户U1计算R1=k1·PR=k1·R2, 计算时间为2·Td; 用户U2计算R2=k2·PR= k2·R1,并进行同态操作C2=k2-1·x2·rckey,计算时间共计2·Td+1·Tp。(3)在在线签名阶段:在本文方案中,用户U1U2都只需要进行线性运算,所以两方在此阶段的点乘运算次数为0。在LINDELL方案中,用户U1需要对接收的密文C3进行同态解密,计算时间为1·Tp; 用户U2需要对信息加密C1=Encpk(ρ·q+[k2-1 ·m′ mod q]),计算时间为1·Tp。综上可知,由于本文方案在离线预计算阶段完成了绝大部分计算量,从而在线签名时仅需要简单的操作,而LINDELL方案在线计算还需要一些Paillier加密操作。相比之下, 本文方案在线签名阶段的计算量是几乎可以忽略的。

    表  1  2种方案的计算效率
    Table  1.  The calculation efficiency of the two schemes
    签名阶段 本文方案 LINDELL方案
    U1 U2 U1 U2
    密钥生成阶段 Td+1·Tp Td Td+1·Tp Td
    离线预计算 Td+1·Tp Td+2·Tp Td Td+1·Tp
    在线签名 0 0 Tp Tp
    下载: 导出CSV 
    | 显示表格

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

  • 图  1   密钥生成算法TPKG

    Figure  1.   The key generation algorithm TPKG

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

    Figure  2.   Step diagram of signature offline preprocessing

    图  3   在线签名步骤图

    Figure  3.   The steps of online signature

    表  1   2种方案的计算效率

    Table  1   The calculation efficiency of the two schemes

    签名阶段 本文方案 LINDELL方案
    U1 U2 U1 U2
    密钥生成阶段 Td+1·Tp Td Td+1·Tp Td
    离线预计算 Td+1·Tp Td+2·Tp Td Td+1·Tp
    在线签名 0 0 Tp Tp
    下载: 导出CSV
  • [1]

    SHAMIR A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613. doi: 10.1145/359168.359176

    [2]

    DESMEDT Y, FRANKEL Y. Threshold cryptosystems[C]//Proceedings of 89th Annual International Cryptology Conference. Berlin: Springer, 1989: 307-315.

    [3]

    SHOUP V, GENNARO R. Securing threshold cryptosystems against chosen ciphertext attack[J]. Journal of Cryptology, 2002, 15(2): 75-96. doi: 10.1007/s00145-001-0020-9

    [4]

    FOUQUE P, POUPARD G, STERN J. Sharing decryption in the context of voting or lotteries[C]//Proceedings of Financial Cryptography—FC 2000. Berlin: Springer, 2000: 90-104.

    [5]

    GENNARO R, GOLDFEDER S, NARAYANAN A. Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security[C]//Proceedings of 16th International Conference on Applied Cryptography and Network Security. Berlin: Springer, 2016: 156-174.

    [6]

    JOHNSON D, MENEZES A, VANSTONE S. The elliptic curve digital signature algorithm(ECDSA)[J]. International Journal of Information Security, 2001, 1(1): 36-63. doi: 10.1007/s102070100002

    [7]

    GENNARO R, JARECKI S, KRAWCZYK H, et al. Robust threshold DSS signatures[C]//Proceedings of 98th International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1996: 354-371.

    [8]

    MACKENZIE P, REITER M K. Two-party generation of DSA signatures[C]//Proceedings of 21st Annual International Cryptology Conference. Berlin: Springer, 2001: 137-154.

    [9]

    BONEH D, GENNARO R, GOLDFEDER S. Using level-1 homomorphic encryption to improve threshold DSA signatures for Bitcoin wallet security[C]//Proceedings of the 5th International Conference on Cryptology and Information Security in Latin America. Berlin: Springer, 2017: 352-377.

    [10]

    LINDELL Y. Fast secure two-party ECDSA signing[C]//Proceedings of 37th Annual International Cryptology Conference. Berlin: Springer, 2017: 613-644.

    [11]

    DOERNER J, KONDI Y, LEE E, et al. Secure two-party threshold ECDSA from ECDSA assumptions[C]//Proceedings of 2018 IEEE Symposium on Security and Privacy (SP). San Francisco: IEEE, 2018: 980-997.

    [12]

    CHOU T, ORLANDI C. The simplest protocol for oblivious transfer[C]//Proceedings of the 1st International Confe-rence on Cryptology and Information Security in Latin America. Berlin: Springer, 2015: 40-58

    [13]

    KELLER M, ORSINI E, SCHOLL P. Actively secure OT extension with optimal overhead[C]//Proceedings of 35th Annual Cryptology Conference. Berlin: Springer, 2015: 724-741.

    [14] 王婧, 吴黎兵, 罗敏, 等. 安全高效的两方协同ECDSA签名方案[J]. 通信学报, 2021, 42(2): 12-25. https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB202102002.htm

    WANG J, WU L B, LUO M, et al. Secure and efficient two-party ECDSA signature scheme[J]. Journal on Communications, 2021, 42(2): 12-25. https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB202102002.htm

    [15]

    PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]//Proceedings of 99th International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1999: 223-238.

    [16]

    DESMEDT Y, FRANKEL Y. Shared generation of authenticators and signatures(extended abstract)[C]//Advances in Cryptology—CRYPTO'91. Berlin: Springer, 1991: 457-469.

  • 期刊类型引用(3)

    1. 李莉,宣佳铮,高尚,郭国疆. 基于不经意多项式估值的SM4协同加解密方案. 计算机应用研究. 2024(06): 1862-1868 . 百度学术
    2. 薛庆水,卢子譞,马海峰,高永福,谈成龙,孙晨曦. 基于SM2的强前向安全性两方共同签名方案. 计算机工程与设计. 2024(08): 2290-2297 . 百度学术
    3. 马文琪,孙传恒,罗娜,徐大明,邢斌. 基于区块链的远洋捕捞产品新鲜度评价与可信追溯模型研究. 农业机械学报. 2024(09): 428-441 . 百度学术

    其他类型引用(0)

图(3)  /  表(1)
计量
  • 文章访问数:  380
  • HTML全文浏览量:  204
  • PDF下载量:  64
  • 被引次数: 3
出版历程
  • 收稿日期:  2021-04-22
  • 网络出版日期:  2022-09-21
  • 刊出日期:  2022-08-24

目录

/

返回文章
返回