A Compute Perspective of MPC-TSS: Paillier in ECDSA Revisited

Multi-Party Computation (MPC) as a technology has seen promising growth and wider adoption, in large part due to interest fueled by recent attacks exploiting single points of failure in managing private keys. High-profile failures of centralized entities (like FTX, most recently) have particularly added to the interest in shifting towards decentralized financial products, where user empowerment is of utmost concern.

This is part of a series of blogs wherein we will shed light on recent developments in distributed authentication, understand the constraints of applications, and discuss problems that we solve.

The history of MPC dates back to the 1980s, when several foundational results [Yao86, BGW88, GMW86, CCD88] established its feasibility. Threshold Signatures Schemes (TSS), an application of MPC with tailored protocols, enjoys broad deployment in enterprise settings today. The protocols of Lindell, GG19, GG20, CMP to name a few, are used to decentralize key management for the ECDSA Signature Scheme. In this series of blog posts, we will explore an alternative approach to distributing ECDSA signatures, namely the ‘DKLs’ protocols: DKLs18, DKLs19, capable of achieving a different efficiency profile that we find better suited to build our key management solutions.

Silence Laboratories has had the pleasure of discussing the future in TSS an author of the DKLs series of papers - Yashvanth Kondi, who (disclosure) also leads Silence Laboratories’s research and technical aspects of cryptographic protocols.

In the foundational Bitcoin whitepaper [Bitcoin], Satoshi Nakamoto specified the ECDSA scheme with the secp256k1 curve to be used as the canonical signature scheme for the Bitcoin protocol. This choice has obvious merits — ECDSA produces compact signatures that are fast to generate and verify. In addition, it has withstood decades of cryptanalysis and enjoys wide compatibility across audited libraries. However, its non-linear structure has famously posed a challenge for MPC protocol designers aiming to decentralize its computation.

A. A Recap of Threshold Signatures

MPC enables a set of parties that do not trust each other, to jointly compute a function over the combination of their individual private inputs. Threshold signatures are a special case of MPC where the function to be computed is a cryptographic digital signature, and the private inputs are secret shares of the signing key.

Threshold Signature protocols vary in complexity depending on the structure of the signature scheme in consideration; they can be straightforward and non-interactive as in the case of BLS (Boneh, Lynn, and Shacham), mildly interactive (but technically simple) as in the case of EdDSA/Schnorr, or relatively complex, using sophisticated cryptographic primitives such as secure multiplication and zero-knowledge proofs, as in the case of ECDSA.

In general, Threshold Signatures have three phases:

• Distributed Key Generation (DKG),
• Distributed Signing, and
• Pro-activization i.e. Key rotation/refresh.

Each phase has its own distinct set of cryptographic operations and interaction patterns amongst computing nodes that hold shares of the signing key. These nodes can be any device with sufficient computational and memory capability, including smartphones, server nodes, and edge devices.

B. Threshold ECDSA Signing

As mentioned earlier, protocols to distribute ECDSA signing are relatively complex, especially as compared to EdDSA/Schnorr signatures which can be decentralized with a simple three-round protocol [Lin22]. However ECDSA was broadly standardized decades ago, and is used across the industry today (including in Bitcoin, Ethereum, etc.) — decentralization was not a ‘top-priority’ concern during standardization.

Modern MPC protocols are typically designed modularly, with complex tasks being encapsulated in self-contained subroutines. Protocols for ECDSA signing become much simpler to construct given a subroutine for “secure multiplication”, which we will refer to as ‘MUL’ henceforth.

Roughly, the MUL subroutine is run between a pair of parties, say, Alice and Bob, who input private integers ‘a’ and ‘b’ respectively, and receive randomly distributed private outputs ‘u’ and ‘v’ that respect the correlation: ‘u+v=a*b’.

Instantiating such an MUL subroutine is where much of the complexity lies, and one common approach to this problem is via Paillier’s encryption scheme [Pai99].

C. Threshold ECDSA with Paillier Encryption

Paillier-based MUL instantiations are used in several deployed protocols to distribute ECDSA [Lindell 17, GG18, GG20] and are typically accompanied by zero-knowledge proofs (ZKPs) to validate their correct usage. Paillier encryption comes from the family of integer factoring-based cryptography, unlike ECDSA which is based on Elliptic Curves. This mismatch broadens the trustbase of the overall system in terms of mathematical assumptions, as well as requiring more audited and battle-tested libraries (implementing and auditing factoring-based cryptography comes with its own challenges).

Well-chosen Elliptic Curves are believed to be ‘optimally’ secure — i.e. no attacks better than generic brute force are known — meaning that schemes like ECDSA are safe to use with small, tight parameters. Concretely, most deployments of ECDSA today, operate over 256-bit integers. In contrast, integer-factoring is known to admit solutions better than generic brute force, meaning that concrete parameters have to be inflated to account for such attacks.
In practice, this means operating over integers that are over an order of magnitude larger than elliptic curves in bitlength; the Paillier cryptosystem (including encryption and ZKPs) involves arithmetic with integers that are thousands of bits in size, which is of course much more demanding of computational resources. Using Paillier encryption for threshold ECDSA therefore, considerably burdens the low computational footprint that made ECDSA itself a good choice for many devices.

To develop a better understanding of the performance of Paillier-based MUL in the ECDSA context, we ran benchmarks with a Java TSS library on a diverse set of hardware — including a range of phones and edge devices such as smartwatches. The TL;DR is that the time for Paillier-based key generation exists in the range of 100s of microseconds, and up to 1 full second for a few phones. As the number of parties grows, the aggregated time is in full seconds and accounts for more than 50% of the time taken in the whole protocol. Figure 1 provides further insight into the results of our benchmarks.

‍

Further, we studied how the same library would perform on edge devices such as smartwatches. We ran our {2, 2} TSS wherein the shards were held between a phone and a watch. As shown in Figure 2, Paillier key generation alone takes close to 2 seconds on the smartwatch, and the total time for key generation becomes very perceptible by the user. Putting it together, employing Paillier-MUL in user-facing applications and running on commercial of-the-shelf devices would induce substantial latency, which we would like to avoid as an industry.

D. An Alternative to Paillier: OT-MUL via DKLs

MUL is a fundamental MPC building block, and today’s literature is rich with approaches for its instantiation. Rather than building protocols on top of Paillier-based MUL, the threshold ECDSA protocols of Doerner (et al.) [DKLs18, DKLs19] instead make use of Oblivious Transfer (OT) to construct MUL, which we will refer to as OT-MUL henceforth. At a high level, they harden and use Gilboa’s OT-based secure multiplication protocol [Gil99], which when combined with OT ‘Extension’ [Roy22], incurs a computation cost of a few thousand hashes — only a few milliseconds on modern hardware. Their protocol additionally makes use of a few simple consistency checks that obviate the need for any zero-knowledge proofs, while retaining a high-security guarantee.

Unlike Paillier’s encryption scheme, OT-MUL can be built from the same elliptic curve and hash function as ECDSA itself. This means that integer computations stay small, and factoring-based cryptography (with its separate mathematical assumptions and implementation/audit complexity) is not needed.

We will dive deeper into the technical details in a future post, but the takeaway, for now, is that the DKLs protocols achieve an efficiency profile that is much lighter on computation than any approach that uses Paillier-based MUL.

Of course, nothing comes for free; the DKLs protocols pay a higher bandwidth cost for OT-MUL. However, our benchmarks show that it is a worthwhile tradeoff to make in many real-world deployment scenarios, including our MPC-based wallet solutions — especially given the proliferation of high-speed connectivity today. In particular, we are able to construct an MPC-based self-custody wallet that, even when using low-budget smart devices, is able to complete signing with latency that is barely perceptible to the user.

Inour upcoming posts, we will also explore other usability concerns that are directly impacted by the DKLs protocols’ smaller computation footprint, including memory and battery consumption. We hope that the insights we provide will serve as a useful reference for designers and architects of scalable TSS solutions.

We welcome you to join in the discussion, collaborate and build together. Please write to us on email or by booking a slot to discuss things, through our Calendly here.

ABOUT US

Silence Laboratories is a deep-tech, decentralized, authentication-infrastructure (MPC-focused) provider that offers developer-focused SDKs and libraries, for protocols, wallets, and projects that can be used to embed/build distributed, zero-trust authentication and authorization products, alike. We aim to be a defacto MPC and Proofing product suite for other builders to build on top of. For ease of integration, we are application, protocol, custodian, and stack agnostic, collaboration-friendly, and future-forward.

References:

1. [Yao86] A. Yao. How to generate and exchange secrets. In Proc. FOCS, pages 162–167, 1986.
2. [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.
3. [GMW86] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC, 1987.
4. [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
5. [Pai99] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.
6. [Lindell 17] Yehuda Lindell. Fast secure two-party ECDSA signing. In CRYPTO, 2017.
7. Lin22] Yehuda Lindell. Simple three-round multiparty schnorr signing with full simulatability. Cryptology ePrint Archive, 2022.
8. [GG 18] Rosario Gennaro and Steven Goldfeder. Fast multiparty threshold ECDSA with fast trustless setup. In CCS, 2018.
9. [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.
10. [Roy22] Lawrence Roy. Softspokenot: Communication–computation tradeoffs in OT extension. Cryptology ePrint Archive, Report 2022/192, 2022. https://ia.cr/2022/192.
11. [Gil99] Niv Gilboa. Two-party RSA key generation. In CRYPTO, 1999
12. [DKLs18] Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Secure two-party threshold ECDSA from ECDSA assumptions. In IEEE S&P, 2018
13. [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.
14. [Bitcoin] https://bitcoin.org/bitcoin.pdf
15. [CMP] https://eprint.iacr.org/2020/492

‍

‍

‍