Threshold signature
A -threshold signature scheme shares the signing key for one public key among parties so that any of them can run a signing protocol whose output verifies under that public key, while corrupted parties cannot forge. The output is often an ordinary signature of an existing DS scheme: RSA full-domain hash — Sho00, BLS — Bol03, Schnorr — KG20, DSS — GJKR96.
Syntax
This page writes for the number of corrupted parties tolerated, so that parties sign. KG20 and the FROST literature write for the number of signers, tolerating corruptions; Sho00 writes for the number of parties, for the corruptions and for the number of shares combined.
A -threshold signature scheme, for , is a tuple with message space :
- , a randomized algorithm, run by a trusted dealer, that outputs the public key , a verification key for each party’s share, and party ‘s key share ,
- , an interactive protocol among a set of at least parties, party on input , at the end of which each party in outputs a signature ,
- , a deterministic algorithm outputting a bit .
A distributed key generation protocol among the parties can replace the dealer, giving party its share and every party and the — standard. When and the distribution of are those of a DS scheme, is a threshold version of that scheme, and verifiers run its unmodified verification algorithm — standard.
In a non-interactive scheme, is one round: each party sends a signature share , a deterministic checks it, and outputs from any set of valid shares — Sho00. BCK+22 also count as non-interactive a scheme whose single signing round follows one round of message-independent preprocessing, such as FROST.
Properties
Correctness
is perfectly correct if for all output by , all with and all , an honest run of among the parties in on outputs a signature with . A non-interactive scheme also requires that honestly generated shares pass .
Unforgeability
The adversary chooses a set of at most parties to corrupt before key generation, and receives their key shares, the public key and every verification key. It opens signing sessions on sets and messages of its choice, plays the parties in , and receives the messages of the honest parties in , interleaving sessions arbitrarily. It wins with a valid signature on a message on which no honest party started a session — standard. The exclusion is needed because a session the adversary completes gives it a signature on its message. Schemes that assume private channels between parties withhold messages between honest parties from the adversary.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ts\text{-}uf}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(C, \stA) \gets \calA(1^\secpar, n, t)$
\Comment{static corruption: $C \subseteq [n]$, $|C| \le t$}
\State $(\pk, (\pk_i)_{i \in [n]}, (\sk_i)_{i \in [n]}) \gets \KeyGen(1^\secpar, n, t)$ ; $\calQ \gets \{\}$
\State $(m^*, \sigma^*) \gets \calA^{\calO_{\Sign}}(\stA, \pk, (\pk_i)_{i \in [n]}, (\sk_i)_{i \in C})$
\If{$m^* \in \calQ$}
\Return $0$
\EndIf
\Return $[\Vrfy(\pk, m^*, \sigma^*)]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(j, S, m, M)$}
\begin{algorithmic}
\If{session $j$ is new, $S \subseteq [n]$ and $|S| \ge t+1$}
\State $\calQ \gets \calQ \cup \{m\}$
\State start each party $i \in S \setminus C$ on $(\sk_i, S, m)$ as session $j$
\EndIf
\State feed the corrupted parties' messages $M$ to session $j$
\State let $M'$ be the next messages of the parties of session $j$ not in $C$ ($M' := \bot$ if session $j$ was never started)
\Return $M'$
\end{algorithmic}
\end{algorithm}
For polynomials and , is unforgeable against static corruption of parties if for all efficient ,
is negligible.
is a threshold signature scheme if, for all polynomials and with , it is perfectly correct and unforgeable against static corruption of parties. Robustness is a further property, not part of this definition.
For non-interactive schemes, BCK+22 give a hierarchy of stronger notions, which relax the condition under which a forged message counts as new.
Robustness
is robust if the corrupted parties cannot prevent the honest parties from producing signatures — Sho00: every session whose set contains at least honest parties outputs a valid signature, whatever the corrupted parties send. The game has the static corruption, and of . Once halts, the game runs every unfinished session to completion, each message a corrupted party has not sent taken to be , so that withholding messages cannot keep a session from ending.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{rob}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(C, \stA) \gets \calA(1^\secpar, n, t)$
\Comment{static corruption: $C \subseteq [n]$, $|C| \le t$}
\State $(\pk, (\pk_i)_{i \in [n]}, (\sk_i)_{i \in [n]}) \gets \KeyGen(1^\secpar, n, t)$ ; $\calQ \gets \{\}$
\State run $\calA^{\calO_{\Sign}}(\stA, \pk, (\pk_i)_{i \in [n]}, (\sk_i)_{i \in C})$
\State run every unfinished session to completion
\Comment{unsent messages of parties in $C$ are $\bot$}
\For{each session $j$, on set $S$ and message $m$, with $|S \setminus C| \ge t+1$}
\If{some $i \in S \setminus C$ outputs $\bot$ or a $\sigma$ with $\Vrfy(\pk, m, \sigma) \ne 1$}
\Return $1$
\EndIf
\EndFor
\Return $0$
\end{algorithmic}
\end{algorithm}
For polynomials and , is robust against static corruption of parties if for all efficient ,
is negligible.
When , a session on all parties has at least honest parties whatever is, so in a robust scheme it outputs a valid signature except with negligible probability; when , an adversary corrupting parties leaves at most honest ones, and the game then asks nothing of the scheme — standard. In a non-interactive scheme, a session with at least honest parties has at least shares that pass , by correctness, so the scheme is robust if, except with negligible probability, every shares that pass combine into a valid signature — standard.
Variations
Adaptive corruption
The adversary corrupts parties at any point of the game, up to in total, and learns the key share and internal state of each, instead of fixing before key generation. In the game above, replaces the first line, receives together with the public keys, and also has the corruption oracle below. is an adaptively secure threshold signature scheme if, for all polynomials and with , it is perfectly correct and every efficient wins this game with negligible probability. Canetti, Gennaro, Jarecki, Krawczyk and Rabin give adaptively secure distributed key generation for discrete-log schemes and adaptively secure threshold DSS, and show how to make static threshold RSA schemes adaptively secure — CGJ+99.
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{Corr}}(i)$}
\begin{algorithmic}
\If{$|C| < t$}
\State $C \gets C \cup \{i\}$
\Return $\sk_i$ and the state of party $i$ in every open session
\EndIf
\Return $\bot$
\end{algorithmic}
\end{algorithm}
Honest majority ()
is an honest-majority threshold signature scheme if, for all polynomials and with and , it is perfectly correct and unforgeable against static corruption of parties. This is the definition of a threshold signature scheme restricted to , so every threshold signature scheme is one (Threshold signature ⇒ Honest-majority threshold signature), and so is Shoup’s scheme (Threshold RSA signatures ⇒ Honest-majority threshold signature) — folklore.
Threshold RSA
In Shoup’s scheme, a trusted dealer chooses with and for primes , and a prime public exponent , computed from , and by an efficient rule , and shares the signing exponent with a random polynomial of degree over , party receiving . With and , party ‘s signature share is , with a Fiat–Shamir proof that it is consistent with the party’s verification key. Any valid shares combine, with Lagrange coefficients multiplied by so that they are integers, into with for . Since is a prime greater than , , and for satisfies : is the RSA full-domain-hash signature on — Sho00. Share generation and verification are non-interactive, and a share is at most a constant times the length of — Sho00. The scheme is unforgeable and robust in the random-oracle model against static corruption of parties, for all polynomials and with (Sho00’s case , ), if RSA is hard for for every polynomial (RSA (safe-prime moduli) ⇒ Threshold RSA signatures) — Sho00.
Threshold BLS
In Boldyreva’s threshold version of BLS signatures, over a gap Diffie–Hellman group of prime order , in which CDH is hard and DDH is easy, party holds for a polynomial of degree with , the signing key, and . Its signature share on is , which anyone checks by deciding whether is a Diffie–Hellman tuple, and any set of valid shares combines into , with the Lagrange coefficients of at , which is the BLS signature — Bol03. Bol03 proves the scheme robust and unforgeable in the random-oracle model in every gap Diffie–Hellman group, such as a group with a symmetric pairing in which CDH is hard. Threshold BLS also meets stronger notions in the hierarchy of BCK+22.
FROST
FROST is a threshold version of Schnorr signatures with the public key included in the hash, in a group of prime order with generator . Party holds a Shamir share of for the public key , with . In this section key generation is the trusted dealer of above, which shares with a random polynomial of degree ; FROST with key generation by a distributed key generation protocol is a different scheme and is not covered here. In a preprocessing round, which may precede the message, party publishes nonce commitments . To sign with a set , given the list of the commitments of the parties in , party computes the binding factors , and , and sends , with the Lagrange coefficient of at . Each share is checked by , and the signature is with , so that — KG20.
KG20 write for the number of signers and tolerate corruptions. The binding factors tie each party’s nonce to and to the whole list , which protects concurrent signing sessions against forgery attacks that apply to similar schemes. FROST is not robust: a party whose share fails its check is identified, and the session aborts. FROST was proposed with a security argument from the hardness of DLOG in the random-oracle model against an adversary controlling fewer than parties — KG20.
FROST is secure, in the sense of this section, if, with the trusted dealer above and with each signing session on and running the commitment round and then the signing round, it is a threshold signature scheme: for all polynomials and with (KG20’s threshold ), it is unforgeable against static corruption of parties. It is perfectly correct, since honest shares pass their checks and — KG20.
FROST2
FROST2 uses one binding factor for all signers, so that costs one exponentiation in place of — CKM21. FROST2 is secure, in the sense of this section, if, with the trusted dealer and the signing sessions of FROST, it is a threshold signature scheme: for all polynomials and with , unforgeable against static corruption of parties. FROST2 with key generation by a distributed key generation protocol is a different scheme and is not covered here.
FROST2 was introduced with a proof of security under OMDL in the programmable random-oracle model — CKM21. With trusted key generation, FROST and FROST2 are unforgeable in the random-oracle model if OMDL is hard, in notions of the BCK+22 hierarchy stronger than unforgeability above; with key generation by PedPoP, the Pedersen DKG in which each party also proves possession of its secret contribution, FROST2 is proved secure in the random-oracle model under OMDL together with a Schnorr knowledge-of-exponent assumption, which the simulation of PedPoP needs — BCK+22.
Threshold DSA and ECDSA
In DSA and ECDSA the signing equation is not linear in the shared secrets and , unlike the Schnorr equation , so a threshold protocol must compute the inverse of a shared nonce and a product of shared values — standard.
- For DSS, with corrupted parties, any parties produce a signature and corrupted parties cannot forge, with no trusted dealer and with unforgeability reduced to that of DSS itself; a robust version tolerates a smaller fraction of maliciously faulty parties — GJKR96.
- Two-party ECDSA, in which both parties sign, can have one party hold a Paillier encryption of the other’s key share and evaluate the signing equation under the encryption — Lin17.
- Gennaro and Goldfeder give threshold ECDSA in this page’s convention, any of parties signing, for every , with dealerless key generation and security against a dishonest majority — GG18. Lindell and Nof give a full-threshold ECDSA protocol, in which any of parties sign and security holds against corrupted parties for every , with practical distributed key generation — LN18b.
Other results
- Threshold cryptography originates in Desmedt’s society- and group-oriented cryptography — Des87 — and in Desmedt and Frankel’s threshold cryptosystems — DF89. The decryption analogue of a threshold signature is threshold encryption.
- Boldyreva builds both a threshold scheme and a multi-signature from BLS signatures: the threshold scheme interpolates shares of one Shamir-shared key, while the multisignature multiplies signatures under independently generated keys and verifies under the product of the signers’ public keys — Bol03.
- A multi-signature with key aggregation, such as MuSig, also outputs a signature that verifies under one key, but that key is computed by from public keys the signers generate independently, without interactive key generation, and every signer whose key was aggregated takes part in signing — MPSW19.
- In an accountable-subgroup multisignature, any subset of a group of signers can sign, and a valid signature identifies — MOR01, BDN18. In Shoup’s and Boldyreva’s threshold schemes the combined signature is the unique RSA full-domain-hash or BLS signature on under , so it is the same whichever parties produced it — standard.
Participates in
Builds on Threshold signature
- Adaptively secure threshold signature ⇒ Threshold signature (via Adaptive corruption)
- FROST ⇒ Threshold signature (via FROST)
- Threshold RSA signatures ⇒ Honest-majority threshold signature (via Threshold RSA)
- Threshold signature ⇒ Honest-majority threshold signature
Produces Threshold signature
- Adaptively secure threshold signature ⇒ Threshold signature
- FROST ⇒ Threshold signature
- RSA (safe-prime moduli) ⇒ Threshold RSA signatures (Shoup) (via Threshold RSA)
- Threshold RSA signatures ⇒ Honest-majority threshold signature (via Honest majority ())
- Threshold signature ⇒ Honest-majority threshold signature (via Honest majority ())