Dividing a secret

The brilliant idea: a polynomial

How do we obtain the magical threshold property? Shamir's idea is of rare elegance: it rests on a simple observation from geometry.

How many points to fix a curve?

Let's go back to school:

Through 1 point, infinitely many lines pass.
Through 2 distinct points, a single line passes.
Through 2 points, infinitely many parabolas pass; but through 3 points, only one.

The general rule is clear:

A polynomial of degree (k - 1) is uniquely
determined by k distinct points.

degree 1 (line)      <- 2 points
degree 2 (parabola)  <- 3 points
degree 3 (cubic)     <- 4 points
...
degree k-1           <- k points

Fewer than k points are never enough: infinitely many candidate curves remain. This is exactly the boundary we need.

Shamir's brilliant idea

We hide the secret in a polynomial, then distribute points of that polynomial as shares.

Concretely, for a (k, n) scheme:

The secret S becomes the constant term of the polynomial: S = P(0).
We choose the other coefficients a_1, ..., a_{k-1} at random.

P(x) = S + a_1·x + a_2·x^2 + ... + a_{k-1}·x^{k-1}
       ^
       constant term = the secret = P(0)

The polynomial has degree k - 1.

We compute n points: P(1), P(2), ..., P(n). Each share is a pair (i, P(i)).
We never use the point x = 0, since it would reveal S directly.

Reconstructing means recovering the polynomial

Since the polynomial has degree k - 1, k points are both necessary and sufficient to fully reconstitute it. Once the polynomial is known, we evaluate it at 0:

k shares  -->  polynomial P recovered  -->  S = P(0)

The simplest example: k = 2 (a line)

Let's hide S = 7 with a threshold k = 2. We draw one coefficient at random, say a_1 = 3, giving the line:

P(x) = 7 + 3x

Distributed shares:
  P(1) = 10   -> share (1, 10)
  P(2) = 13   -> share (2, 13)
  P(3) = 16   -> share (3, 16)

  y
16 |              * (3,16)
13 |        * (2,13)
10 |  * (1,10)
 7 |* <- P(0) = S = 7  (secret, never distributed)
   +------------------- x
   0   1   2   3

Any two shares, for example (1, 10) and (3, 16), give back the unique line that connects them, hence P(0) = 7. A single share says nothing: infinitely many lines pass through a single point.

Summary