Secret Sharing & Threshold Schemes

Some keys must not have a single holder. A root CA key, a cryptocurrency cold wallet, a disaster-recovery master key, a nuclear release code — each needs distributed authority, where no one person can act alone and no one person's absence blocks everyone else. Secret sharing provides exactly this, with an information-theoretic guarantee rather than a computational one.

The trivial scheme, and why it isn't enough #

Split a secret $M$ among two parties: generate random $R$ the same length as $M$, give one party $R$ and the other $S = M \oplus R$. Either share alone is a one-time pad ciphertext — perfectly uninformative. Extend to $n$ parties by XOR-ing with $n-1$ random strings.

This is unconditionally secure and useless in practice, because it is an all-or-nothing scheme: lose one share and the secret is gone forever. Schneier makes the point plainly — if one shareholder leaves the company with their piece, nobody can reconstruct, and the remaining holders learn nothing but the length.

Shamir's threshold scheme #

Shamir (1979) fixed this with polynomials over a finite field. An $(m, n)$-threshold scheme produces $n$ shares such that any $m$ reconstruct the secret and any $m-1$ reveal nothing.

Pick a prime $p$ larger than the secret and than $n$. To build a $(3, n)$ scheme, choose a quadratic

$$F(x) = (a x^2 + b x + M) \bmod p$$

with $a, b$ random and discarded after distribution. Share $i$ is the pair $(i, F(i))$. Any three shares give three equations in three unknowns; recover $M$ by Lagrange interpolation at $x = 0$.

That last property is what distinguishes threshold sharing from "splitting the password in half", where each half cuts the search space. Shamir's scheme is information-theoretically secure: $m-1$ shares give an unbounded adversary zero information, not merely insufficient computing time.

Properties and variants #

• Extensible — new shares are just more evaluations; issue one to a new holder without disturbing existing shares.
• Refreshable — periodically re-randomize $a, b$ keeping $M$ fixed, and redistribute. Old shares become useless, which defeats an attacker slowly collecting shares over years (proactive secret sharing).
• Weighted — give an important holder several shares. Schneier's illustration: a general holding three shares and colonels one each, in a $(5, n)$ scheme, means the general plus two colonels or five colonels can act, but neither alone.
• Blakley's scheme (1979, independent) uses intersecting hyperplanes instead of polynomials; correct but with larger shares, so Shamir's is what gets deployed.

Where this is actually used #

• Key ceremonies. Root CA and DNSSEC root KSK operations split the activation material among officers, in a filmed procedure with multiple custodians — no single person can activate the key.
• Cryptocurrency custody. Institutional cold storage splits the seed across geographies and officers; consumer wallets expose it as "Shamir backup" (SLIP-39).
• HSM administration. FIPS 140 modules commonly require $m$ of $n$ smartcards to authorize sensitive operations.
• Threshold signatures — the important modern generalization. Rather than reconstructing the key and thereby exposing it, threshold cryptography lets $m$ parties jointly produce a signature while the private key never exists anywhere. NIST IR 8214 covers this; threshold ECDSA and FROST (threshold Schnorr) are deployed in custody and validator infrastructure.

Source claims audit #

The worked example and the general framing were seeded from Applied Cryptography ch. 3.6–3.7 and 23.2.