Security and reconstruction

Reconstruction by Lagrange interpolation

We know that k points are enough, in principle. The practical question remains: how do we actually reconstruct the secret from k shares? The answer is Lagrange interpolation.

The principle of Lagrange interpolation

Given k points, Lagrange interpolation directly provides the unique polynomial of degree k - 1 that passes through all these points. Since we only want S = P(0), we can evaluate the formula at 0 without even writing out the full polynomial:

Shares: (x_1, y_1), (x_2, y_2), ..., (x_k, y_k)

            k                    x_j
S = P(0) =  Σ   y_i ·  ∏   ---------------
           i=1        j≠i     x_j - x_i

Each share y_i is weighted by a coefficient that depends only on the x-coordinates x_i. We combine everything, and we obtain S.

A complete example with k = 2

Let's take the line from the previous lesson again. We are given two shares, (1, 10) and (3, 16), and we look for S = P(0):

          x_2                x_1
S = y_1·-------  +  y_2·-------
        x_2-x_1          x_1-x_2

         3               1
= 10·-------  +  16·-------
       3-1             1-3

= 10·(3/2)  +  16·(-1/2)
= 15 - 8
= 7                      <- secret recovered !

We indeed recover S = 7, without having needed the third share. Any two shares would have given the same result.

Why a finite field is indispensable

In the examples, we worked with ordinary integers. In reality, Shamir requires all arithmetic to be done modulo a large prime number p: we work in the finite field written GF(p). Three major reasons:

Precision. Reals and fractions generate rounding errors. In a finite field, everything is an integer and exact — division becomes a multiplication by a modular inverse, always defined.
Perfect secrecy. Over ordinary integers, the magnitude of the values P(i) leaks information about the coefficients, hence about S. A finite field bounds all values in [0, p-1] uniformly: the perfect secrecy of the previous lesson is rigorously true only in a finite field.
Uniformity. Drawing the coefficients at random in [0, p-1] makes each secret equally probable, which is the key to the proof.

Complete reconstruction chain:

  k shares (x_i, y_i)
        |
        |  Lagrange interpolation (mod p)
        v
   polynomial P (implicit)
        |
        |  evaluation at x = 0
        v
   S = P(0)  = the secret

What to take away from the whole thing

Shamir's scheme is remarkable: simple to state, proven secure, and flexible (you can add shares without changing the secret, adjust the threshold, etc.). This is why it appears in master key management, cryptocurrency wallets, and security ceremonies.

Summary