Secret Sharing

The Single Point of Failure

You have a secret: a master key, a password, nuclear launch codes.

One person holds it. What could go wrong?

• They die unexpectedly
• They get compromised
• They go rogue
• They simply forget

A secret held by one person is a single point of failure.

The Solution: Split It

Secret sharing splits a secret into multiple shares distributed among different people.

• No single person can reconstruct the secret alone
• A minimum number must cooperate (the threshold)
• Below that minimum, nothing is revealed

The combiner could be one of the players, or a separate trusted party.

Threshold Schemes: (t, n)

A (t, n) threshold scheme splits a secret into $n$ shares such that:

• Any $t$ or more shares can reconstruct the secret
• Fewer than $t$ shares reveal absolutely nothing

Example: A (3, 5) scheme:

• 5 people each get one share
• Any 3 can recover the secret
• Any 2 learn zero information

$t$ = threshold (minimum needed), $n$ = total shares

The Naive Approach Fails

Why not just split the secret into pieces?

The problem: Each piece reveals partial information.

With SECR, you’ve already narrowed down possibilities. That’s a leak.

True secret sharing must be all-or-nothing. Below threshold = zero information. Not “less” information.

Shamir’s Secret Sharing

Adi Shamir (the S in RSA) invented this in 1979.

The key insight: A polynomial of degree $t-1$ is uniquely determined by exactly $t$ points.

With fewer points, infinitely many polynomials fit. You learn nothing about which one is correct.

The Setup

Dealer wants to share secret $S$ with:

• Threshold: $t$ (minimum shares needed)
• Players: $n$ (total shares)

The dealer will build a polynomial where the secret is hidden at $f(0)$.

Step 1: Build a Random Polynomial

The dealer constructs:

$f(x) = S + a_1 x + a_2 x^2 + \ldots + a_{t-1} x^{t-1}$

• Constant term = the secret $S$
• Other coefficients $a_1, a_2, \ldots, a_{t-1}$ = random values
• Degree = $t - 1$

The secret sits at $f(0) = S$. The randomness hides everything else.

Step 2: Generate Shares

The dealer evaluates the polynomial at $n$ different points:

Each player receives one point on the polynomial.

Step 3: Reconstruct the Secret

When $t$ players combine their shares:

1. They have $t$ points on a degree $t-1$ polynomial
2. Use Lagrange interpolation to recover the unique polynomial
3. Evaluate $f(0)$ to get the secret $S$

With exactly $t$ points, there’s exactly one polynomial that fits. The secret is determined.

Why Fewer Shares Reveal Nothing

With only $t-1$ points on a degree $t-1$ polynomial:

Infinitely many polynomials pass through those points.

For any possible secret value $S$, there exists a valid polynomial with $f(0) = S$.

You can’t even narrow down. The secret could literally be anything.

Concrete Example: (2, 3) Scheme

Secret: $S = 42$

Threshold: $t = 2$

Players: $n = 3$

Step 1: Build a degree 1 polynomial (a line):

$f(x) = 42 + 7x$

The coefficient $7$ is chosen randomly.

Step 2: Generate shares:

Step 3: Reconstruction

Any 2 players can find the line through their points and compute $f(0) = 42$.

1 player alone? Infinitely many lines pass through one point. The secret could be any value.

Information-Theoretic Security

This isn’t “computationally hard to break.” It’s impossible.

With $t-1$ shares, every possible secret is equally consistent with your data. No amount of computing power helps.

Unconditional security. Not based on assumptions. Mathematically absolute.

Applications

Key Insight

Secret sharing transforms a single point of failure into distributed trust.

The secret exists nowhere until enough parties cooperate. No single share, no single person, no single server holds the answer.

The whole is recoverable. The parts are useless.