Shamir's Secret Sharing

A master key, a cryptocurrency wallet's seed, a nuclear launch code — some secrets are too sensitive to hand to any one person, and too important to risk losing if that one person is unavailable, compromised, or dishonest. Adi Shamir's 1979 secret sharing scheme solves both problems at once: split a secret into n shares, distributed to n different participants, such that any k of them can reconstruct the original secret exactly — and any k−1 reveal absolutely nothing about it, not even a probabilistic hint.

This is a (k, n)-threshold scheme: k is the number of shares required, n is the total number handed out. Unlike simply cutting the secret into n pieces (which would need every single piece back), a threshold scheme tolerates up to n−k missing or unavailable shares — lost hardware, an absent officer, a departed employee — while still recovering completely once enough shares are present.

The entire scheme rests on one fact from basic algebra: two points determine a unique line; three points determine a unique parabola; in general, k points uniquely determine a polynomial of degree k−1 — and with only k−1 points, infinitely many different degree-(k−1) polynomials still pass through them all, with no way to narrow it down further.

Shamir's insight: hide the secret as the constant term of a random polynomial of degree k−1, and hand each participant one other point on that polynomial's curve as their share. Reconstructing needs exactly k points — the threshold — because that's exactly how many it takes to pin the polynomial down uniquely.

To share a secret s with threshold k among n participants: pick a prime p larger than both the secret and the number of participants, then choose k−1 random coefficients a₁, …, a_{k−1} to build the polynomial f(x) = s + a₁x + a₂x² + ⋯ + a_{k−1}x^{k−1} mod p. Each participant i (for i = 1, …, n) receives the point (i, f(i)) as their share. Notice x = 0 is never handed out to anyone — that point is the secret itself.

Worked example: share the secret s = 13 with threshold k = 3 among n = 5 participants, working mod p = 23. Pick random coefficients a₁ = 2, a₂ = 4, giving f(x) = 13 + 2x + 4x² mod 23. Evaluating at x = 1 through 5 gives the five shares: (1, 19), (2, 10), (3, 9), (4, 16), (5, 8). The dealer then destroys the polynomial and every coefficient, keeping no copy of the secret anywhere.

Given any k shares, Lagrange interpolation reconstructs the unique polynomial through them and evaluates it at x = 0 to recover the secret directly — without ever rebuilding the coefficients a₁ through a_{k−1} along the way. For each share (xⱼ, yⱼ), its contribution to the secret is yⱼ multiplied by a basis term built from every other chosen share's x-coordinate; the terms from all k shares add up to exactly s.

Worked example: reconstruct s from shares (1, 19), (2, 10), and (3, 9). Each share's term is yⱼ times a fraction built from the other two x-values, reduced mod 23 using modular inverses (the same extended-Euclidean technique from the math foundations module): the share at x=1 contributes 11, the share at x=2 contributes 16, and the share at x=3 contributes 9. Summed: 11 + 16 + 9 = 36 ≡ 13 (mod 23) — the original secret, recovered exactly, with no rounding and no approximation.

With only k−1 shares, every possible secret value remains exactly equally consistent with what's held — for any candidate secret, there's precisely one polynomial of the right degree that fits both the held shares and that candidate. No computational shortcut narrows this down, because there's genuinely nothing to compute toward: this is information-theoretic security, the same category of guarantee Shannon proved for the one-time pad in the history module, not merely computational security like AES or RSA.

That's a meaningfully stronger guarantee than almost everything else in this catalog. An attacker with unlimited future computing power — including a full-scale quantum computer running Shor's algorithm — gains nothing at all from k−1 shares, because the missing information was never encoded in the shares in a breakable form to begin with.

Secret sharing underpins several real, widely deployed systems: threshold wallets and HSMs, where a cryptocurrency key or hardware security module operation requires k of n officers to cooperate before anything can be signed or spent; threshold signatures and multi-party computation (MPC), which extend the same idea to computing or signing without ever assembling the full key in one place, even transiently; and key backup and escrow, recovering a lost key from a quorum of custodians while tolerating some number of them being unreachable.