Visualizing Shamir’s Secret Sharing

What is Shamir’s secret sharing?

Imagine you need to store a password so that no single person knows it. When enough people come together, they can recover it and use it.

You could split the password into pieces and give each person one. But if one person is unavailable, everyone else is stuck. A more useful setup would give shares to ten people and let any six of them recover the password.

The Israeli mathematician Adi Shamir devised a scheme that does exactly that, and it now bears his name.

Wikipedia explains the full algorithm. Here we’ll use graphs to show the idea behind it.

Polynomials

A polynomial is a sum of powers of x multiplied by constants called coefficients.

f (x) = \sum_{i = 0}^{n} a_{i} x^{i}

The degree is the highest power with a nonzero coefficient. Here are a few examples.

Degree 0: 5
Degree 1: 3x + 6
Degree 2: 6x² + 3x + 6
Degree 3: 19x³ + 17x² + 15x + 13

How many points pin down a curve?

The graph of a first-degree polynomial is a straight line. How many lines can you draw through one point?

Infinitely many. Add a second point, and only one straight line passes through both.

A second-degree polynomial gives us a parabola. One point leaves us with infinitely many possibilities.

Even with two points, infinitely many parabolas still fit.

What about three? Only one parabola fits these three points.

In general, n + 1 points with distinct x-coordinates are enough to recover a polynomial of degree n.

From curves to secret sharing

Shamir’s scheme uses that same idea. The graphs use ordinary numbers so we can see how reconstruction works. The actual scheme uses finite-field arithmetic to protect the secret.

Say we want to split a secret number S into five shares and let any three recover it.
Choose a quadratic whose value at x = 0 is S.
Evaluate it at five distinct, nonzero values of x and give each person one point.
Any three points determine the original polynomial. Evaluate it at x = 0 to recover S.

What about text?

Text is encoded as a sequence of bytes. Each byte represents a number from 0 to 255. Apply the secret sharing scheme to each byte separately.

What if the message is large?

For a long message, you can encrypt it with AES and split the encryption key instead. With AES-128, that means sharing a 16-byte key. Send the encrypted message along with the key shares.

Try it with three out of five points

Where the points come from

If we need any k shares to recover the secret, we use a polynomial of degree k − 1. For three shares, that’s a quadratic f(x) = ax² + bx + C. The constant term C is the secret. We choose the other two coefficients at random.

Take a = 3, b = 7, and a secret of 15. That gives us f(x) = 3x² + 7x + 15. Evaluating it at five different values of x gives us one point per person.

f(1) = 25 gives (1, 25)
f(2) = 41 gives (2, 41)
f(3) = 63 gives (3, 63)
f(4) = 91 gives (4, 91)
f(5) = 125 gives (5, 125)

What if we need 100 out of 500?

Use a polynomial of degree 99 and evaluate it at 500 different nonzero values of x. It has the form ax⁹⁹ + bx⁹⁸ + … + kx + S. Any 100 of those points recover the polynomial and its constant term S.