Shamir's Secret Sharing

Let’s say you and your eighty friends (you’re extremely popular) were recently offered jobs local bank. Though you are confused about how the bank can do this, you are happy to accept the job.

The main component of the job is that you are in charge of encoding all vault passwords such that only when all eighty-one of you agree to unlock the vault, it unlocks. Otherwise, your fifteen disloyal friends could form a faction and betray you, or one person could go rogue and steal from all the vaults. If you enter an incorrect passcode into a vault, it seals forever and you die.

An example of something that could be done would be an 81 digit passcode - each one of you would receive a digit and the index of your digit in the passcode. For example, you receive “1 (index 0)” and your friend receives “3 (index 1)”. This indicates that the first two digits are 1 and 3.

As you give each person a different number, you realize, wow! This sounds exactly like a cryptography problem!

Then the fourth wall snaps back into place and you continue your tedious bank work.

Now, the problem with this 81 digit passcode is that if your 33rd friend (who has been known to occasionally disappear) vanishes off the face of the Earth one day, you can never get into any of your vaults again.

As a result, you decide that you want any 16 people with information in your group to be able to find the secret. Since you only have 15 people who might betray you, they can’t unlock vaults, and this way, even if more than 60 of your friends disappear, you can still get into the vault.

Then again, if 60 of your friends disappear, you have bigger problems.

Essentially, we want to come up with a way to find a ‘secret’ with $k$ pieces of information, a secret that cannot be built with $k-1$ pieces of information, and can be built with any $k$ pieces of information. For a secret code with $n$ parts, each one given to a different person, this value of $k$ and $n$ forms a $(K, N)$ threshold scheme, and it’s encoded with Shamir’s Secret Sharing Algorithm.

The algoirthm states that for “$K$ points, we can find a polynomial equation with the degree ($K - 1$).”

You’ve probably seen something similar - two points encode a line, three (non-collinear points) a plane, and so forth.

This theorem states that with three points, one can find a quadratic polynomial, and with four, a cubic polynomial.

There is a unique polynomial of degree $\leq n-1$ that passes through $(x_1, y_1), (x_2, y_2) \cdots (x_n, y_n).$

Assume that there are two different polynomials of degree $n-1$ that can exist from the same set of points. Call these polynomials $p(x)$ and $q(x).$

Then, define a new polynomial $p(x) - q(x).$ For all values $i \in {1 \cdots n},$ where $x = x_i$⁠, both $p(x)$ and $q(x)$ are $y_i,$ so $p(x) - q(x) = 0,$ so the polynomial $p(x) - q(x)$ has $n$ roots.

However, we know that a polynomial of degree $d$ has at most $d$ roots or it is the zero polynomial — so since the polynomial has degree $n-1$ and $n$ roots, $p(x) - q(x)$ is zero, and $p(x) = q(x).$

However, for higher degrees, it might be difficult to reconstruct a polynomial with points. Thankfully, Lagrange Interpolating Polynomials exist!

Now, we can use our points, or individual secrets, to construct a polynomial, or our vault key.

Lagrange interpolating polynomials are the polynomials that pass through the points $(x_1, y_1), (x_2, y_2) \cdots (x_n, y_n).$

They are defined as

$$P(x) = {(x_1 - x_2)(x_1 - x3)\cdots (x_1 - x_n)} y_1 + \cdots )}{(x_n - x_2)(x_n - x3)\cdots (x_n - x_{n-1})} y_n$$

This ensures that each value is a root, and that it passes through all possible points.

For more explanation on these polynomials, check out this slide deck: https://coast.nd.edu/jjwteach/www/www/30125/pdfnotes/lecture3_6v13.pdf

Anyway, now, you and your eighty-one friends can encode your 16 degree polynomial vault secret! Rest assured, you will have both job and bank security in the future.