Warning: This post has KaTeX enabled, so if you want to view the rendered math formulas, you’ll have to unfortunately enable JavaScript.

In this post, we’ll talk about
**Shamir’s Secret Sharing
(SSS)**, a cryptographic algorithm that allows us to **split a secret into multiple parts,
called shares, in such a way that the secret can only be reconstructed
if a certain number of shares are combined**.

The idea is to give a visual intuition of how the algorithm works, and describe the mathematical details behind it.

The code for all the plots in this post can be found in
`storopoli/shamir-secret-sharing`

.

## Polynomial Interpolation

**If you have two points you can draw a unique line that passes through them**.
Suppose that you have the points $(3,3)$ and $(4,4)$.
Hence, there is only one line that passes through these two points.
See the plot below.

**If you have three points you can draw a unique parabola that passes through them**.
Suppose that you have the points $(-4,16)$, $(1,1)$, and $(4,16)$.
Hence, there is only one parabola that passes through these three points.

**If you have four points you can draw a unique cubic polynomial that passes through them**.
Suppose that you have the points $(-2,8)$, $(-1,1)$, $(1,1)$, and $(2,8)$.
Hence, there is only one cubic polynomial that passes through these four points.

As you might have guessed, **if you have $n$ points you can draw a unique polynomial of degree $n-1$ that passes through them**.
This is called

**polynomial interpolation**

^{1}.

More formally, say that we have a polynomial $f(x)$ of degree $n$:

$$ f(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1x + a_0 $$

and we have $n$ points $(x_1, y_1)$, $(x_2, y_2)$, $\ldots$, $(x_n, y_n)$. Then, there is a unique polynomial $f(x)$ of degree $n-1$ such that $f(x_i) = y_i$ for $i = 1, 2, \ldots, n$.

## Shamir’s Secret Sharing

Ok now let’s connect this idea to Shamir’s Secret Sharing.
Suppose you encode a **secret $k$ as a number**.
Let’s say a private key for a Bitcoin wallet.
As you’ve already know, a private key is just a very big number.

You want to split this secret into **$N$ parts**, called **shares**.
You also want to specify a **threshold $T$** such that the **secret $k$ can only be reconstructed if at least $T$ shares are combined**.
Here’s how you can use polynomial interpolation to achieve this.

The idea is to use polynomial interpolation to generate a polynomial $f(x)$ of degree $T-1$ such that $f(0) = k$.
In other words, the polynomial $f(x)$ when evaluated at $x = 0$ should give you the secret $k$.
Then, you can **generate $N$ shares by evaluating $f(x)$ at $N$ different points**.

Here’s an example with $T = 4$ and $N = 5$. Our secret is $k = 5$ and since $T = 4$, we generate a polynomial of degree $T-1 = 3$. We’ve chosen the polynomial $f(x) = 2x^3 - 3x^2 + 2x + 5 $. Then, we evaluate $f(x)$ at $N = 5$ different points to generate the shares.

Now this polynomial is **guaranteed to pass through the point $(0, k)$**.
Hence if you evaluate **$f(0)$ you get the secret $k$**.
To know the secret, you **need to know the polynomial $f(x)$**.
And to know the polynomial $f(x)$, you **need to know at least $T$ shares**.
Otherwise, you **can’t reconstruct the polynomial and hence the secret**.

In this setup we generate addresses from the extended public key (xpub) of a Bitcoin wallet that has the private key $k$. Then, we split the private key into shares and distribute them to different people. Only if at least $T$ people come together, they can reconstruct the private key and spend the funds.

## Rotating Shares

Note that there’s nothing special about the points

- $(-2, f(-2))$
- $(-1, f(-1))$
- $(\frac{1}{2}, f(\frac{1}{2}))$
- $(1, f(1))$
- $(2, f(2))$

that we’ve used in the previous example.
You could have chosen **any other $N$ points and the polynomial would still be the same**.

Suppose now that your share buddy has lost his share.
Then, the participants can get together and **generate a new polynomial evaluation at any point $n \notin \{ -2, -1, \frac{1}{2}, 1, 2 \}$**.

This is exactly what the image below shows:

Here we’ve replaced the point $(-2, f(-2))$ with the point $(3, f(3))$.
We also assume that the point $(-2, f(-2))$ is lost.
The **polynomial is still the same**, and the secret can still be reconstructed if at least $T$ shares are combined.

We can also **rotate all the shares**.
This is shown in the image below:

Here **all previous points have been replaced by new points**.

## The Polynomial King

I am the

~~Lizard~~Polynomial King, I can do anything!Jim Morrison

In the end **if you somehow know the polynomial $f(x)$, you can do anything**.
You can rug-pull all you share buddies and take all the funds.

There are several ways that a malicious actor could learn the polynomial.
For example, if the shares are generated in a predictable way, an attacker could guess the polynomial.
Or, during the reconstruction phase, an attacker could learn the polynomial by observing the shares.
Additionally, during a distributed share generation, an attacker could disrupt the process and force the participants to reveal their shares^{2}.

## Conclusion

In this post, **we’ve seen how polynomial interpolation can be used to split a secret into multiple shares**.
We’ve also seen how the **secret can be reconstructed if a certain number of shares are combined**.
This is the basic idea behind **Shamir’s Secret Sharing (SSS)**.

Note that the devil is in the details.
A lot of the complexities of SSS come from the **details of how the shares are generated and how the secret is reconstructed**.
There are **several types of attacks that can be done by a malicious actor**.
Especially during the share generation and reconstruction phases.

The intent of this blog post is to show how **elegant, simple and powerful the idea behind SSS is**.

## License

This post is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

and steams from the Lagrange interpolation. ↩︎

or force them to reuse nonces. Then, “poof”, private keys are gone. ↩︎