密码学 - Two-party ECDSA Signing - Cig01

Created: <2020-11-13 Fri>

Last updated: <2023-01-06 Fri>

Two-party ECDSA Signing

1. Two-party ECDSA 简介

“Two-party ECDSA”问题是指：由两方组成的群体共同完成 ECDSA 签名，可以看作是 2/2 门限签名。本文以 P1 和 P2 表示参与共同签名的两方。

1.1. 标准的 ECDSA

假设待签名的消息为 m ，其哈希为 H(m) ，用户的私钥为 x ，我们回顾一下标准的（只涉及一方的）ECDSA 签名算法：

1. 随机选择 k←Zp ；

2. 计算 R=k⋅G ；

3. 计算 r=rxmodq ，其中 rx 是 R 的 x 轴坐标；

4. 计算 s=k−1⋅(H(m)+r⋅x)modq 。

得到的 (r,s) 就是 ECDSA 签名数据。

2. MacKenzie-Reiter 方案

2001 年，MacKenzie 和 Reiter 在论文 Two-Party Generation of DSA Signatures（ full version）中提出了一个 Two-party ECDSA Signing 方案。

MacKenzie 和 Reiter 提出的思路如下：参与方 P1 随机生成 x1,k1 （和标准的 ECDSA 一样，其中 x1 是需要保存的，而 k1 是一次一用的），类似地参与方 P2 也随机生成 x2,k2 ，这两方所组成的群体的 k 和 x 分别由 k=k1⋅k2 和 x=x1⋅x2 得到，由于 P1 不能泄露 x1,k1 ，同样 P2 也不能泄露 x2,k2 ，所以不能直接得到群体的 k,x 。MacKenzie 和 Reiter 给出了一个方案，可以在各方不泄露自己秘密（即 xi,ki ）的情况下构造出群体私钥对消息的签名数据。

2.1. 群体公钥

在介绍如何构造群体签名数据前，先介绍一下如何得到群体的公钥 Q=x⋅G=x1⋅x2⋅G 。在各方不泄露各自秘密值 xi 的情况下，可以按图 1 所示方法求得 Q ，这是一个标准的 Diffie–Hellman key exchange 过程。

Figure 1: 运用 Diffie-Hellman 协议得到群体公钥 Q

P1 发送 Q1=x1⋅G 给 P2 （由 Q1 无法倒推出 P1 的秘密 x1 ），P2 拿了 Q1 再乘上 x2 就得到了群体公钥；类似地 P1 也可以得到群体公钥 Q 。

2.2. 群体签名数据 r 部分

由 ECDSA 知，群体签名数据 r 是 R=k1⋅k2⋅G 的 x 轴坐标，我们只需要求得群体 R 即可知道 r 。

和计算群体公钥 Q 类似，利用 Diffie-Hellman key exchange 方法 P1,P2 都可以得到群体的 R ，如图 2 所示。

Figure 2: 运用 Diffie-Hellman 协议得到群体 R

2.3. 群体签名数据 s 部分

群体签名数据的 s 部分的求解相对 r 的求解要麻烦一些，我们回顾下标准 ECDSA 的 s ： s=k−1⋅(H(m)+r⋅x)modq 换为两方共同完成签名后， s 的计算方式相应地调整为： s=(k1⋅k2)−1⋅(H(m)+r⋅x1⋅x2)modq

在确保 P1 不泄露 x1,k1 ，而 P2 不泄露 x2,k2 的情况下，如何计算群体签名数据的 s 部分呢？利用 Paillier Cryptosystem 的“同态加密”性质可以做到。

2.3.1. Paillier 加同态

Paillier Cryptosystem 是一种公钥密码算法。除此外，Paillier 还具备“加同态”性质。

Paillier 具备下面两个性质：

1. 仅已知公钥和两个加密后的消息 E(m1) 和 E(m2) ，不接触私钥（也就是说不解密）情况下，可以计算出两个明文 m1 和 m2 相加后再加密的结果，即 E(m1+m2) ；我们把同态相加记为 ⊕ ，也就是： E(m1+m2)=E(m1)⊕E(m2)

2. 仅已知公钥和密文 E(m1) 情况下，可以计算出 k⋅m1 的密文（这里 k 是常量），即 E(k⋅m1) ，我们把这个运算记为 ⊙ ，也就是： E(k⋅m1)=k⊙E(m1)

这两个性质很有用，可以帮助我们计算群体签名数据中的 s 部分。

2.3.2. 计算 s 的具体协议

有了前面介绍的 Paillier，我们可以确保 P1 不泄露 x1,k1 ，而 P2 不泄露 x2,k2 的情况下，计算群体签名数据的 s 了。

s=(k1⋅k2)−1⋅(H(m)+r⋅x1⋅x2)modq=k2−1⋅H(m)⋅k1−1+r⋅x2⋅k2−1k1−1⋅x1modq

上式中，红色部分是只有 P1 知道的，把它加密后，发送给 P2 ， P2 利用 Paillier 的同态加密性质在密文上构造出加密后的 s ，然后发送给 P1 ， P1 解密即可得到 s ，这个过程如图 3 所示。

Figure 3: 计算 s 的具体协议（简化版本）

2.4. MacKenzie-Reiter 方案的缺点

为了防止恶意参与者，Two-party ECDSA 协议需要确保“最终生成的群体签名是正确的”。 P1 需要在不泄露 k1 的情况下证明他向 P2 提供的加密数据中确实包含了 k1−1 ，这需要借助“零知识证明”来完成。 由于 P2 手头掌握的和 k1 相关的数据只有 R1=k1⋅G （并不包含 k1−1⋅G ），这个证明过程是很复杂的，涉及很多运算，代价比较大。

Yehuda Lindell 于 2017 年提出了另一种 Two-party ECDSA 方案，其零知识证明过程的代价比 MacKenzie-Reiter 方案要小。

3. Yehuda Lindell 方案

2017 年，Yehuda Lindell 在论文 Fast Secure Two-party ECDSA Signing 提出一个更快的 Two-party ECDSA 方案。除去零知识证明相关内容，和 MacKenzie-Reiter 方案的主要区别在于如何构造群体签名数据的 s 部分。

Yehuda Lindell 方案中构造群体公钥、群体签名数据 r 部分的方法和 MacKenzie-Reiter 方案是类似的，这里不介绍。

3.1. 群体签名数据 s 部分

Yehuda Lindell 方案中，构造群体签名数据 s 部分的流程如图 4 所示。

s=(k1⋅k2)−1⋅(H(m)+r⋅x1⋅x2)modq=(k2−1⋅H(m)+r⋅x2⋅k2−1⋅x1)k1−1modq

Figure 4: Yehuda Lindell 方案（构造群体签名数据的 s 部分）

这个流程中引入了随机数 ρ ，这是为了获得更好的安全性，由于在它出现的地方同时乘以了模数 q ，所以并不会影响到正确性。

3.2.x=x1+x2

前面的介绍中， P1 保存的秘密 x1 和 P2 保存的秘密 x2 的乘积 x1⋅x2 就是他们作为群体对外的私钥，即 x=x1⋅x2 。我们可以把相乘改为相加吗，即 x=x1+x2 ？答案是肯定的。不过协议要相应地调整，下文将具体介绍如何调整。

3.2.1. 群体公钥

和节 2.1 中介绍的方式有一点点区别。现在群体公钥的计算要调整为： Q=x⋅G=(x1+x2)⋅G=x1⋅G+x2⋅G=Q1+Q2

3.2.2. 群体签名数据 r 部分

由于 k=k1⋅k2 没有变化，所以群体签名数据 r 部分的构造没变化，参考节 2.2 。

3.2.3. 群体签名数据 s 部分

构造群体签名数据 s 部分的协议需要调整，如图 5 所示。

s=(k1⋅k2)−1⋅(H(m)+r⋅(x1+x2))modq=(k2−1⋅H(m)+r⋅k2−1⋅(x2+x1))k1−1modq

Figure 5: 采用 x=x1+x2 方式时，构造 s

3.3. 开源实现

在 blockchain-crypto-mpc 中有 Yehuda Lindell 方案的开源实现，在这个实现中，为了更方便地支持“ Share Refresh”（即在群体私钥不变的前提下实现 x1,x2 的更新），采用了 x=x1+x2 的方式。

在 multi-party-ecdsa 中也有 Yehuda Lindell 方案的开源实现，这个实现中，采用了原始论文 x=x1⋅x2 的方式，参考： https://github.com/ZenGo-X/gotham-city/blob/master/white-paper/white-paper.pdf

4. 参考

Fast Secure Two-party ECDSA Signing, 2017

Paper by Yehuda Lindell presented at Crypto 2017, YouTube

Two-Party Generation of DSA Signatures, 2011

ECDSA is not that bad: two-party signing without Schnorr or BLS

• 本文转载自： aandds.com/blog/two-part... , 如有侵权请联系管理员删除。