JA

How Shamir's secret sharing and Lagrange interpolation fit together

Introduction

In the previous post, I introduced secret sharing and secure computation together as techniques for handling data you want to use but cannot let out of the building. They form a pair: secret sharing splits the data into shares when it goes in, and secure computation works on it while it stays split.

This time I dig into the secret sharing side. Anyone who reads up on it quickly runs into “Shamir’s secret sharing” and “Lagrange interpolation”, so here I lay out how the two are connected.

Here is what this post covers:

What secret sharing is

Secret sharing splits one piece of secret information into several shares (fragments) so that the original secret can be recovered only when a certain number of shares come together. This is called a (k, n) threshold scheme, and it is defined by two parameters:

  • n: the number of people who receive a share
  • k: the minimum number of people needed to recover the secret (the threshold)

With (2, 3), for example, shares go to three people and any two of them can recover the secret. The diagram in the previous post showed a simple form where every share had to be present; this scheme lets you choose how many people need to come together.

Shamir’s idea: embed the secret in a polynomial

The core of Shamir’s secret sharing is the idea of embedding the secret as the constant term of a polynomial.

Let the secret be s. The dealer (the person distributing the shares) builds a random polynomial of degree k-1:

f(x) = s + a1・x + a2・x^2 + … + a(k-1)・x^(k-1)
  • The constant term is the secret s (that is, f(0) = s)
  • a1, …, a(k-1) are random numbers chosen by the dealer

Each participant i (i = 1, 2, …, n) then receives the point (i, f(i)) as their share. A participant holds only one pair — an x coordinate (their number) and a y coordinate (the computed value) — and knows nothing about the polynomial itself.

In real implementations this arithmetic is done not over the real numbers but over a finite field (modulo a sufficiently large prime p). Over the reals, the size of a share would hint at the range of the secret, and the “information-theoretically secure” property described below would no longer hold.

Why use a polynomial

Polynomials have a mathematically guaranteed property:

A polynomial of degree k-1 is uniquely determined by k points with distinct x coordinates.

Put another way, with fewer than k points there are infinitely many polynomials of that degree that fit. The line between “uniquely determined” and “not determined” maps directly onto the threshold k of secret sharing.

  • k or more shares come together → the polynomial is pinned down to exactly one → f(0) = s can be computed
  • k-1 or fewer shares come together → there are infinitely many candidate polynomials → s cannot be identified (information-theoretically secure)

“Information-theoretically secure” means no amount of computing power can break it. There are infinitely many candidates and all of them are equally likely, so even brute force cannot narrow them down.

The role of Lagrange interpolation

Lagrange interpolation is the tool for actually computing the degree k-1 polynomial that passes through k given points.

Given k points (x1, y1), …, (xk, yk), Lagrange interpolation builds the polynomial with this formula:

The Lagrange interpolation formula. f(x) is the sum, over i from 1 to k, of yi times the product, over all j other than i, of (x - xj) divided by (xi - xj) f(x) = Σ k i=1 yi × Π j≠i x − xj xi − xj

It looks complicated, but what it does is simple. The fraction in each term is a basis polynomial built to equal 1 at x = xi and 0 at every other xj. Multiply each one by its yi and add them all up, and you get exactly the expression that passes through every point.

To recover a secret, you just substitute x = 0 into this formula:

The recovery formula. The secret s equals f(0), which is the sum, over i from 1 to k, of yi times the product, over all j other than i, of -xj divided by (xi - xj) s = f(0) = Σ k i=1 yi × Π j≠i − xj xi − xj

In other words, recovery is nothing more than plugging the k collected shares into the Lagrange interpolation formula and computing the value at x = 0.

Building intuition with a line and a parabola

Lower degrees are easier to picture, so let’s look at a concrete example.

First, k = 2 (degree 1, a straight line). With the secret s = 1234 and the random coefficient a1 = 56, the polynomial is f(x) = 1234 + 56x. The shares handed to three people are these three points:

ParticipantShare
1f(1) = 1290
2f(2) = 1346
3f(3) = 1402
Three shares lie on one straight line; any two of them fix the line, and its y-intercept is the secret f(0) is the secret Share 1 Share 2 Share 3 0 1 2 3

Reading the figure: all three shares lie on the same straight line. Two points are enough to fix a line, so any two participants can draw it, and its y-intercept is the secret. With only one point, infinitely many lines pass through it, so the secret could be any value.

Let’s actually recover the secret from the shares of participants 1 and 3. All it takes is putting x = 0 into the Lagrange interpolation formula:

s = 1290 × (0-3)/(1-3) + 1402 × (0-1)/(3-1)
  = 1290 × 1.5 − 1402 × 0.5
  = 1935 − 701
  = 1234

Even without participant 2, we get back the original 1234.

Next, k = 3 (degree 2, a parabola). With only two points, infinitely many parabolas pass through them, because there is still freedom in how the curve bends. Only when a third point is added is the parabola pinned down to exactly one.

The higher the degree, the more points it takes to recover the secret. In other words, k is also the parameter that decides how many people have to collude before the secret leaks.

Summary

ConceptRole
Shamir’s secret sharingA scheme that embeds the secret in the constant term of a polynomial and hands each participant a point on that polynomial
Lagrange interpolationThe computation that rebuilds the original polynomial from the collected points and finds f(0)
Threshold kThe polynomial’s degree plus one. Once this many points come together, the polynomial is mathematically determined uniquely

Shamir’s secret sharing bases its security on the mathematical fact that a polynomial is uniquely determined by k points, and Lagrange interpolation is the means of actually computing that unique polynomial. Framing the relationship that way makes the whole thing easier to understand.

References