Shamir's Secret Sharing: Polynomial Math

Shamir's Secret Sharing (1979) encodes the secret as the y-intercept (f(0)) of a random degree-(k-1) polynomial over a finite field. Any k points uniquely determine the polynomial (Lagrange interpolation); fewer than k points reveal nothing.

To share secret S with threshold k among n parties: choose a prime p > S and n. Pick random coefficients a_1, ..., a_{k-1}. Define f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Party i receives share (i, f(i)).

Secret S=7, p=17, k=2 (linear polynomial). Pick a_1=3. f(x)=7+3x mod 17. Shares: (1,10), (2,13), (3,16). Any two points determine the line. f(0)=7. One point alone: infinite possible lines, zero information about S.

Given k points (x_1,y_1),...,(x_k,y_k), reconstruct f(0) using Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. All arithmetic is modular. No floating point — exact reconstruction over the finite field.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

For k-1 shares, there exists exactly one polynomial of degree k-1 through those k-1 points for every possible secret value S. So knowing k-1 shares, every value of S in [0, p-1] is equally likely — zero information is revealed.

p must be larger than the secret and n. Common choice: p = 2^127-1 (Mersenne prime) for 128-bit secrets. This ensures all shares fit in 128 bits and arithmetic is efficient. Alternatively use p=2^521-1 for 512-bit secrets.

Basic SSS has no share integrity: a malicious shareholder can submit a false share, causing wrong secret reconstruction. Feldman VSS (Verifiable Secret Sharing) publishes commitments g^{a_i} mod p, allowing shares to be verified without revealing the polynomial.

Shares can be refreshed periodically: generate new polynomial with same secret S, redistribute new shares, old shares become invalid. An attacker who compromises a shareholder after refresh gets a useless old share. Used in long-lived key management systems.

ssss (Linux command-line), python-secret-sharing, hashicorp/vault uses SSS for its seal mechanism, Trezor hardware wallet uses SSS for wallet seed backup (SLIP-39). All operate over large prime fields.

SSS requires trusted dealer to generate and distribute shares (dealer knows the secret). No dealer scenario requires DKG (Distributed Key Generation). Reconstruction reveals the secret to whoever holds k shares — eliminated by MPC/threshold signatures.

In Shamir's (3,5) secret sharing, what is the minimum number of shares needed to reconstruct the secret?

Shamir's SSS encodes secrets as polynomial y-intercepts. Lagrange interpolation recovers the secret from k shares. Perfect information-theoretic security for fewer than k shares. Next: visual and additive secret sharing.