在公钥密码技术领域中，密钥对于密码算法来说至关重要，私钥的安全决定着系统以及敏感信息的安全，一旦公钥系统中的私钥被泄露或者丢失，不仅会造成系统出现单点故障，而且在恶意攻击者获得用户私钥之后就可以轻松地获取并篡改敏感信息。由此，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.   预备知识

在本文中，循环群G的阶为素数q，有限域F_p有p个元素，由其中的元素可定义有限域F_p上的一条椭圆曲线E，P为椭圆曲线E上的一个基点; x←X表示从集合X中(或者是从X分布中)随机均匀采样x; H(·)表示哈希杂凑函数，其表现形式为H: {0, 1}^*→Z_q; 对于一个整数$N, \mathbb{Z}_N=\{1, 2, \cdots, N-1\}$, $\mathbb{Z}_N^*=\{x \mid 0 < x < N且\operatorname{gcd}(x, N)=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←Z_q;

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

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

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

(5) 计算签名$s=k^{-1}(H(M)+x r) \bmod q$，若s=0，则重新从第(1)步开始执行;

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

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

(1) 计算sP+H(M)Q=(x₁, y₁);

(2) 当且仅当x₁mod q==r时，验证成功。

1.2   Paillier同态加密方案

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

(1) 密钥生成算法PK：任选2个长度相同且满足$\operatorname{gcd}(p q,(p-1)(q-1))=1$的大素数p和q，然后计算N=pq，令$\lambda$(N)=lcm(p-1, q-1)为N的卡迈可尔函数，并且任意选择整数$g \in \mathbb{Z}_{N^2 }^*$。令L(x)=(x-1)/N，计算$\mu=\left(L\left(g^{\lambda(N)} \bmod N^2\right)\right)^{-1} \bmod N$。生成Paillier加密方案的公钥ppk=(N, g)，私钥$\mathrm{psk}= (\lambda(N), \mu)$。

(2) 加密算法PE：选择随机数$r \in \mathbb{Z}_N^*$，然后计算密文$C=E(m, r)=g^m r^N \bmod N^2$，其中$m \in \mathbb{Z}_N$为待加密信息。

(3) 解密算法PD：针对密文C，对其进行解密得到明文$m=L\left(C^\lambda \bmod N^2\right) \times \mu \bmod N$。

Paillier加密方案满足加法同态加密性质。对于任意2个明文$a, b \in \mathbb{Z}_N$，其对应的密文分别为$e_a=$ $\operatorname{PE}(\mathrm{ppk}, a)=g^a r_1^N \bmod N^2$和$e_b=\mathrm{PE}(\mathrm{ppk}, b)=g^b r_2^N\bmod N^2$，其中随机数$r_1, r_2 \in \mathbb{Z}_n^*$。定义$e_a \otimes e_b=\left(e_a \times\right.$ $\left.e_b\right) \bmod N^2=g^a\left(r_1\right)^N \otimes g^b\left(r_2\right)^N=g^{a+b}\left(r_1 r_2\right)^N \bmod N^2=$ $\operatorname{PE}(a+b)$，则$e_a \otimes e_b$为a+b的密文。定义$\left(e_a\right)^b= \underbrace{e_a \otimes e_a \otimes \cdots \otimes e_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$^{\lambda}$，每个参与签名的成员P_i会获得公钥Pk以及对应的私钥份额sk_i，则sk₁, sk₂, …, sk_n是关于私钥sk的(t, n)门限秘密共享。

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

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

1.4   安全模型和定义

1.4.1   敌手模型

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

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

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

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

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

1.4.2   安全定义

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

定义2   ((t, n)门限签名方案的不可伪造性)令ε=(Thresh-KeyGen, Thresh-Sig, Ver)为(t, n)门限签名方案，称其是不可伪造的，如果敌手$\mathcal{A}$可以自适应地选择k次待签名信息M₁, M₂, …, M_k进行门限签名查询之后，能够在新的待签名信息$M^{\prime}\left(M^{\prime} \notin\right. \left.\left\{M_1, M_2, \cdots, M_k\right\}\right)$上伪造有效的门限签名的概率是可忽略的。

2.   高效的两方ECDSA门限方案

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

2.1   密钥生成算法TPKG

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

图  1  密钥生成算法TPKG

Figure  1.  The key generation algorithm TPKG

下载: 全尺寸图片 幻灯片

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

Step 2. 用户U₁将子公钥片P₁和子私钥同态加密密文ex₁发送给用户U₂。

Step 3. U₂同样随机选择x₂←Z_q作为子私钥，并计算子公钥片P₂=x₂·P。

Step 4. 用户U₂将子公钥片P₂发送给用户U₁。

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

Step 6. 用户U₂在收到用户U₁发送的公钥份额P₁后，计算公钥Pk=P₁+P₂，并存储参数{Pk, P₁, ppk, ex₁}。

2.2   两方签名算法TPsign

签名生成阶段包括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. 用户U₁生成随机数k₁←Z_q，并计算R₁=k₁·P;

Step 2. 用户U₁将R₁发送给用户U₂;

Step 3. 用户U₂选择随机数k₁←Z_q，b←Z_q和ρ←Z_q2;

Step 4. 用户U₂计算R₂=k₂·P;

Step 5. 用户U₂计算t=k₂^-1 mod q;

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

Step 7. 用户U₂进行同态操作$\overline{\mathrm{ex}}_1=\left(e_b \otimes x_1\right)^t$;

Step 8. 用户U₂利用从用户U₁获得的R₁计算(x, y)=k₂·R₁;

Step 9. 计算r=x mod q;

Step 10. 用户U₂将$\overline{\mathrm{ex}}_1$、R₂发送给用户U₁;

Step 11. 用户U₁利用从用户U₂获得的R₂计算(x, y)=k₁·R₂;

Step 12. 计算r=x mod q;

Step 13. 用户U₁利用同态加密方案中的私钥进行解密，获得$\bar{x}$=PD(psk, $\overline{\mathrm{ex}}_1$);

Step 14. 用户U₁存储参数{x₁, Pk, ppk, psk, r, $\bar{x}$, k₁};

Step 15. 用户U₂存储参数{x₂, Pk, ppk, ex₁, k₂, r, b}。

算法2   在线签名算法

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

Step 2. 用户U₂在本地计算部分签名片ps=k₂^-1(h+x₂·r-b·r) mod q;

Step 3. 用户U₂将ps发送给用户U₁;

Step 4. 用户U₁计算对消息的正式签名s=k₁^-1(ps+${\bar x}$·r)mod q;

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

2.3   签名验证

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

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

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

3.   方案分析

3.1   正确性分析

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

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

此外, sk=x₁+x₂，k=k₁·k₂, 可得

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

3.2   安全性分析

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

下面给出可模拟的概念。

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

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

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

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

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

情形1:用户U₁被攻击。假设敌手$\mathcal{A}_1$攻击并控制了用户U₁，再构造模拟器$\mathcal{S}im_1$来模拟用户U₂，通过提取用户U₁的输入，生成一个敌手不可区分的交互视图。

(1) 模拟密钥生成。假设敌手$\mathcal{A}_1$破坏了用户U₁，则由于模拟器$\mathcal{S}im_1$知道用户U₁的私钥份额x₁及系统的公钥Pk，模拟器可以通过计算P₂=Pk-x₁·P，模拟出用户U₂在密钥生成算法TPKG中输出公钥Pk的视图。由于模拟器知道私钥份额x₁，所以也可以计算出ex₁=PE(ppk, x₁)。因此，密钥生成算法TPKG是可模拟的。

(2) 模拟签名生成。

① 模拟器$\mathcal{S}im_1$接受一个关于消息M的ECDSA签名σ=(r, s);

② 模拟器$\mathcal{S}im_1$使用ECDSA验证算法来计算R=s·P+r·Pk;

③ 若第1条会话信息被解析为验证R₁=k₁·P，则模拟器$\mathcal{S}im_1$令R₂= k₁^-1 ·R，否则模拟器$\mathcal{S}im_1$随机地选取R₂;

④ 第2条会话信息被解析为R₂、$\overline{\mathrm{ex}}_1$、ps。模拟器$\mathcal{S}im_1$随机选取ps的值并计算${\bar x}$=s·k₁-ps，则可以由计算出传递的信息$\overline{\mathrm{ex}}_1$=PE(ppk,${\bar x}$);

⑤ 模拟器$\mathcal{S}im_1$输出正确的ECDSA签名σ=(r, s)并终止模拟签名过程。

观察以上模拟的交互过程可知，敌手$\mathcal{A}_1$的视图分布与真实协议执行环境下的输出是不可区分的。究其原因为：在交互过程中计算公钥Pk时，真实协议执行中，是由诚实用户U₂随机选择私钥份额x₂，计算公钥片P₂=x₂·P; 在模拟过程中，模拟器$\mathcal{S}im_1$计算公钥片P₂=Pk-x₁·P。由于Pk是随机选择的，故x₂·P和Pk-x₁·P是同分布的。因此，模拟器$\mathcal{S}im_1$的输出与诚实用户U₂的输出分布是相同的。

在签名阶段, 敌手$\mathcal{A}_1$的视图分布与真实协议执行环境下的不同之处在于ex₁、$\overline{\mathrm{ex}}_1$和ps的生成方式。具体来说：(1)在模拟执行环境中，R₂= k₁^-1·R，其中k₁是随机数。但是在真实环境中R₂=k₂·P，其中，k₂是随机数。因为敌手无法获取k₂的信息，所以二者都满足均匀随机分布，敌手无法有效区分这2种情况。(2)在真实环境下计算$\overline{\operatorname{ex}}_1=\left(e_b \otimes \operatorname{ex}_1\right)^t$，其中t=k₂^-1 mod q，而模拟器$\mathcal{S}im_1$使用随机选取的ps，然后计算${\bar x}$=(s·k₁-ps)，便可以得到传递的信息$\overline{\mathrm{ex}}_1$= PE(ppk, ${\bar x}$)。显然，真实环境与模拟执行环境下生成的签名都为σ=(r, s)，敌手无法做出区分。综上所述，对于敌手$\mathcal{A}_1$来说，真实的签名协议执行过程和模拟的执行过程是无法区分的。

情形2:用户U₂被攻击。假设敌手$\mathcal{A}_2$攻击并控制了用户U₂，现在构造模拟器$\mathcal{S}im_2$来模拟用户U₁，通过提取用户U₂的输入，生成一个敌手不可区分的交互视图。

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

(2) 模拟签名生成。

① 模拟器$\mathcal{S}im_2$接受一个关于消息M的ECDSA签名σ=(r, s)。

② 模拟器$\mathcal{S}im_2$使用ECDSA算法来计算点R=s·P+r·Pk，并向敌手$\mathcal{A}_2$发送指令，指示其开始执行签名协议。

③ 第1条会话消息被解析为敌手$\mathcal{A}_2$向模拟器$\mathcal{S}im_2$发送R₂，模拟器$\mathcal{S}im_2$验证是否满足R₂=k₂·P，且判断R₂是否为椭圆曲线上的非零点。若不成立，模拟器$\mathcal{S}im_2$中止协议; 否则，模拟器$\mathcal{S}im_2$计算R₁=k₂^-1·R并发送给敌手$\mathcal{A}_2$。

④ 第2条会话信息被解析为：模拟器$\mathcal{S}im_2$计算ps=k₂^-1(h+x₂·r-b·r) mod q和$\overline{\operatorname{ex}}_1=\left(e_b \otimes \operatorname{ex}_1\right)^t$。

⑤ 第3条会话消息被解析为和ps，模拟器$\mathcal{S}im_2$设置给敌手$\mathcal{A}_2$的预言机回答为s。

若敌手$\mathcal{A}_2$诚实执行协议，则会输出正确的ECDSA签名σ=(r, s)。

观察以上模拟的交互过程可知，敌手$\mathcal{A}_2$的视图分布与真实协议执行环境下密钥生成阶段的输出是不可区分的，与用户U₂被攻击的情况相似，由于Pk是随机选择的，故x₁·P和Pk-x₂·P是同分布的。因此，其密钥生成协议是可模拟的。

在签名过程中，具体来说：(1)在模拟执行环境中，R₁= k₂^-1 ·R; 在真实环境中, R₁=k₁·P, 其中k₁为随机数。因为敌手无法获取k₁的信息，所以二者都满足均匀随机分布，敌手无法有效区分这2种情况。因此，其签名生成协议是可模拟的。(2)在真实环境中，$\overline{\operatorname{ex}}_1=\left(e_b \otimes \operatorname{ex}_1\right)^t$，其中，ex₁=PE(ppk, x₁)，t=k₂^-1 mod q。而在模拟环境中, 由于用户U₂的信息都被暴露，包括b、k₂、x₂，所以与真实环境下的执行结果是一样的。由于签名预言机生成的(r, s)一定满足随机均匀的特性，且k₁也是随机选择的，两者的执行结果对于敌手$\mathcal{A}_2$来说都是一样的。

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

3.3   效率分析

在现有的两方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)在密钥生成阶段：在本文方案中，用户U₁计算P₁=x₁·P和ex₁=PE(ppk, x₁)，计算时间为1·T_d+1·T_p; 用户U₂计算P₂=x₂·P，计算时间仅为1·T_d。而在LINDELL方案中，用户U₁计算Q₁= x₁·P，Q=x₁·Q₂和Paillier加密操作c_key=Enc_pk(x₁)，计算时间为2·T_d+1·T_p; 用户U₂计算Q₂=x₂·P和Q=x₂·Q₁，计算时间仅为2·T_d。(2)在离线预计算阶段：在本文方案中，用户U₁计算R₁=k₁·P和x, y=k₁·R₂，并对$\overline{\mathrm{ex}}_1$进行解密${\bar x}$=PD(psk, $\overline{\mathrm{ex}}_1$)，计算时间为2·T_d+1· T_p; 用户U₂计算R₂=k₂·P和(x, y)=k₂· R₁，并进行Paillier加密操作e_b=PE(ppk, b+ρq)和Paillier同态操作$\overline{\operatorname{ex}}_1=\left(e_b \otimes \operatorname{ex}_1\right)^t$，计算时间为2·T_d+2· T_p。在LINDELL方案中，用户U₁计算R₁=k₁·P和R=k₁·R₂, 计算时间为2·T_d; 用户U₂计算R₂=k₂·P和R= k₂·R₁，并进行同态操作C₂=k₂^-1·x₂·r⊙c_key，计算时间共计2·T_d+1·T_p。(3)在在线签名阶段：在本文方案中，用户U₁、U₂都只需要进行线性运算，所以两方在此阶段的点乘运算次数为0。在LINDELL方案中，用户U₁需要对接收的密文C₃进行同态解密，计算时间为1·T_p; 用户U₂需要对信息加密C₁=Enc_pk(ρ·q+[k₂^-1 ·m′ mod q])，计算时间为1·T_p。综上可知，由于本文方案在离线预计算阶段完成了绝大部分计算量，从而在线签名时仅需要简单的操作，而LINDELL方案在线计算还需要一些Paillier加密操作。相比之下, 本文方案在线签名阶段的计算量是几乎可以忽略的。

表  1  2种方案的计算效率

Table  1.  The calculation efficiency of the two schemes

签名阶段	本文方案			LINDELL方案
	U1	U2		U1	U2
密钥生成阶段	1·Td+1·Tp	1·Td		2·Td+1·Tp	2·Td
离线预计算	2·Td+1·Tp	2·Td+2·Tp		2·Td	2·Td+1·Tp
在线签名	0	0		1·Tp	1·Tp

下载: 导出CSV 

| 显示表格

4.   结论

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