MPC-TSS的计算视角：ECDSA中Paillier的再思考

MPC-TSS 的计算视角：重新审视 ECDSA 中的 Paillier

Yashvanth、Jay 以及 Silence Laboratories 的成员

多方计算 (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 的密码协议研究和技术方面。

在 Bitcoin 基础性白皮书中 [Bitcoin]，Satoshi Nakamoto 指定 ECDSA 方案与 secp256k1 曲线一起用作 Bitcoin 协议的规范签名方案。这种选择具有明显的优点——ECDSA 产生紧凑的签名，可以快速生成和验证。此外，它经受了数十年的密码分析，并在经过审核的库中享有广泛的兼容性。然而，它的非线性结构对于旨在分散其计算的 MPC 协议设计者来说，提出了著名的挑战。

A. 阈值签名回顾

MPC 使一组互不信任的参与方能够联合计算其各个私有输入的组合上的函数。 阈值签名是 MPC 的一种特殊情况，其中要计算的函数是密码数字签名，而私有输入是签名密钥的秘密共享。

阈值签名协议的复杂性因所考虑的签名方案的结构而异； 它们可以像 BLS（Boneh、Lynn 和 Shacham）那样简单且非交互，像 EdDSA/Schnorr 那样轻微交互（但在技术上很简单），或者相对复杂，使用复杂的密码原语，例如安全乘法和零知识证明，如 ECDSA 的情况。

一般来说，阈值签名有三个阶段：

• 分布式密钥生成 (DKG)，
• 分布式签名，以及
• 主动化，即密钥轮换/刷新。

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

B. 阈值 ECDSA 签名

如前所述，分配 ECDSA 签名的协议相对复杂，尤其是与 EdDSA/Schnorr 签名相比，EdDSA/Schnorr 签名可以使用简单的三轮协议进行去中心化 [Lin22]。 然而，ECDSA 早在几十年前就已得到广泛标准化，并且如今已在整个行业中使用（包括在 Bitcoin、以太坊等中）——去中心化在标准化期间并不是“重中之重”的考虑因素。

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

大致来说，MUL 子程序在两个参与方（例如 Alice 和 Bob）之间运行，他们分别输入私有整数“a”和“b”，并接收随机分布的私有输出“u”和“v”，这些输出尊重相关性：“u+v=a*b”。

实例化这样的 MUL 子程序是大部分复杂性所在，解决这个问题的一种常见方法是通过 Paillier 加密方案 [Pai99]。

C. 使用 Paillier 加密的阈值 ECDSA

基于 Paillier 的 MUL 实例化用于多个已部署的协议中，以分配 ECDSA [Lindell 17, GG18, GG20]，并且通常伴随有零知识证明(ZKP) 以验证其正确使用。 Paillier 加密来自基于整数分解的密码学系列，这与基于椭圆曲线的 ECDSA 不同。 这种不匹配扩大了整体系统在数学假设方面的信任基础，并且需要更多经过审核和实战检验的库（实现和审核基于分解的密码学有其自身的挑战）。

人们认为精心选择的椭圆曲线是“最佳”安全的——即，没有比通用暴力破解更好的攻击方式是已知的——这意味着像 ECDSA 这样的方案可以安全地与小型、紧凑的参数一起使用。 具体来说，如今 ECDSA 的大多数部署都在 256 位整数上运行。 相比之下，已知整数分解允许比通用暴力破解更好的解决方案，这意味着必须增加具体的参数以应对此类攻击。

在实践中，这意味着在大于椭圆曲线的位长度一个数量级以上的整数上进行运算； Paillier 密码系统（包括加密和 ZKP）涉及对数千位大小的整数进行算术运算，这当然对计算资源的要求更高。 因此，将 Paillier 加密用于阈值 ECDSA 会大大增加低计算占用空间，这使得 ECDSA 本身成为许多设备的一个不错的选择。

为了更好地理解基于 Paillier 的 MUL 在 ECDSA 上下文中的性能，我们在各种硬件上使用 Java TSS 库运行了基准测试——包括一系列手机和边缘设备（例如智能手表）。 简而言之，基于 Paillier 的密钥生成时间存在于 100 微秒到 1 整秒之间（对于少数手机）。 随着参与方数量的增加，总时间以整秒为单位，并且占整个协议所花费时间的 50% 以上。 图 1 进一步说明了我们的基准测试结果。

图 1：Silence Laboratories 在 200 多部智能手机（价格按升序排列）上进行的基准测试的示例快照

此外，我们研究了同一库在智能手表等边缘设备上的性能如何。 我们运行了我们的 {2, 2} TSS，其中分片保存在手机和手表之间。 如图 2 所示，仅 Paillier 密钥生成在智能手表上就需要接近 2 秒的时间，并且用户可以非常清楚地感觉到密钥生成的总时间。 综上所述，在面向用户的应用程序中采用 Paillier-MUL 并在商业现成设备上运行会产生大量的延迟，我们希望整个行业都能避免这种情况。

图 2：智能手机 (Realme X7) 和智能手表 (Fossil GEN 6) 之间的 TSS {2, 2} 的快照

D. Paillier 的替代方案：通过 DKLs 实现 OT-MUL

MUL 是 MPC 的基本构建块，今天的文献中有很多关于其实例化的方法。 Doerner（等人）[DKLs18, DKLs19] 的阈值 ECDSA 协议没有在基于 Paillier 的 MUL 之上构建协议，而是使用不经意传输(OT) 来构建 MUL，我们将在下文中将其称为 OT-MUL。 在较高的层次上，它们加强并使用 Gilboa 基于 OT 的安全乘法协议 [Gil99]，该协议与 OT“扩展”[Roy22] 结合使用时，会产生数千个哈希的计算成本——在现代硬件上只需几毫秒。 他们的协议还使用了一些简单的一致性检查，从而消除了对任何零知识证明的需求，同时保留了高安全性保证。

与 Paillier 的加密方案不同，OT-MUL 可以从与 ECDSA 本身相同的椭圆曲线和哈希函数构建。 这意味着整数计算保持**较小，并且不需要基于分解的密码学**(及其单独的数学假设以及实现/审核的复杂性) 。

我们将在以后的文章中更深入地研究技术细节，但目前的要点是，DKLs 协议实现的效率配置文件比任何使用基于 Paillier 的 MUL 的方法计算量要轻得多。

当然，没有什么是不需要成本的； DKLs 协议为 OT-MUL 支付了更高的带宽成本。 然而，我们的基准测试表明，在许多现实世界的部署场景中（包括我们基于 MPC 的钱包解决方案），这是一个值得做出的权衡——尤其是在当今高速连接激增的情况下。 特别是，即使在使用低成本的智能设备时，我们也能够构建一个基于 MPC 的自我托管钱包，该钱包能够以用户几乎感觉不到的延迟完成签名。

在我们即将发布的文章中，我们还将探讨其他可用性问题，这些问题直接受到 DKLs 协议较小的计算占用空间的影响，包括内存和电池消耗。 我们希望我们提供的见解可以作为可扩展 TSS 解决方案的设计者和架构师的有用参考。

https://eprint.iacr.org/2019/523.pdf

我们欢迎你加入讨论，协作和共同构建。 请通过 电子邮件 或通过我们的 Calend ly 在此处预订一个时段来讨论事情，写信给我们。

关于我们

Silence Laboratories 是一家专注于 MPC 的深层技术、去中心化身份验证基础设施提供商，它提供以开发者为中心的 SDK 和库，适用于协议、钱包和项目，这些 SDK 和库可用于嵌入/构建分布式、零信任身份验证和授权产品。 我们的目标是成为其他构建者在其之上构建的事实上的 MPC 和验证产品套件。 为了便于集成，我们不依赖于应用程序、协议、托管和堆栈，与协作友好，并且面向未来。

参考：

1. [Yao86] A. Yao. 如何生成和交换秘密。 在 Proc. FOCS，第 162-167 页，1986 年。
2. [BGW88] Michael Ben-Or、Shafi Goldwasser、Avi Wigderson：非密码容错分布式计算的完备性定理（扩展摘要），1988 年。在 STOC '88 第二十届 ACM 计算理论年会论文集中。
3. [GMW86] O. Goldreich、S. Micali 和 A. Wigderson。 如何玩任何智力游戏。 在 STOC，1987 年。
4. [CCD88] David Chaum、Claude Crépeau、Ivan Damgård：多方无条件安全协议。 在 STOC '88 第二十届 ACM 计算理论年会论文集中
5. [Pai99] Pascal Paillier。 基于复合度剩余类的公钥密码系统。 在 EUROCRYPT，1999 年。
6. [Lindell 17] Yehuda Lindell。 快速安全的两方 ECDSA 签名。 在 CRYPTO，2017 年。
7. Lin22] Yehuda Lindell。 具有完全可模拟性的简单三轮多方 Schnorr 签名。 密码学电子预印本档案，2022 年。
8. [GG 18] Rosario Gennaro 和 Steven Goldfeder。 具有快速无信任设置的快速多方阈值 ECDSA。 在 CCS，2018 年。
9. [GG 19] [GG20] Rosario Gennaro 和 Steven Goldfeder。 具有可识别中止的一轮阈值 ECDSA。 密码学电子预印本档案，报告 2020/540，2020 年。http://eprint.iacr.org/2020/540.
10. [Roy22] Lawrence Roy。 Softspokenot：OT 扩展中的通信-计算权衡。 密码学电子预印本档案，报告 2022/192，2022 年。https://ia.cr/2022/192.
11. [Gil99] Niv Gilboa。 两方 RSA 密钥生成。 在 CRYPTO，1999 年
12. [DKLs18] Jack Doerner、Yashvanth Kondi、Eysa Lee 和 Abhi Shelat。 来自 ECDSA 假设的安全双人阈值 ECDSA。 在 IEEE S&P，2018 年
13. [DKLs19] Doerner, J., Kondi, Y., Lee, E., & Shelat, A. (2019, May). 来自 ECDSA 假设的阈值 ECDSA：多方案例。 在 2019 IEEE 安全与隐私研讨会 (SP)（第 1051–1066 页）。 IEEE。
14. [Bitcoin] https://bitcoin.org/bitcoin.pdf
15. [CMP] https://eprint.iacr.org/2020/492

• 原文链接： medium.com/silence-labor...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～