Shamir's Secret Sharing

Adi Shamir — the S in RSA — published ‘How to Share a Secret' in 1979, a paper of barely two pages. George Blakley published a different construction, using intersecting hyperplanes, in the same year. Shamir's version won out because it is simpler, because share size does not grow with the number of participants, and because the mathematics it needs was already three centuries old: fitting a polynomial through a set of points, a technique Lagrange had formalised in 1795.

The whole scheme rests on one fact from school algebra. Two points determine a straight line. Three determine a parabola. In general, k points determine exactly one polynomial of degree k−1 — and k−1 points determine nothing at all, because infinitely many curves of that degree pass through them.

So hide the secret as a polynomial's constant term. Pick k−1 random coefficients above it, evaluate the polynomial at x = 1, 2, 3, … and hand out those values as shares. Any k shareholders can interpolate back to the curve and read off its value at zero. Any k−1 hold points that fit every candidate secret equally well.

One detail makes the difference between a neat trick and a secure scheme: the arithmetic happens in a finite field, not the ordinary numbers. Over the reals, the slope between two shares would leak information about where the curve is heading. Modulo a prime, it leaks none.

Arithmetic runs modulo the prime 257, so a secret is one byte. Choose a threshold, deal the shares, then tick shareholders to bring them into the room.

Deal the shares to begin.

It is easy to say ‘fewer than k shares reveal nothing'. Here is the claim made checkable. Below, every one of the 257 possible secrets is tested against the shares currently in the room: for each candidate, is there a polynomial of degree k−1 that passes through those shares and hits that value at zero?

With k−1 shares, the answer is yes for all 257 — the shares are consistent with every secret, so they single out none. Add one more share and exactly one survives.

Each cell is one candidate secret from 0 to 256. Gold means ‘still possible given the shares revealed'.

There is no cryptanalysis of Shamir's scheme, because there is nothing to attack. Its security is information-theoretic, the same standard the one-time pad meets: a quantum computer, or an adversary with unlimited time, gains exactly as much from k−1 shares as from none. The scheme survives Shor's algorithm untouched.

What it does not do is guard against dishonesty. A shareholder who submits a wrong share corrupts the reconstruction silently — everyone walks away with a plausible, useless value and no indication anything went wrong. The scheme assumes participants are honest but may be unavailable. Handling participants who actively cheat needs verifiable secret sharing, which adds commitments so that a bad share can be detected and attributed.

Two other practical cautions: the dealer sees the secret and must be trusted or eliminated by a distributed key-generation protocol, and the random coefficients must be genuinely random — predictable coefficients collapse the whole argument.

The DNSSEC root signing ceremony splits control of the internet's root key among trusted community representatives, so no individual can sign the root zone alone. Hardware security modules split master keys across custodians for backup and recovery. Cryptocurrency custodians shard private keys across jurisdictions. The same threshold logic underlies modern threshold-signature schemes such as FROST, where k parties jointly produce a signature without any of them ever holding the whole key.