In this blog post, we will look at the CGGMP21 paper¹ and how their protocols improved in the recent eprint updated version, CGGMP24.²
Signatures
A signature scheme is a cryptographic primitive that allows one to verify the authenticity of a message, ensuring that it comes from a trusted source. Digital Signature Algorithm (DSA) is a specific digital signature scheme that relies on the discrete logarithm problem. Specifically, in the case of an Elliptic Curve DSA (ECDSA), DSA is combined with elliptic curve cryptography. In this blogpost we will focus on ECDSA signatures.
ECDSA
ECDSA (Elliptic Curve Digital Signature Algorithm) is the most widely used signing scheme in web3, being deployed in 74 out of the top 100 cryptocurrencies³ as a mechanism to authorize transactions. We recall that ECDSA is parametrized by an elliptic curve over a finite field and defined by a triple (G, g, q), where G is a subgroup of points in the curve with prime order q and generator g. Given a message M, secret key x, and random nonce k in ℤ*q, the ECDSA signature is a pair (r, s) ∈ ℤ*q where s = k · (H(M) + x · r), for a cryptographic hash function H, and r is the x-coordinate of the point R = gk-1.
Threshold Signatures
Threshold signatures are a tool in cryptography that enables a message to be signed if and only if a minimum number of parties in a larger group agree to sign it. This setup helps avoid a “single point of failure”— instead of just one party having control, a subgroup has to act together. It’s a powerful tool, especially for systems like blockchain that rely on decentralization. For this reason, implementing ECDSA in a threshold setting is especially desirable for such systems, but it presents unique challenges. Unlike some other signing schemes, ECDSA requires keeping a private, random value k confidential while simultaneously using it to jointly compute r and its modular inverse for the signature component s.
In GG18,⁴ the authors presented a protocol that laid the foundation for CGGMP21. We briefly describe the idea of a simplified version of GG18:
- The n protocol parties hold additive shares of the secret key x.
- They start by generating additive shares of the random nonce k = k1 + … + kn and of its mask γ = γ1 + … + γn.
- Parties open the product δ = k · γ and compute k-1 by multiplying the local shares of γ with δ-1.
- Point R is computed by opening (gγ1 … gγn) δ-1 and r is given as the x-coordinate of R.
- Compute secret shares of the product σ = k · x = w1 + … + wn.
- Compute shares of s using the above elements: si = ki · H(M) + wi · r.
- Parties output (r, si).
CGGMP21
In 2021, researchers came out with CGGMP21,¹ a threshold version of ECDSA building on top of previous work.² CGGMP21 uses the above idea along with the GMW approach of proving parties followed the protocol based on zero-knowledge proofs. They presented two main protocols with some unique features and interesting trade-offs, and we will refer to them as the “4-round” and “7-round” protocols.
Both of these protocols support two modes of operation—online and non-interactive—offering flexibility depending on your infrastructure. Plus, they’re secure under the Universal Composability framework, meaning they can handle multiple concurrent secure executions, and they have safeguards like identifiable aborts (you can identify misbehavior) and proactive security (the shared signing key stays safe over time). The primary difference between these two is that the 4-round protocol can generate “presignatures” in 3 rounds, while the 7-round protocol requires a heftier 6 rounds. It’s no surprise that the 4-round version, with its faster setup, has gained traction. In fact, it’s become a bit of a standard for threshold ECDSA, with an open-source implementation by the DFNS team⁵ that’s now part of the Linux Foundation Decentralized Trust (LFDT).
Fast forward to the latest version of this paper, CGGMP24.² It turns out the 7-round protocol is not presented there and the authors described the reason:
“The protocol presented in this document is the culmination of several improvements and simplifications, achieving the best costs compared to the two protocols in [21].”
Let’s take a closer look and see if we can shed some light on why the 7-round protocol disappeared from the CGGMP lineup.
Some Technical Assumptions
In this post, we are not going to delve into technical details nor the assumptions that are required for each protocol. But it’s worth pointing out that these protocols make extensive use of zero-knowledge proofs for the identification of corrupted parties which rely on some intense mathematical operations. They use exponentiations in an elliptic curve group (Secp256k1) G and in two different rings: integers modulo N and modulo N² (e.g., Paillier encryption scheme and the Pedersen commitments). Now, without getting into all the details, it’s enough to say these operations can be computationally demanding, and they’re central to analyzing the cost of these protocols. We present below the time required for each of these operations from the following LFDT-Lockness repos: fast-paillier⁶ and generic-ec.⁷ This will give us a clearer view of how each protocol stacks up in terms of efficiency and cost.
[table id=4 /]
Investigating the Case
Uncovering the Differences in CGGMP21
CGGMP21 paper doesn’t introduce two signing protocols for the sake of variety – these two versions exist because they follow different methods to catch corrupted parties presenting a trade-off. Without this difference in identifying and handling bad actors, there wouldn’t be a need for multiple protocols.
Both protocols wrap up with a single round dedicated to signing the actual message, but they differ in the number of rounds needed for presigning, or “preprocessing”. In the 4-round protocol, one makes use of Paillier encryption, Pedersen commitments. and group exponentiations to prove participants’ honesty and expose dishonesty. This version keeps the presigning phase shorter but demands more computation to achieve identifiable aborts (IA). The 7-round protocol takes a different approach. Instead of multiple proofs for each participant, it employs El-Gamal commitments, which allow each party to prove things without needing separate proofs for each other party. Additionally, it optimizes computational efficiency by increasing the use of group exponentiations, which are computationally cheap, while reducing the need for the more computationally demanding ring exponentiations. Indeed, the ring exponentiation modulo N is bout 60x slower than the group exponentiation. This reduces both the computational and communication costs associated with IA—but at the price of adding three more rounds to the presigning phase.
What’s the trade-off? In the 7-round protocol, the cost of identifying a dishonest participant grows linearly with the number of participants. But in the 4-round protocol, this identification cost grows quadratically, becoming significantly more resource-intensive as the number of parties grows. So each protocol comes with its own balance of speed and efficiency depending on what’s prioritized: faster setup or cheaper dishonest identification.
CGGMP24
In CGGMP24, the researchers made a key update: they incorporated El-Gamal commitments directly into the 4-round protocol increasing the use of group exponentiations while reducing the use of ring exponentiations modulo N and N². Note that the exponentiation modulo N² is about 500x slower than the group exponentiation. This integration reduces both computation and communication costs for the IA feature, without adding any extra rounds to the presigning phase. Essentially, CGGMP24 completes what CGGMP21 hinted at by making the 7-round protocol obsolete—now, all the benefits are available within the faster 4-round version.
Below is a cost comparison for the exponentiations operations required in each presigning protocol. We’ll break down the computational and communication requirements using values for group exponentiations in elliptic curve secp256k1 (G), and modular exponentiations in rings N and N². Note that these costs refer only to the exponentiation operations and not to the overall protocol. Here, n = 3 is the number of participants, and κ = 256 and μ = 3072 refer to the message size for elliptic group elements and Paillier plaintext ring elements, respectively. Table 2 presents timing estimates for the group and ring exponentiations performed in the CGGMP21 and CGGMP24 protocols based on the numbers from Table 1 and the complexity expressions provided in CGGMP21 and CGGMP24, highlighting that CGGMP24’s 4-round protocol outperforms both CGGMP21 protocols in computational efficiency and communication overhead—even more so when IA is needed.
[table id=5 /]
Looking at the above table, it is easy to see that the CGGMP24 4-round protocol is better than the previous protocols: not only minimizes rounds but also offers the lowest costs in computation and communication. If IA is called, it is also clear that this protocol is still the best of the three. IA in CGGMP24 remains linear in cost relative to the number of parties, making it simpler and quicker compared to CGGMP21’s 4-round protocol quadratic cost approach.
Client Perspective: Gains in Non-Interactive Signing
Now, consider a setting where clients delegate ECDSA key management and decentralized signing to an external network. Here, CGGMP24 brings a clear advantage from a client experience perspective, particularly when compared to CGGMP21’s 4-round protocol. Both CGGMP21 and CGGMP24 offer two modes of execution: online (interactive) signing and non-interactive signing. In online signing, the client submits both the message and the instruction to sign it simultaneously, triggering the signing process from scratch. By contrast, the non-interactive mode lets the network prepare presignatures in advance before the message is even provided. This preparation enables a faster response time when the client eventually requests a signature, as significant parts of the computation and communication have already been handled.
This is relevant in case IA is called. Let’s assume the protocol is being run in non-interactive mode. In this case, once the user submits a message to be signed, all the necessary presignatures have already been computed, and valid presignatures are in place. With the CGGMP24 4-round protocol, all the zero-knowledge proofs required for IA are handled during the preprocessing phase. This means that if a signature validation fails and corrupted parties need to be identified, the process is straightforward—since the necessary proofs have already been generated, the identification of bad actors is fast and efficient. However, the picture changes with the CGGMP21 4-round protocol. Even if valid presignatures are available from the preprocessing phase, if the signature fails, additional zero-knowledge proofs must still be computed. This makes identifying corrupted parties after a signature failure significantly slower and more resource-intensive. From a client perspective, CGGMP24 offers a clear advantage—by moving the computational and communication costs of identifying corrupted parties to the preprocessing phase, the network is spared from handling costly zero-knowledge proofs during the actual signing phase. This architecture means less waiting and an overall more efficient experience when dealing with faulty parties.
Conclusion
So, where is the CGGMP 7-round protocol? Inside the 4-round protocol! In a nutshell, the CGGMP24 4-round signing protocol takes the CGGMP21 4-round protocol and enhances it by incorporating tools from the CGGMP21 7-round protocol. The result is a new protocol with the best of both protocols:
- Lighter on computation and communication than both of its predecessors.
- Whenever IA is called, the CGGMP24 4-round protocol keeps the cost of identifying a dishonest participant scaling linearly with the number of participants—unlike the CGGMP21 4-round protocol, where costs grew quadratically as group size increased.
- When CGGMP24 4-round protocol runs in non-interactive mode and IA is called, all the heavy computations for IA are handled during the preprocessing phase. This differs from the CGGMP21 4-round protocol where the workload is split between the presigning and signing phases.
Acknowledgments
We thank Denis Varlakov from Dfns Labs for the development of the benchmark tests used in Table 1 and Dimitris Mouris for valuable comments on this post..
References
¹ Canetti, R., et al. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts, CCS’20.
² Canetti, R., et al. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts, eprint 21 Oct 2024 version: https://eprint.iacr.org/archive/2021/060/20241021:172019
³ http://ethanfast.com/top-crypto.html
⁴ Gennaro, R. and Goldfeder, S. Fast multiparty threshold ECDSA with fast trustless setup, CCS’18.
⁵ https://github.com/LFDT-Lockness/cggmp21