# Shamir's Secret Sharing

## 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:

With this knowledge we can use a polynomial to hide and share a secret among $n$ parties so that $k+1$ our of $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.