Shamir secret sharing

How it works

Shamir’s scheme hides a secret $s \in \mathbb{F}_p$ as the constant term of a random polynomial $f(x) = s + a_1 x + \cdots + a_{t-1} x^{t-1}$ of degree $t - 1$. Share $i$ is the point $(i, f(i))$. Any $t$ points determine a polynomial of degree $t - 1$ uniquely, so $t$ shares recover $f$ and hence $s = f(0)$.

Reconstruction uses Lagrange interpolation, evaluated directly at 0: $s = \sum_i y_i \lambda_i$ with $\lambda_i = \prod_{j \ne i} x_j / (x_j - x_i) \bmod p$. The coefficients $\lambda_i$ depend only on which shares are used, not on their values.

With $t - 1$ shares or fewer nothing is learned: for every candidate secret there is exactly one polynomial of degree $t - 1$ through those shares and that secret, so all secrets remain equally likely. This is information-theoretic security, independent of any computational assumption. Shamir sharing is linear (shares of $s_1 + s_2$ are the sums of shares), which makes it a building block of threshold cryptography and secure multiparty computation.