Shamir's Secret Sharing: Split a Private Key into $n$ Shares, Recover It from Any $k$

This article has three layers:

1. The intuition: two points determine a line
2. Real-world use: wallet backups, MPC wallets, threshold signatures, the DNSSEC root key
3. The mathematics: polynomials over finite fields, Lagrange interpolation, perfect security and a worked example

Layer 1: The Intuition

1.1 Why "split" a private key

If a Bitcoin private key is stored in only one place:

• Lose it, and the money is gone forever;
• Have it stolen, and the money is gone too.

Keeping several copies protects against loss but multiplies the risk of theft. What we want is: split it into 5 shares for 5 people (or 5 places), so that any 3 together can recover it, while any 2 together are useless. This is called a $(3, 5)$ threshold scheme.

1.2 Two points determine a line

Start with the simplest $(2, n)$ scheme:

1. Plot the secret $S$ on the $y$-axis, as the point $(0, S)$;
2. Draw any line (with a random slope) through this point;
3. Take the points on the line at $x = 1, 2, \dots, n$, and give one to each person.

Any two people put their points together; two points determine a line, and extending it to the $y$-axis reveals $S$. But someone holding just one point sees infinitely many lines through it, meeting the $y$-axis at any value at all, so they can't guess $S$ at all.

For a threshold of 3, replace the line with a parabola (three points determine a parabola); for a threshold of $k$, use a polynomial of degree $k-1$.

1.3 The same thing as Reed–Solomon codes

Reed–Solomon error correction treats data as polynomial coefficients and sends the polynomial's values at many points, so the data can be interpolated back even if some points are lost. Shamir's secret sharing uses the same evaluation map with a different emphasis: error-correcting codes care about "recovering what was lost", while secret sharing also cares that "too few points reveal nothing".

Layer 2: Real-World Use

Layer 3: The Mathematics

3.1 Working in a finite field

Polynomials over the real numbers leak information (the size of a share can hint at the range of the secret), so everything happens in a finite field $\mathbb{F}_p$, where $p$ is a prime larger than the secret.

Distribution: the secret is $S \in \mathbb{F}_p$, with threshold $k$. Randomly choose $a_1, \dots, a_{k-1} \in \mathbb{F}_p$ and let

$$f(x) = S + a_1 x + a_2 x^2 + \cdots + a_{k-1} x^{k-1},$$

and person $i$ receives the share $(i, f(i))$, for $i = 1, \dots, n$.

3.2 Why $k$ points determine the polynomial uniquely

A nonzero polynomial of degree at most $k-1$ over a field has at most $k-1$ roots (abstract algebra: $F[x]$ is an integral domain, and the factor theorem). If two polynomials of degree $\le k-1$ agree at $k$ points, their difference has $k$ roots and must be the zero polynomial. So it is unique.

3.3 Lagrange interpolation

Given $k$ points $(x_j, y_j)$, construct

$$L_j(x) = \prod_{m \ne j} \frac{x - x_m}{x_j - x_m},$$

which equals $1$ at $x_j$ and $0$ at the other $x_m$. Then $f(x) = \sum_j y_j L_j(x)$. We only need the constant term:

$$S = f(0) = \sum_j y_j \, L_j(0),\qquad L_j(0) = \prod_{m \ne j} \frac{-x_m}{x_j - x_m}.$$

Note that $S$ is a linear combination of the shares. This is crucial: in threshold signatures, the parties needn't hand over their shares; each computes only the part "share $\times L_j(0)$", and these are added in the exponent or as elliptic curve points.

3.4 Why $k-1$ shares reveal nothing

Fix any $k-1$ shares. For every candidate value of the secret $S' \in \mathbb{F}_p$, adding the point $(0, S')$ gives $k$ points in all, which determine exactly one polynomial. So each $S'$ corresponds to the same number (exactly one) of coefficient choices, and since coefficients are chosen uniformly at random, each $S'$ has probability $1/p$.

This is called information-theoretic security (perfect security): it depends on no computational hardness, and no amount of computing power, quantum or otherwise, helps. The reasoning is the same as for the one-time pad.

3.5 A worked example

Summary