重新审视ECDSA中的Paillier算法

0

摘要

多方安全计算（MPC）有着广泛的应用，这主要是因为近期提出的攻击利用了管理私钥中的单点故障。集中式实体（例如，最近的FTX）的失败，使得人们增加了对分布式金融产品的兴趣，其中用户授权是最重要的关注点。

MPC的历史可以追溯到20世纪80年代，当时几个基础性的工作（如Yao86，BGW88，GMW86，CCD88）确立了它的可行性。阈值签名方案（TSS）是MPC的一种应用，目前在企业系统中得到广泛应用。Lindell，GG19，GG20，CMP等协议用于分散ECDSA签名方案的密钥管理。在本系列博客文章中，我们将探讨一种可以替代分发ECDSA签名的方法，即“DKLs”协议：DKLs18，DKLs19，能够实现不同的效率配置文件，我们认为这更适合构建我们的密钥管理解决方案。

Silence Laboratories很高兴与DKLs系列论文的作者Yashvanth Kondi讨论TSS的未来，他（披露）还领导着Silence Laboratories的研究和密码协议的技术方面。

在开创性的比特币白皮书中，Satoshi Nakamoto指定了ECDSA方案和secp256k1曲线作为比特币协议的规范签名方案。这个选择显然有很多优点-比如ECDSA可以产生紧凑的签名，并且生成和验证速度快。此外，它经受了几十年的密码分析，并且在经过审计的库中具有兼容性。然而，它的非线性结构对于试图分散其计算的MPC协议设计者来说一直是一个挑战。

1

阈值签名

MPC使一组相互不信任的参与方共同计算一个特定函数，并能保护各参与方的输入隐私。阈值签名是MPC的一种特殊情况，其中要计算的函数是密码数字签名，而私有输入是签名密钥的秘密份额。

根据所考虑的签名方案的结构，阈值签名协议的复杂性各不相同；它们可以是直接且非交互的，如BLS（Boneh，Lynn和Shacham）的情况，也可以是稍微交互（但技术上简单）的，如EdDSA/Schnorr的情况，或者相对复杂的，使用复杂的密码原语，如安全乘法和零知识证明，如ECDSA的情况。

一般而言，阈值签名有三个阶段：

分布式密钥生成（DKG），分布式签名，以及密钥轮换/刷新。

每个阶段都有自己独特的一组密码操作和计算节点之间的交互模式，这些节点持有签名密钥的份额。这些节点可以是具有足够计算和内存能力的任何设备，包括智能手机、服务器节点和边缘设备。

2

阈值ECDSA签名

如前所述，相对于可以通过简单的三轮协议[Lin22]实现分散化的EdDSA/Schnorr签名来说，分发ECDSA签名的协议相对复杂。然而，几十年前就已经定制了标准化的ECDSA，并且今天在行业中广泛使用（包括比特币、以太坊等）-在标准化过程中，分散化并不是一个“重要的优先”考虑因素。

现代MPC协议通常以模块化的方式设计，复杂的任务被封装在独立的子程序中。给定一个“安全乘法”的子程序，用于构建ECDSA签名的协议变得更简单，我们将其简称为“MUL”。

粗略地说，MUL子程序在一对参与方之间运行，例如Alice和Bob，他们分别输入私有整数“a”和“b”，并收到满足关系“u+v=a*b”的随机分发的私有输出“u”和“v”。

实例化这样一个MUL子程序是复杂性的主要问题，可以通过Paillier加密方案[Pai99]来解决这一问题。

3

使用Paillier加密的阈值ECDSA

基于Paillier的MUL实例在几个部署的协议中用于分发ECDSA [Lindell 17，GG18，GG20]，并且通常伴随着零知识证明（ZKPs）来验证其正确使用。Paillier加密来自基于整数集合的密码家族，而不是基于椭圆曲线的ECDSA。

这种不匹配在数学假设的整体系统中扩大了信任基础，并且需要更多经过审计和经过实战验证的库（实现和审计基于因子分解的密码学带来了自己的挑战）。

精心选择的椭圆曲线被认为是“最优安全”的-即没有比暴力破解更好的攻击方法-这意味着像ECDSA这样的方案在小而紧凑的参数下是安全的。具体而言，今天大多数的ECDSA部署都是在256位整数上操作的。相比之下，整数因子分解存在比暴力破解更好的解决方案，这意味着具体的参数必须足够大，才可以抵抗此类攻击。

实际上，这意味着操作的整数比椭圆曲线的位数多一个数量级；Paillier密码系统（包括加密和ZKPs）涉及与数千位大小的整数的算术运算，这对计算资源要求很高。因此，对于阈值ECDSA的Paillier加密来说，它会极大地增加ECDSA本身对许多设备而言的低计算占用量。

为了更好地了解Paillier-based MUL在ECDSA环境中的性能，我们在各种硬件上使用Java TSS库进行了基准测试，包括各种手机和智能手表等边缘设备。简而言之，Paillier-based密钥生成所需的时间在数百微秒的范围内，对于一些手机而言，最高可达1秒。随着参与方数量的增加，聚合时间达到整个协议所需时间的一半以上。图1进一步说明了我们基准测试结果的情况。

图1. 基准测试结果

此外，我们研究了同一库在智能手表等边缘设备上的性能。我们在手机和手表之间运行了我们的{2, 2} TSS，其中分片被保存在两者之间。如图2所示，Paillier密钥生成在智能手表上需要近2秒的时间，而密钥生成的总时间对用户来说非常明显。综合考虑，在用户面向的应用中使用Paillier-MUL并在商用设备上运行会引起相当大的延迟，而我们希望避免这种延迟作为一个行业。

图2. Paillier密钥生成时间

4

一种替代Paillier的方法：通过DKLs实现OT-MUL

MUL是一个基本的多方计算构建模块，现有文献中有很多方法可以实现它。DKLs18、DKLs19的门限ECDSA协议不是基于Paillier的MUL，而是利用Oblivious Transfer (OT)构建MUL，我们将其称为OT-MUL。在高层次上，他们通过Gilboa的基于OT的安全乘法协议以及OT Extension来加固和使用OT-MUL，这样的计算成本只需几千次哈希计算，对于现代硬件而言只需要几毫秒的时间。他们的协议还利用了一些简单的一致性检查来避免使用零知识证明，同时保持了很高的安全性保障。

与Paillier的加密方案不同，OT-MUL可以使用与ECDSA相同的椭圆曲线和哈希函数构建。这意味着整数计算保持较小，并且不需要基于因式分解的密码学（具有单独的数学假设和实施/审计复杂性）。

我们将在以后的文章中深入探讨技术细节，但目前的要点是，DKLs协议实现的效率比任何使用Paillier-based MUL的方法都要高。

当然，DKLs协议在OT-MUL方面付出了更高的带宽成本。然而，我们的基准测试显示，在许多实际部署场景，包括基于多方计算的钱包解决方案中，这是一个权衡。同样，我们能够构建一个基于多方计算的自托管钱包，即使使用低预算的智能设备，也能够以用户几乎感觉不到的延迟完成签名。

5

引用

• [Yao86] A. Yao. How to generate and exchange secrets. In Proc. FOCS, pages 162–167, 1986.
• [BGW88] Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (extended abstract), 1988. In STOC ’88 Proceedings of the twentieth annual ACM symposium on Theory of computing.
• [GMW86] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC, 1987.
• [CCD88] David Chaum, Claude Crépeau, Ivan Damgård: Multiparty Unconditionally Secure Protocols. In STOC ’88 Proceedings of the twentieth annual ACM symposium on Theory of computing
• [Pai99] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.
• [Lindell 17] Yehuda Lindell. Fast secure two-party ECDSA signing. In CRYPTO, 2017.
• Lin22] Yehuda Lindell. Simple three-round multiparty schnorr signing with full simulatability. Cryptology ePrint Archive, 2022.
• [GG 18] Rosario Gennaro and Steven Goldfeder. Fast multiparty threshold ECDSA with fast trustless setup. In CCS, 2018.
• [GG 19] [GG20] Rosario Gennaro and Steven Goldfeder. One round threshold ECDSA with identifiable abort. Cryptology ePrint Archive, Report 2020/540, 2020. http://eprint.iacr.org/2020/540.
• [Roy22] Lawrence Roy. Softspokenot: Communication–computation tradeoffs in OT extension. Cryptology ePrint Archive, Report 2022/192, 2022. https://ia.cr/2022/192.
• [Gil99] Niv Gilboa. Two-party RSA key generation. In CRYPTO, 1999
• [DKLs18] Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Secure two-party threshold ECDSA from ECDSA assumptions. In IEEE S&P, 2018
• [DKLs19] Doerner, J., Kondi, Y., Lee, E., & Shelat, A. (2019, May). Threshold ECDSA from ECDSA assumptions: the multiparty case. In 2019 IEEE Symposium on Security and Privacy (SP) (pp. 1051–1066). IEEE.
• [Bitcoin] https://bitcoin.org/bitcoin.pdf
• [CMP] https://eprint.iacr.org/2020/492

本文来源：

https://medium.com/silence-laboratories/a-compute-perspective-of-mpc-tss-paillier-in-ecdsa-revisited-3e7e92f4bd0a

作者：Jay Prakash

翻译：杨赟博

分享仅供学习参考，若有不当，请联系我们处理。

END

往期推荐

1.笔记分享 | 组队学习密码学（3）——隐私求交之不经意的伪随机函数构造
2.笔记分享 | 组队学习密码学（3）——隐私求交的关键路径及其应用3.课程报名丨2023年浙江大学暑期Crypto School系列课程4.综述 | 面向边缘智能的联邦学习