Shamir's Secret Sharing

Open Table of contents

What it is
How it works
Why it works
References

What it is

Shamir’s Secret Sharing allows one to split access to a secret value among multiple parties.

The secret can be split up in a way that a threshold number of secret share holders have to collaborate to reconstruct it.

How it works

The core mathematical building block this scheme relies on is polynomials. Each polynomial has coefficients $a$ as well as a certain degree $k$ which is the polynomial’s largest exponent.

A polynomial $P(x)$ can therefore be written as:

P(x) = a_k x^k + a_{k-1} x^{k-1} + ... + a_0

One important property of polynomials is that any $k$ -degree polynomial can be uniquely reconstructed via $k+1$ polynomial evaluations (” $y$ -values”). While more than $k+1$ evaluations also allow for a reconstruction, less than $k+1$ evaluations won’t.

An algorithm to perform such reconstruction is called Lagrange Interpolation which we won’t dive deeper into in this writeup.

As an example, we can look at the polynomial of degree $1$ that’s defined as:

P(x) = a_1 x^1 + a_0

This polynomial describes a line that intersects the $y$ -coordinate at $a_0$ .

As we can see in the following visualization, we can reconstruct the line uniquely via $k+1 = 1+1 = 2$ points:

Degree 1 Polynomial Visualization

With this knowledge we can use a polynomial to hide and share a secret among $n$ parties so that $k+1$ of our $n$ share holders can reconstruct it.

The first step is to define the secret value $s$ we want to hide and share. Next up, we need to decide how many participants will be required to reconstruct the secret (the “threshold”) and how many secret share holders there will be.

The secret $s$ will be defined as the $a_0$ value of the polynomial $P(x)$ (the value where the graph intersects the $y$ -coordinate).

The threshold number of participants to reconstruct the secret will be $k+1$ . The overall number of participants that will hold secret shares will be $n$ ( $n$ has to be $\geq k+1$ ).

We start by setting the polynomial’s $a_0$ value to $s$ . After that we generate random coefficients for a $k$ -degree polynomial.

Next up, we evaluate the polynomial at $n$ points (note that $n \geq k+1$ ):

\begin{aligned} share_1 &= P(1) \\ share_2 &= P(2) \\ &... \\ share_n &= P(n) \end{aligned}

We can then hand out these $n$ evaluations to our participants.

Given that we have a degree $k$ polynomial, any $k+1$ shares (polynomial evaluations) are enough to recover the polynomial (e.g. via Lagrange Interpolation).

Once it’s recovered, we can get access to the secret $s=a_0$ by evaluation the recovered polynomial at $x=0$ . Remember that the secret $s=a_0$ is the $y$ -intercept, i.e. the $y$ -value where $x=0$ .

Why it works

Shamir’s Secret Sharing leverages the ability to uniquely reconstruct polynomials via techniques such as Lagrange Interpolation.

Such techniques allow for the reconstruction of a polynomial of degree $k$ if at least $k+1$ evaluations of such polynomial are known. It’s important to emphasize that less than $k+1$ evaluations won’t allow for a proper reconstruction, whereas more than $k+1$ always do.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.