Skip to content

Shamir's Secret Sharing

Table of contents

Open Table of contents

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 aa as well as a certain degree kk which is the polynomial’s largest exponent.

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

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

One important property of polynomials is that any kk-degree polynomial can be uniquely reconstructed via k+1k+1 polynomial evaluations (”yy-values”). While more than k+1k+1 evaluations also allow for a reconstruction, less than k+1k+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 11 that’s defined as:

P(x)=a1x1+a0P(x) = a_1 x^1 + a_0

This polynomial describes a line that intersects the yy-coordinate at a0a_0.

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

Degree 1 Polynomial Visualization

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

The first step is to define the secret value ss 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 ss will be defined as the a0a_0 value of the polynomial P(x)P(x) (the value where the graph intersects the yy-coordinate).

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

We start by setting the polynomial’s a0a_0 value to ss. After that we generate random coefficients for a kk-degree polynomial.

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

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

We can then hand out these nn evaluations to our participants.

Given that we have a degree kk polynomial, any k+1k+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=a0s=a_0 by evaluation the recovered polynomial at x=0x=0. Remember that the secret s=a0s=a_0 is the yy-intercept, i.e. the yy-value where x=0x=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 kk if at least k+1k+1 evaluations of such polynomial are known. It’s important to emphasize that less than k+1k+1 evaluations won’t allow for a proper reconstruction, whereas more than k+1k+1 always do.

Additional Resources