Threshold signatures
A signing key is secret-shared among n parties so that authorized subsets jointly produce a signature under one public key, while smaller coalitions can neither sign nor learn the key.
What it is
In a -out-of- threshold signature scheme, the signing key of a signature scheme is secret-shared among parties. Any authorized set runs a signing protocol whose output verifies under the single public key; the key is never reconstructed. Unforgeability must hold against an adversary that corrupts fewer parties than the threshold and takes part in arbitrarily many signing sessions. The paradigm goes back to threshold cryptosystems (). A threshold signature uses one shared key; a multisignature combines independent keys.
Core notions
- Threshold convention: papers use either for the number of tolerated corruptions, so that parties sign, or for the number of required signers. The -out-of- case is called full threshold.
- Key generation: a trusted dealer shares the key, or a distributed key generation (DKG) protocol lets the parties create their shares and the public key so that no party ever holds the key (, ).
- Robustness and identifiable abort: a robust protocol outputs a valid signature despite malicious participants; with identifiable abort, a failed run names a cheater; otherwise the protocol may simply abort.
- Static, adaptive, proactive: the adversary fixes its corrupted set before key generation or chooses it during execution; proactive refresh renews shares across epochs against an adversary that moves between parties.
- Rounds and preprocessing: online rounds after the message is known are counted separately from message-independent preprocessing; some schemes let each party send its signature share without interaction.
- Interoperability: the combined signature is accepted by the unmodified verifier of the base scheme (for example ECDSA, Schnorr/EdDSA, BLS, or ML-DSA), so a verifier need not know that a threshold was used.
Main approaches
- Non-interactive shares for algebraic schemes: threshold RSA (, ) and threshold BLS (), where a combiner checks and interpolates signature shares.
- Threshold Schnorr: the shared nonce is the main difficulty. FROST signs in two rounds, or one online round after preprocessing (); later work proves FROST-type signing without the algebraic group model (), gives stateless deterministic signing (), and obtains full adaptive security from DDH in the random-oracle model ().
- Threshold ECDSA: the inversion in ECDSA signing requires secure multiplication, built from Paillier encryption (, , ) or oblivious transfer (). adds UC security against adaptive corruption, identifiable abort, and proactive refresh.
- Lattice threshold signatures: abort-based lattice signing leaks through rejected attempts and needs short shares. Approaches include two-round full-threshold signing (), threshold homomorphic encryption for arbitrary thresholds (), Raccoon with one-time additive masks (), hash-and-sign via noise flooding (), two rounds without FHE under algebraic one-more LWE (), and an implemented scheme with ordinary-verifier output and proactive refresh (). Threshold ML-DSA protocols target the standardized verifier directly (, , ).
Notation used in the comparison table
Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.
| Symbol | Meaning | Regime | Paper aliases | ||
|---|---|---|---|---|---|
| n | Total number of key-share holders. | Threshold signing. | writes n; writes N; writes l; writes N; writes N | ||
| t | Minimum number of shares/signers required to sign. | Threshold signing; this is not the tolerated-corruption count. | writes t; writes T; writes t + 1; writes k; writes 2t + 1; writes T; writes T; writes t + 1; writes t + 1; writes t; writes t + 1 | ||
| tc | Number of tolerated corruptions, as stated by the security theorem. | Threshold signing; it need not equal t − 1. | writes tc; writes tc; writes t; writes T − 1; writes t; writes t; writes t; writes t | ||
| λ | Computational security parameter. | Threshold-signature security. | No paper spelling asserted. | ||
| q | Prime order of the signing group; in lattice schemes, the modulus of Rq. | Group-based and lattice threshold signatures. | writes q; writes p; writes p; writes p | ||
| s | Statistical security parameter. | OT-based threshold ECDSA. | No paper spelling asserted. | ||
| κ | Symmetric security parameter: the output length of the hash and the PRG, and the number of base OTs an OT extension takes. DKLs18 sets \( \kappa = | q | \), so a scalar there is κ bits. | OT-based threshold ECDSA. | writes κ |
| 𝔾 | The signing group; \( | \mathbb{G} | \) is the size of one element in bits. | Discrete-logarithm threshold signatures. | No paper spelling asserted. |
| 𝔾1 | The source group of a pairing that holds signatures; \( | \mathbb{G}_1 | \) is the size of one element. | Pairing-based threshold signatures. | No paper spelling asserted. |
| 𝔾2 | The source group of a pairing that holds public keys; \( | \mathbb{G}_2 | \) is the size of one element. | Pairing-based threshold signatures. | No paper spelling asserted. |
| ℤq | Scalars modulo the group order q; \( | \mathbb{Z}_q | \) is the size of one scalar. | Discrete-logarithm threshold signatures. | No paper spelling asserted. |
| N | RSA or Paillier modulus. | RSA threshold signatures and Paillier-based threshold ECDSA. | No paper spelling asserted. | ||
| ℤN | Residues modulo N, and ℤN2 modulo N2 (a Paillier ciphertext); \( | \cdot | \) is the size of one residue. | RSA and Paillier-based threshold signatures. | No paper spelling asserted. |
| k | Number of rows of the public matrix A ∈ Rk×ℓq. | Module-lattice threshold signatures. | No paper spelling asserted. | ||
| ℓ | Number of columns of the public matrix A ∈ Rk×ℓq. | Module-lattice threshold signatures. | No paper spelling asserted. | ||
| d | Degree of the ring: Rq = ℤq[X]/(Xd + 1), so a ring element has d coefficients. In the BGGJKRS circuit-based construction, the depth of the circuit it evaluates. | Lattice threshold signatures; the BGGJKRS circuit-based construction. | writes N; writes d; writes N; writes N; writes n; writes n; writes n | ||
| Rq | The polynomial ring modulo q, of degree d, whose elements lattice keys and signatures are made of; \( | \mathcal{R}_q | \) is one element at full width, d⌈log2 q⌉ bits. | Lattice threshold signatures. | No paper spelling asserted. |
| Rm | An element of the same ring whose coefficients take ⌈log2 m⌉ bits: a rounded, compressed or short element, counted at the modulus of its encoding. | Lattice threshold signatures that encode elements below full width. | No paper spelling asserted. | ||
| qsig | Number of signing queries/sessions counted by the source theorem. | Threshold-signature reductions. | writes qsig | ||
| N̂ | The auxiliary RSA modulus a verifier generates for the range proofs it checks, with its ring-Pedersen parameters; \( | \mathbb{Z}_{\hat{N}} | \) is one residue modulo it. | Paillier-based threshold ECDSA. | writes N̂; writes Ñ |
The comparison tables count communication and computation from each protocol, per role and per phase: P1 and P2 in the two-party table, and in the threshold table each signer, the coordinator and the dealer where the protocol has them.
| Role | Meaning | Regime | Paper names |
|---|---|---|---|
| P1 | The party that sends first in signing and outputs the signature. | Two-party signing. | writes "P_1"; writes "Bob"; writes "P_1" |
| P2 | The other party of a two-party signing session. | Two-party signing. | writes "P_2"; writes "Alice"; writes "P_2" |
| Per signer | Each key-share holder: all n in key generation, each of the t signers in a signing session. | Threshold signing. | writes "players"; writes "servers"; writes "parties"; writes "parties"; writes "participants"; writes "users"; writes "users" |
| Coordinator | A party outside the signers that relays, aggregates or combines, where the protocol has one; it is costed wherever it sends or computes. | Threshold signing with an aggregator, coordinator or combiner. | writes "signature aggregator SA"; writes "coordinator"; writes "aggregator"; writes "combiner"; writes "combiner" |
| Dealer | The trusted dealer, in setup only. | Threshold signing with a trusted dealer. | No paper name asserted. |
This topic covers protocols in which one signing key is secret-shared and an authorized subset produces a publicly verifiable signature without reconstructing it, including DKG, refresh, and identifiable-abort results that change the protocol. Multisignatures, aggregate signatures, threshold encryption, and generic MPC are outside it; ordinary signatures have their own topic.