Cryptographic Foundations

Shamir's Secret Sharing

How to split a secret among multiple parties such that only a threshold can reconstruct it—and fewer learn absolutely nothing.

The Intuition

Imagine you're a bank manager who needs to secure a vault. You want to require that at least 3 out of 5 trusted officers must agree before the vault can be opened. No single officer—or even two colluding—should be able to access it alone.

Adi Shamir's elegant 1979 solution exploits a fundamental property of polynomials: any polynomial of degree k−1 is uniquely determined by k points. Two points define a line. Three points define a parabola. And so on.

Core Insight

Hide the secret as the y-intercept of a random polynomial. Each share is a point on that curve. With fewer than k points, infinitely many polynomials fit—revealing nothing about the secret. With exactly k points, only one polynomial exists.

Interactive Visualization

Below, the secret is the point where the polynomial crosses the y-axis (x = 0). Adjust the threshold and number of shares to see how the scheme works.

Polynomial & Share Distribution

Threshold (k) 3

Shares (n) 5

Secret (y-intercept)

Shares (points)

Polynomial curve

The Mathematics

To create a (k, n) threshold scheme for secret S:

Construct a random polynomial of degree k − 1 with S as the constant term:

f(x) = S + a₁x + a₂x² + ... + aₖ₋₁xᵏ⁻¹

where a₁, a₂, ..., aₖ₋₁ are random coefficients from a finite field

Generate n shares by evaluating the polynomial at n distinct non-zero points:

Share_i = (i, f(i)) for i = 1, 2, ..., n

Each participant receives one coordinate pair

Reconstruct using Lagrange interpolation. Given k shares, compute the unique polynomial and evaluate at x = 0:

S = f(0) = Σᵢ yᵢ · ∏ⱼ≠ᵢ (−xⱼ)/(xᵢ − xⱼ)

The Lagrange basis polynomials isolate each share's contribution

Try Reconstruction

Select shares below to attempt reconstruction. The scheme is configured as (3, 5)—you need at least 3 shares.

Reconstructed Secret

Select shares...

Security Properties

🔐

Perfect Secrecy

With fewer than k shares, an attacker gains zero information about the secret. Every possible secret value remains equally likely.

🧩

Minimal Reconstruction

Exactly k shares are necessary and sufficient. No more, no less. Any k shares work equally well.

📐

Ideal Scheme

Each share is exactly the same size as the secret itself. This is information-theoretically optimal.

➕

Extensible

New shares can be generated without changing existing ones—just evaluate the polynomial at new x-coordinates.

Why Finite Fields?

The visualization above uses real numbers for intuition, but real implementations operate over a finite field. But what exactly is a finite field?

What is GF(p)?

GF(p) (Galois Field of order p) is the set of integers {0, 1, 2, ..., p−1} where all arithmetic is performed modulo p. When p is prime, this forms a field—meaning addition, subtraction, multiplication, and division all work and stay within the set.

For example, in GF(7): 5 + 4 = 9 mod 7 = 2, and 3 × 5 = 15 mod 7 = 1. That last result means 5 is the multiplicative inverse of 3—division is just multiplication by the inverse.

Why does this matter for secret sharing?

Bounded arithmetic: All values stay within {0, ..., p−1}. No overflow, no growing coefficients, no precision loss.
Division always works: In a prime field, every non-zero element has a multiplicative inverse. Lagrange interpolation requires division, so this is essential.
Perfect secrecy: With real numbers, share magnitudes might leak information. In a finite field, every possible secret maps uniformly to every possible share combination.
Efficient implementation: Modular arithmetic maps directly to CPU instructions. No floating point, no arbitrary precision libraries.

Common choices include:

GF(p) for a large prime p—e.g., p = 2⁵²¹ − 1 (a Mersenne prime) for 521-bit secrets
GF(2⁸) for byte-oriented schemes like SLIP-0039 (Shamir backup in hardware wallets)—this is an extension field using polynomial arithmetic
GF(2²⁵⁶) for cryptocurrency applications where secrets are 256-bit scalars

The field choice depends on your secret size and performance requirements, but the beautiful mathematical properties of Shamir's scheme hold in any finite field.

Real-World Applications

Shamir's scheme underpins critical infrastructure across cryptography and distributed systems:

Key management: Splitting master keys across geographic locations or organizational roles
Cryptocurrency wallets: Multi-signature schemes and social recovery (e.g., Shamir backups in hardware wallets)
Secure multi-party computation: Foundation for protocols where parties jointly compute on private inputs
Nuclear launch codes: The canonical "two-person rule" generalized to any threshold

Implementation Sketch

// Simplified SSS over integers (use finite fields in production)

function createShares(secret, k, n) {
  // Generate random coefficients for polynomial
  const coeffs = [secret];
  for (let i = 1; i < k; i++) {
    coeffs.push(randomCoefficient());
  }
  
  // Evaluate polynomial at x = 1, 2, ..., n
  return Array.from({length: n}, (_, i) => ({
    x: i + 1,
    y: evaluatePolynomial(coeffs, i + 1)
  }));
}

function reconstruct(shares) {
  // Lagrange interpolation at x = 0
  let secret = 0;
  for (let i = 0; i < shares.length; i++) {
    let basis = shares[i].y;
    for (let j = 0; j < shares.length; j++) {
      if (i !== j) {
        basis *= -shares[j].x / (shares[i].x - shares[j].x);
      }
    }
    secret += basis;
  }
  return Math.round(secret);
}