Improving threshold ECDSA and its applications to AI Agents

PUBLISHED

01.29.2025

AUTHOR

José Reis and Manuel B. Santos

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 $^{\text{3}}$ 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 an additive 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 $\mathbb{Z}^*_q$ , the ECDSA signature is a pair $(r, s) \in \mathbb{Z}^*_q$ where $s = k \cdot (H(M) + x \cdot r)$ , for a cryptographic hash function $H$ , and $r$ is the $x$ -coordinate of the point $R = g^{k^{-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.

New practical implementations: AI agents

Threshold signature is a powerful tool, especially for systems like blockchain that rely on decentralization. They can enhance crypto wallet security by improving private key management, and can also improve the robustness of validators. Validators can use threshold signatures to distributively sign transactions with a single key to improve the consensus mechanism $^{\text{4}}$ . Beyond blockchain, threshold signatures are highly effective in addressing security risks associated with AI agents managing sensitive tasks, such as executing trading transactions. By leveraging a signing network, they prevent unauthorized key use or extraction by AI agents while still allowing secure execution of transactions.

Imagine a scenario where we want an AI agent to assist in executing trading transactions, a concept demonstrated by Nillion in our demo $^{\text{5}}$ . The level of autonomy I can give it may vary:

Command AI agent. The AI agent creates a transaction based solely on my decision;
Autonomous AI agent. We delegate the trading decision to the AI agent, based on a financial strategy I define or its own analysis of the market trends.

To allow both cases, the AI agent needs access to our secret signing key. But this comes with serious risks:

Agents with keys can go rogue: If the AI misbehaves or is hacked, there’s nothing stopping it from making unauthorized transactions.
Keys can be extracted: Since these agents often operate in remote, third-party environments (like cloud servers), the risk of someone stealing the keys increases dramatically.

One way to tackle these two issues is using threshold signatures, which split a private key into shares distributed across a network of nodes. The AI agent holds an authentication key to communicate with the network, but the actual signing is done by the nodes using a secure cryptographic protocol (e.g., CGGMP24). Why is this of any use?

User-defined permissions: As the user, we can tightly control what the AI agent can and cannot do. We can set limits on transaction amounts, asset types, specific addresses, time periods, and even the blockchain networks it can interact with. This reduces the risk of the AI agent going rogue.
No direct access to the signing key: The AI agent never sees or holds the private key. It only communicates with the network, requesting signatures when needed. This significantly reduces the risk of the key being stolen or misused.

ECDSA Threshold signatures

Given the impact of threshold ECDSA, implementing it is especially desirable, 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 components r and its modular inverse for the signature component $s$ .

In $^{\text{6}}$ , the authors presented a protocol that laid the foundation for CGGMP21. We briefly describe the idea of a simplified version of $^{\text{6}}$ :

The $n$ protocol parties hold additive shares of the secret key $x$ .
They start by generating additive shares of the random nonce $k = k_1 + \ldots + k_n$ and of its mask $\gamma = \gamma_1 + \dots + \gamma_n$ .
Parties open the product $\delta = k\cdot\gamma$ and compute $k^{-1}$ by multiplying the local shares of $\gamma$ with $\delta^{-1}$ .
Point $R$ is computed by opening $(g^{\gamma_1} \cdot \ldots \cdot g^{\gamma_n})^{\delta^{-1}}$ and $r$ is given as the $x$ -coordinate of $R$ .
Compute secret shares of the product $\sigma = k\cdot x = w_1 + \cdot w_n$ .
Compute shares of the s using the above elements: $s_i = k_i\cdot H(M) + w_i\cdot r$ .
Parties output $(r, s_i)$ .

CGGMP21

In 2021, researchers came out with CGGMP21 $^{\text{1}}$ , a threshold version of ECDSA building on top of previous work $^{\text{2}}$ . 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 $^{\text{7}}$ that’s now part of the Linux Foundation Decentralized Trust (LFDT).

Fast forward to the latest version of this paper, CGGMP24 $^{\text{2}}$ . 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 $^{\text{1}}$ .”

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^2$ (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 $^{\text{8}}$ and generic-ec $^{\text{9}}$ . This will give us a clearer view of how each protocol stacks up in terms of efficiency and cost.

Exponentiation in	Time (ms)
Elliptic curve group (Secp256k1) $G$	0.027
Integers modulo $N$	1.696
Integers modulo $N^2$	13.868

Table 1 – Time for each exponentiation type given by the benchmark tests from cggmp21 repo exp file $^{\text{10}}$ . A MacBook Pro with an M3 Pro @ 4.1 GHz was used.

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 about 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^2$ . Note that the exponentiation modulo $N^2$ is about $500\times$ 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 exponentiation 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^2$ . 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 $\kappa = 256$ and $\mu = 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. It highlights that CGGMP24’s 4-round protocol outperforms both CGGMP21 protocols in computational efficiency and communication overhead—even more so when IA is needed.

Presigning Protocol	Computation		Communication
Presigning Protocol	Complexity	Time estimation (s)	Complexity	Estimation (KB)
CGGMP21 4-rounds	$n\cdot (12G + 56N + 33N^2)$	$1.66$	$n\cdot (57\kappa + 54\mu)$	$68$
CGGMP21 7-rounds	$n\cdot(29G + 49N +33N^2)$	$1.62$	$n\cdot (67\kappa + 51\mu)$	$65$
CGGMP24 4-rounds	$n\cdot(26G + 48N +26N^2)$	$1.33$	$n\cdot (65\kappa + 48\mu)$	$62$

Table 2 – Computation and communication cost of exponentiation operations in three different presigning protocols. $G$ , $N$ and $N^2$ stand for operations in the elliptic curve group and rings mod $N$ and mod $N^2$ . The expressions for complexity were taken from Table 1 in CGGMP21 and Table 1 in CGGMP24

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

[1] Canetti, R., et al. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts, CCS’20.

[2] 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

[3] http://ethanfast.com/top-crypto.html

[4] https://github.com/ethereum/distributed-validator-specs, accessed on January 17th, 2025.

[5] https://nillion.com/news/1607/

[6] Gennaro, R. and Goldfeder, S. Fast multiparty threshold ECDSA with fast trustless setup, CCS’18.

[7] https://github.com/LFDT-Lockness/cggmp21

[8] https://github.com/LFDT-Lockness/fast-paillier

[9] https://github.com/LFDT-Lockness/generic-ec

[10] https://github.com/LFDT-Lockness/cggmp21/blob/m/tests/benches/exp.rs, accessed on January 17th, 2025.