Shamir's Secret Sharing: a polynomial that hides a secret

Inspired by Ente’s writeup, How Shamir’s Secret Sharing works — which they use inside their Legacy Kit to hand out recovery shares to people you trust without trusting any one of them.

Suppose you want to split a secret — a password, an encryption key, the location of a buried hard drive — into n pieces, hand them to n people, and guarantee two things at once:

1. Any k of them can reconstruct the secret by combining their pieces.
2. Any k − 1 of them learn absolutely nothing — not “very little,” not “less than before,” literally nothing they couldn’t have known without their shares.

That second property sounds impossible the first time you hear it. With k − 1 shares in hand, surely you’ve at least narrowed it down? Adi Shamir’s 1979 scheme says no — and the reason is a single, almost embarrassingly simple fact about polynomials.

Two of n: a line through two points

Start with the easy case: k = 2. Pick the secret to be a number S. Now pick a random number a, and draw the line:

f(x) = S + a · x

The secret is the y-intercept: f(0) = S. Hand each shareholder a point on this line — person 1 gets (1, f(1)), person 2 gets (2, f(2)), and so on, up to n people total.

Two points determine exactly one straight line. So any two shareholders can put their points side-by-side, draw the line through them, and read off where it hits the y-axis — that’s the secret.

A single shareholder, though, has one point. Through one point pass infinitely many lines, and each line has a different y-intercept. Their share is consistent with every possible value of S. That’s not a metaphor: there is no computation you can run on a single share that yields any information about the secret, because every possible secret produces a perfectly valid corresponding share.

k of n: a polynomial of degree k − 1

Once you see the line trick, the generalization writes itself. To require k shares instead of 2, use a polynomial of degree k − 1:

f(x) = S + a₁·x + a₂·x² + … + a_{k-1}·x^{k-1}

where the secret S is again the y-intercept (f(0)), and a₁, …, a_{k-1} are random. Each shareholder i gets (i, f(i)).

The relevant fact is: k distinct points determine a unique polynomial of degree k − 1. (Three points pin down a parabola; four pin down a cubic.) So any k shareholders can reconstruct the polynomial, evaluate it at 0, and recover S. Fewer than k points, though, don’t pin the polynomial down — there are infinitely many polynomials of degree k − 1 that fit any set of k − 1 or fewer points, each with a different y-intercept.

Try it

Click a share to reveal it. With fewer than k revealed, the ghost curves are alternative polynomials that pass through the same revealed points but have completely different secrets at f(0) — every one is just as consistent with what you know. Once you have k, the curve snaps into place and the secret reads straight off the y-axis.

Push k up to 4 or 5 and watch the curve wiggle more. The shares are still just points on a polynomial; there are just more degrees of freedom to constrain before the curve is locked in.

Reconstruction: Lagrange interpolation

Reconstructing the polynomial from k points is a one-line formula called Lagrange interpolation. Given points (x₁, y₁), …, (x_k, y_k), the unique degree-(k − 1) polynomial through them is:

f(x) = Σ_{i=1..k}  y_i · ℓ_i(x)

         where  ℓ_i(x) = ∏_{j ≠ i}  (x − x_j) / (x_i − x_j)

Each ℓ_i(x) — the Lagrange basis polynomial — is constructed so that it equals 1 at x = x_i and 0 at every other x_j. So f(x_i) = y_i for each share point, exactly as required, and the sum is a polynomial of degree at most k − 1.

Since we only care about the secret, we don’t need to recover the whole polynomial — just f(0):

S = f(0) = Σ_{i=1..k}  y_i · ∏_{j ≠ i}  (−x_j) / (x_i − x_j)

Notice that the multipliers ∏(−x_j)/(x_i − x_j) depend only on which shareholders show up — not on the secret, not on the random coefficients. The set of k x-coordinates is the only thing that matters.

Information-theoretic security

Here’s the property that makes this scheme remarkable. Most cryptosystems are computationally secure: an attacker could break them in principle, but it would take longer than the age of the universe (assuming P ≠ NP, factoring is hard, etc.). Shamir’s scheme is information-theoretically secure: an attacker with k − 1 shares could spend unlimited compute and still learn nothing about the secret.

The reason is the ghost-polynomial argument made formal. For any guess S' of the secret, you can construct a degree-(k − 1) polynomial passing through (0, S') and your k − 1 known share points — that polynomial uses up exactly k degrees of freedom (the k coefficients of a degree-(k − 1) poly) on k constraints, so it exists and is unique. The original polynomial that was actually used is one of these — but you have no way to distinguish it from the polynomial built around the guess S' = 42, or S' = 100000, or any other value. Every possible secret is consistent with every possible k − 1-share set, with the same probability distribution.

This is qualitatively stronger than RSA or AES. There’s no “key length” to grow over time as computers get faster, because there’s no computation to be done — the information just isn’t there.

Finite fields in practice

The visualization above uses real numbers, which is fine for intuition but leaks information in practice: a share like (3, 14.7) tells you the polynomial doesn’t have super-large coefficients, which slightly narrows down the secret. Real implementations work over a finite field — typically GF(2^8) (one byte at a time) or GF(p) for some prime p.

In a finite field, arithmetic is closed under addition and multiplication modulo a fixed structure: there are no “magnitudes” — the elements are just labels, every nonzero value has a multiplicative inverse, and division works exactly. The polynomial evaluation, Lagrange interpolation, all of it carries over with ÷ replaced by “multiply by the modular inverse.” Crucially:

• Shares are uniformly distributed. Without finite fields, share values cluster around values derived from a small range of polynomial outputs. In GF(2^8), each share is a uniformly random byte — there’s no statistical leakage at all.
• No overflow, no precision issues. Lagrange interpolation in GF(p) is exact integer arithmetic mod p, no floats.

A typical real implementation: pick a prime p > 2^B where B is the bit-length of the secret (or process the secret one byte at a time in GF(2^8)), sample uniform random coefficients a_i ∈ {0, …, p − 1}, hand out (i, f(i) mod p) for i = 1..n. To recover, gather k shares and compute the Lagrange interpolation at x = 0, all mod p.

Properties that follow for free

Once you see secrets as polynomials, several useful properties fall out:

• Shareholders are interchangeable. Any k shares work; nobody is privileged. This is what makes the scheme robust to a few shareholders being lost, absent, or even dishonest.
• Adding a share is free. Want to issue a new share to a 6th person? Just evaluate f(6) and hand it over. No need to touch the existing shares.
• Refreshing is cheap. You can re-randomize the non-constant coefficients (a₁, …, a_{k-1}) at any time to invalidate all old shares without changing the secret. Add a polynomial g(x) of degree k − 1 with g(0) = 0, give each shareholder g(i) to add to their share. Old shares (before any have been corrupted/leaked) and new shares don’t mix usefully.
• Linear homomorphism. If two secrets S₁ and S₂ are split using polynomials f₁ and f₂ with the same threshold and the same x-coordinates, then f₁(i) + f₂(i) is a valid share of S₁ + S₂. Shareholders can locally combine their shares to participate in multi-party computation without ever reconstructing either secret. This is the seed of an entire subfield (MPC).

What you don’t get is verifiability — a malicious shareholder can submit a fake share at reconstruction time and the others won’t necessarily catch it; they’ll just reconstruct the wrong secret. Schemes like Feldman’s and Pedersen’s verifiable secret sharing layer commitments on top to fix this, at the cost of some computational (rather than information-theoretic) security assumptions.

Where this actually gets used

• Legacy / inheritance kits. Ente’s “Legacy Kit” splits a recovery key across designated contacts. A k-of-n threshold means losing a single trusted person is recoverable, and any single rogue contact can’t unilaterally seize the account.
• Root key custody. AWS KMS, HashiCorp Vault, certificate authorities, and HSM-backed systems use threshold schemes (often Shamir directly) so that no single operator can unseal or sign with the root key.
• MPC and threshold signatures. Modern threshold schemes for ECDSA and BLS signatures — used in custody products and validators — generalize Shamir into protocols where parties hold shares of a private key and can collaboratively produce signatures without ever reconstructing the key on any one machine.
• Password splitting / cold storage. Hardware wallets, password managers, and offline backups sometimes use Shamir to split a master seed across geographically separated locations.

A small worked example

Let’s say k = 3, n = 5, and the secret is S = 11. Pick random coefficients a₁ = 4, a₂ = 2. Then:

f(x) = 11 + 4x + 2x²

f(1) = 11 + 4 + 2  = 17     →  share #1 = (1, 17)
f(2) = 11 + 8 + 8  = 27     →  share #2 = (2, 27)
f(3) = 11 + 12 + 18 = 41    →  share #3 = (3, 41)
f(4) = 11 + 16 + 32 = 59    →  share #4 = (4, 59)
f(5) = 11 + 20 + 50 = 81    →  share #5 = (5, 81)

Now suppose shares #2, #3, and #5 reconstruct. Plugging into Lagrange at x = 0:

S = 27 · (0−3)(0−5)/((2−3)(2−5)) + 41 · (0−2)(0−5)/((3−2)(3−5)) + 81 · (0−2)(0−3)/((5−2)(5−3))
  = 27 · (15/3) + 41 · (10/−2) + 81 · (6/6)
  = 27 · 5 + 41 · (−5) + 81 · 1
  = 135 − 205 + 81
  = 11   ✓

Two of those shares alone (#2 and #3, say) interpolate to the line f(x) = 13 + 14x, giving “secret” 13 — which is wrong, but you’d have no way to know. The line passes through both their points perfectly; their data is consistent with the wrong answer just as well as the right one.

Source & further reading

• Adi Shamir, How to Share a Secret, Communications of the ACM 22(11), 1979 — the original three-page paper, very readable.
• Ente, How Shamir’s Secret Sharing works — the blog post that prompted this writeup, with the graphical line-through-two-points framing used here.
• Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, CRYPTO ‘91 — extends Shamir to detect cheating shareholders.
• Gennaro, Jarecki, Krawczyk, Rabin, Robust Threshold DSS Signatures, EUROCRYPT ‘96 — early threshold-signature scheme built on Shamir’s foundation, now widely used in custody and validator setups.