Lagrange Interpolation and Secret Sharing

Interactive Demo

Lagrange interpolation, named after Joseph-Louis Lagrange, finds the unique polynomial of degree at most n − 1 through n points with distinct x-coordinates. I built this demo to show how the curve changes as you add and move points.

Open the full-screen interpolation demo.

Tap to add a point. Drag a point to move it. Keep the points at distinct x-coordinates so the polynomial is defined.

Secret Sharing

Shamir's Secret Sharing divides a secret into n shares, with a threshold t. Any t distinct valid shares can reconstruct the secret; no particular combination is required.

The demo above uses real-number coordinates to illustrate interpolation. It is not a cryptographic implementation. Shamir's scheme, introduced by Adi Shamir, needs finite-field arithmetic and securely generated random coefficients.

How It Works

1. Choose the field and threshold: Use a finite field large enough to represent the secret and provide n distinct non-zero x-coordinates. Choose a threshold t between 1 and n.
2. Create the polynomial: Encode the secret s as a field element. Choose t − 1 coefficients independently and uniformly at random from the field, using a cryptographically secure random source. With s as the constant term, these form a polynomial of degree at most t − 1.
3. Create the shares: Evaluate the polynomial at each chosen x-coordinate. Each share is a pair containing the x-coordinate and its corresponding value.
4. Recover the secret: Use Lagrange interpolation in the same finite field with any t distinct valid shares. Evaluate the recovered polynomial at zero to obtain s.

With this construction, fewer than t shares reveal no additional information about the secret. Using ordinary real-number arithmetic or predictable coefficients does not provide that guarantee.

Applications

One use is master-key recovery, as explored in my password manager project. Shares can be held by different people or stored separately, with a threshold needed to recover the key.

Educational Video

This video explains the connection between interpolation and secret sharing: