Threshold ECDSA: Multi-Party Signing

ECDSA signatures require computing a random nonce k, the curve point R = k*G, and the signature s = k^{-1}(h + r*x) mod n where x is the private key and r is the x-coordinate of R. The inversion of k and the multiplication by the private key make ECDSA inherently non-linear, unlike Schnorr signatures where the response is a simple linear combination. This non-linearity makes distributing the computation among parties extremely challenging.

The GG18 protocol by Gennaro and Goldfeder (2018) was the first practical two-party and threshold ECDSA construction secure without a trusted dealer. The key insight is using Paillier homomorphic encryption to perform the multiplicative-to-additive (MtA) conversion needed for the non-linear ECDSA computation. GG18 provides simulation-based security against static semi-honest adversaries.

GG20 (Gennaro and Goldfeder 2020) improved GG18 by proving security against malicious adversaries without a trusted setup. GG20 added zero-knowledge proofs to ensure each party follows the protocol correctly. These proofs prevent a malicious party from biasing the nonce or the signature to extract information about other parties' key shares. GG20 became the foundation for many production MPC wallet implementations.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) is the current state-of-the-art threshold ECDSA protocol. It achieves identifiable abort, meaning that if the signing protocol fails due to malicious behavior, the protocol can identify which party is responsible. This is critical for enterprise deployments where accountability matters. CGGMP21 is implemented in popular MPC libraries including tss-lib and multi-party-sig.

The core challenge in threshold ECDSA is computing a product of secret shares without revealing them. The MtA (multiplicative-to-additive) conversion transforms a product a*b of two parties' shares into additive shares: party 1 gets alpha, party 2 gets beta, such that alpha + beta = a*b. This is achieved using Paillier encryption: party 1 encrypts a, party 2 homomorphically multiplies by b and adds randomness, the result is decrypted by party 1 to get additive shares.

Paillier encryption is a partial homomorphic encryption scheme supporting both addition and multiplication by a plaintext. Given an encryption Enc(a), anyone can compute Enc(a*b) for known b without decrypting. This property enables the MtA protocol: party 1 generates a Paillier key pair and sends Enc(k1) and Enc(x1) (shares of nonce and private key). Party 2 uses homomorphic operations to compute its contribution without learning k1 or x1.

Threshold ECDSA signing typically involves several rounds of communication. In GG20, there is a preprocessing phase (2 rounds) that computes commitments to the nonce and random blinding values, and an online signing phase (1 round) that combines partial signatures. The preprocessing can be done before the message is known, reducing online latency to a single round. CGGMP21 optimizes this further.

Identifiable abort means that if the threshold signing protocol fails (because a party sent a malformed message or did not follow the protocol), the honest parties can cryptographically determine which party misbehaved. This requires zero-knowledge proofs of correct computation at each step. Without identifiable abort, a malicious party could cause denial of service (refusing to complete the protocol) without being identified.

EdDSA (Schnorr-based signatures over Ed25519) is much easier to threshold than ECDSA because Schnorr signatures are linear: the response z = r + c*x is a sum of additive shares. FROST (Flexible Round-Optimized Schnorr Threshold) by Komlo and Goldberg (2020) achieves two-round threshold Schnorr signing with no trusted setup. FROST is being standardized by the IETF (RFC draft) for use in privacy-preserving protocols and cryptocurrency wallets.

Threshold ECDSA is computationally more expensive than single-party ECDSA due to the MtA protocol and zero-knowledge proofs. GG20 two-party signing takes approximately 1-2 seconds on modern hardware; threshold with larger n takes longer due to more pairwise MtA executions. CGGMP21 optimizations reduce this to hundreds of milliseconds. For cryptocurrency transactions where signing latency matters, this performance is acceptable but significant.

Threshold ECDSA is deployed at scale in institutional finance. Fireblocks uses GG20-based threshold ECDSA securing over $4 trillion in transaction volume. Coinbase Prime uses MPC custody based on threshold signatures. Qredo and Copper.co offer threshold ECDSA for institutional asset management. The tss-lib Go library (used by Binance) and multi-party-sig (used by Coinbase) are major open-source implementations.

What role does Paillier homomorphic encryption play in threshold ECDSA?

Threshold ECDSA allows t parties to sign without any party knowing the full key. ECDSA's non-linear structure requires MtA conversion using Paillier homomorphic encryption. GG18 pioneered the approach, GG20 added malicious security, and CGGMP21 added identifiable abort. EdDSA/Schnorr is easier to threshold via FROST (2-round, no trusted setup). Production deployments at Fireblocks and Coinbase secure trillions in assets.