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

Before continuing, one should have a solid understanding of Lagrange Interpolation which allows for the reconstruction of the shared secret.

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.

As mentioned above, an algorithm to perform such reconstruction is called Lagrange Interpolation.

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 of our 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.

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.