How We Implemented Our MPC-ECDSA Protocol at Utila

Our product utilizes several Multi-Party Computation (MPC) protocols for tasks such as distributed key generation, distributed signing, and key rotation/refresh. One of the most complex tasks we handle is computing a threshold ECDSA signature for distributed signing. 

This process aims to sign a transaction privately, ensuring that neither Utila nor the client learns the other party’s share of the private key. The challenge with ECDSA lies in its non-linear structure, which complicates decentralization for MPC protocol designers.

Numerous protocols have been suggested in the literature to tackle this task. In this blog post, we’ll review the main protocols and explain the design considerations that influenced our choice. 

Key Factors We Considered

Selecting the right MPC protocol for our product involves evaluating several key factors. The most important of these is security, as not all protocols offer the same level of protection. 

Additionally, efficiency metrics such as computational, communication, and round complexities must also be considered. Each protocol has its own advantages, and it’s rare to find one that is universally superior. It’s important to note that our decision not to choose a particular protocol doesn’t imply that we identified security issues or view it as problematic. 

Rather, we simply chose the one that best aligns with our product’s needs. Broadly, ECDSA protocols fall into two main categories:

• Protocols that are based on (linear) homomorphic encryption, such as Paillier Encryption. In this family of protocols we can find the protocols by Lindell [Lindell17¹], Gennaro and Goldfeder [GG18²], Lindell and Nof [LN18³], and Canetti, Gennaro, Goldfeder, Makriyannis and Peled [CGGMP20⁴].
• Protocols that are based on Oblivious Transfers. In this family of protocols we can find the two protocols by Doerner, Kondi, Lee, and shelat [DKLs19⁵] and [DKLs23⁶], as well as an updated version of the protocol by Lindell and Nof (together with Haitner and Ranellucci).

We elaborate on each family separately. 

Protocols Based on Linear Homomorphic Encryption

These protocols primarily rely on the Paillier homomorphic encryption scheme, which is additive in nature. This means that given the encryptions of two values, m₁ and m₂, and the public key, one can compute an encryption of m₁+m₂​ directly from the ciphertexts, without ever needing to decrypt them. 

Essentially, operations can be performed on the ciphertexts without knowing the underlying plaintexts, resulting in a fresh encryption that corresponds to the sum of the original plaintexts. 

However, this advantage does not come for free. Like RSA, Paillier encryption requires a relatively high bit modulus, with a 2048-bit modulus being the minimum standard for security today. 

In contrast, elliptic curve-based encryption schemes (such as ElGamal, or signature schemes like Schnorr, ECDSA, and EdDSA) operate with much smaller, 256-bit groups. 

Consequently, operations in the Paillier scheme are significantly more resource-intensive—at least 8 times more costly—compared to their elliptic curve counterparts. This is the reason why the blockchain industry widely adopted elliptic-curve-based signatures.

Let’s now focus on the CGGMP20 protocol, which belongs to this family of protocols. In addition to the computationally expensive Paillier encryption, the protocol requires the generation of several zero-knowledge proofs on Paillier-encrypted values. 

For example, it necessitates proving that an encryption (relative to a known public key) is within the correct range, or that the Paillier homomorphic operations were performed correctly. These proofs are particularly costly because they involve operations over large fields with secret orders. 

In contrast, zero-knowledge proofs over groups with known orders, such as those used in elliptic curves, are much more efficient. Furthermore, to utilize the Paillier encryption scheme, parties need to generate safe biprimes as an auxiliary input—a process that is resource-intensive. Consequently, the key generation protocol also demands considerable computational resources.

Protocols that are Based on Oblivious Transfers

Oblivious Transfer (OT) is a cryptographic primitive that was introduced in 1981 by Michael Rabin. It involves a Sender and a Receiver, and abstractly it implements the following functionality:

• Input: The sender inputs two messages m₀, m₁; The receiver inputs its choice bit b;
• Output: The receiver outputs m_b. 

In particular, the sender learns nothing about the choice bit of the receiver, and the receiver learns nothing about the message m_1-b. OTs are very powerful; it has been shown that the task of OT is “MPC-complete”, namely, any MPC task can be realized using a protocol that uses just OTs.

However, it is also known that Oblivious Transfer (OT) must rely on public-key cryptography, which is generally more resource-intensive than private-key cryptography. Moreover, secure computation protocols often require a large number of OTs, which historically posed a bottleneck in the implementation of MPC protocols. 

Fortunately, this challenge has been overcome with the development of OT extensions. OT extension protocols work by running a small number of “base OTs” (e.g., 256) that generate correlated randomness. This randomness is then used to efficiently derive a large number of OTs using low-cost symmetric cryptographic operations. 

This approach is similar to the common practice in public-key encryption, where instead of encrypting an entire message with a public key, a hybrid encryption scheme is used. In such schemes, the public key is only used to encrypt a symmetric key, and the bulk of the message is encrypted using the more efficient symmetric-key cryptography.

As a result, protocols based on OTs no longer require a large number of public-key operations. Additionally, OTs can be implemented using standard public-key encryption without relying on linear properties. This makes them well-suited for implementation with elliptic curve cryptography, which, as mentioned earlier, uses significantly smaller keys than Pallier. 

In this family of protocols, we mainly focus on DKLs23, which can be viewed as an upgraded version of DKLs19. Both DKLs23 and DKLs19 are reasonably fast in terms of computation. The main advantage of DKLs23 is the number of rounds – 3 instead of 5. The number of rounds is the most important efficiency factor when dealing with high-latency networks. 

Considering these factors, we chose to implement the DKLs23 protocol. It has minimal rounds, resulting in low latency, and is computationally efficient—an essential feature when working with relatively low-power devices like smartphones. 

Comparing CGGMP20, DKLs19, and DKLs23

This table compares between the three protocols: CGGMP20, DKLs19 and DKLs23. 

The Wall-clock is measured when implementing the protocol on a single machine, and therefore ignores the network latency; that is, it reflects the computation overhead. 

Pre-signatures

All three protocols – DKLs19, DKLs23, and CGGMP20 allow for the separation of offline and online phases, enabling the online phase to be as quick as sending a single message between parties. This approach theoretically allows for an “offline phase” to occur during system idle times, in which the parties compute some “pre-signature”. 

Then, the actual signing process happens swiftly when a transaction arrives. However, GS22⁷ has identified conditions where pre-signatures can compromise security; To avoid those attacks, pre-signatures require re-randomization, which adds additional interaction. 

As a result, these protocols cannot easily achieve the “non-interactive” property as initially claimed. Given our priority on security, we currently do not use this pre-signature optimization.  We therefore report the total number of rounds for the entire protocol, without distinguishing between offline and online phases.

Security

As with all protocols used by Utila, our cryptographic team thoroughly reviewed and re-validated the security proof of DKLs23 before implementation, and provided an independent proof of security. 

From a theoretical point of view, the DKLs protocol also has one more advantage over the linear homomorphic-encryption based protocols counterpart. In particular, all cryptographic schemes have to rely on some underlying hardness assumption. 

To prove that the DKLs protocol is secure, the underlying assumptions are the same as those that are already assumed to prove the security of ECDSA signature. That is, to make the ECDSA MPC-compatible, there is no need to assume anything beyond what we already assume for the security of plain ECDSA. In other words, from a theoretical perspective, breaking DKLs is as hard as breaking ECDSA.

This is in contrast to CGGMP, which also relies on the assumption of  strong RSA (this is a variant of RSA that requires that the problem is hard even if the adversary is allowed to chose the public exponent e); semantic security of Paillier encryption, and an enhanced variant of existential unforgeability of ECDSA. All of those are valid assumptions (and do not pose any known security threat), but as a general principle, we want to assume as little as possible.

References

1. Lindell17 – Yehuda Lindell:
   Fast Secure Two-Party ECDSA Signing. CRYPTO (2) 2017: 613-644
   https://eprint.iacr.org/2017/552.pdf
2. GG18 – Rosario Gennaro, Steven Goldfeder:
   Fast Multiparty Threshold ECDSA with Fast Trustless Setup. CCS 2018: 1179-1194
   https://eprint.iacr.org/2019/114.pdf
   
3. LN18 – Yehuda Lindell, Ariel Nof:
   Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody. CCS 2018: 1837-1854
   https://eprint.iacr.org/2018/987.pdf
4. CGGMP20 – Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, Udi Peled:
   UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts.  CCS 2020: 1769-1787
   https://eprint.iacr.org/2021/060
5. DKLs19 – Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat:
   Threshold ECDSA from ECDSA Assumptions: The Multiparty Case.
   IEEE Symposium on Security and Privacy 2019, https://eprint.iacr.org/2019/523.pdf
6. DKLs23 – Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat:
   Threshold ECDSA in Three Rounds.
   In IEEE Symposium on Security and Privacy 2024, https://eprint.iacr.org/2023/765
   
7. GS22 – Jens Groth, Victor Shoup:
   On the Security of ECDSA with Additive Key Derivation and Presignatures. EUROCRYPT (1)2022: 365-396
   https://eprint.iacr.org/2021/1330