Shamir's Secret Sharing

Shamir's Secret Sharing

Shamir's Secret Sharing (Adi Shamir, 1979) splits a secret into $n$ shares such that any $t$ shares can reconstruct the secret, but any $t-1$ shares reveal absolutely nothing. This is called a $(t, n)$-threshold scheme.

Construction

1. Represent the secret as an integer $s$ (the constant term of a polynomial)
2. Choose a random polynomial of degree $t-1$: $f(x) = s + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1} \pmod{p}$ where $p$ is a prime larger than both $s$ and $n$
3. Give party $i$ the share $(i, f(i))$ for $i = 1, 2, \ldots, n$

Reconstruction — Lagrange Interpolation

Given $t$ shares $(x_1, y_1), \ldots, (x_t, y_t)$, reconstruct $f(0) = s$ using Lagrange interpolation modulo $p$:

$s = f(0) = \sum_{i=1}^{t} y_i \prod_{j \neq i} \frac{-x_j}{x_i - x_j} \pmod{p}$

The modular division uses Fermat's little theorem: $a^{-1} \equiv a^{p-2} \pmod{p}$.

Security

With fewer than $t$ shares, the secret is information-theoretically hidden — any value of $s$ is equally likely. This is provably secure, unlike computational security assumptions.

Applications

• Distributed key management — split private keys across multiple servers
• Disaster recovery — $m$-of-$n$ backup schemes
• Secure multi-party computation — building block for advanced protocols

Our Deterministic Version

For testability, we use deterministic coefficients: $a_i = (s \times i \times 1337) \bmod p$ (instead of random).

Your Task

Implement:

• shamir_share(secret, n, threshold, prime=2**31-1) — generate $n$ shares using a degree-$(t-1)$ polynomial
• shamir_reconstruct(shares, prime=2**31-1) — Lagrange interpolation to recover the secret