Shamir Secret Sharing in a Nutshell

The main idea behind Shamir Secret Sharing (SSS) is to split a secret into parts, such that any parts can be used to reconstruct the secret, but any parts are not enough to do so, and do not give any information about the secret.

Splitting the Secret#

Let's take the following example: we want to split the secret into parts, such that any parts can be used to reconstruct the secret. It is supposed we are working in a finite field for the entirety of this post.

What the hell is

?

A finite field where ( is a prime power), is a finite set of elements, on which we can apply our usual additions and multiplications.

The most common finite field is the set of integers modulo , , where all computations are taken , which means that we have:

In the case of an elliptic curve, is our curve's order.

The first step is to sample a random polynomial of degree such that . This gives us the property .

Our splits, also called shares, are in fact just points of our polynomial. We can generate them by evaluating for . Do not evaluate for as this would obviously just give away the secret.

Thus, our shares are , , , and .

Let's now plot the polynomial :

Reconstructing the Secret#

We know that points will suffice to construct the polynonial of degree .

In our case, , so we need points to restore , just as described in the beginning.

Based on the shares we generated earlier, let's take , and (our recovery group ) to reconstruct the polynomial using Lagrange interpolation:

It's even cooler when represented graphically:

Commitments, Proofs and Verifications#

In a perfect world where everyone is honest and where there are no transmission errors caused by cosmic rays, we could just send the shares to the participants and call it a day. But guess what? Sh*t happens.

We need a way to check that the share we receive as a shareholder after the secret has been split is actually a valid one. You could gather with other bearers and collectively verify if the recovered secret is correct, but that is just too much hassle for such a simple task.

Instead, let's take advantage of the properties of elliptic curves to create a commitment scheme. After we have generated our polynomial , we can take each coefficient and multiply it by the generator point of the curve. This gives us a few values that we can send to the shareholders.

When a shareholder wants to verify their share , they can check with the following equation:

You could see this procedure as computing the "public keys" of the coefficients. This method is also called "Feldman's Verifiable Secret Sharing".

One may argue that disclosing could give information about the polynomial, but if we suppose that is an EC secret key, the public key is supposed public and may be shared. Finding with comes down to solving the discrete logarithm problem, which is supposed really hard here.

Verifying that is a private key#

We know some public key and we want to verify that the secret being shared is actually the private key . This can be done by first checking if the commitments are valid, and then verifying that .

Pedersen's Verifiable Secret Sharing (PVSS)#

Another way the dealer could commit to the polynomial he generated without directly sharing , is to add a so-called "blinding polynomial", a pretty common concept in cryptography.

Let's now instead take where comes from a randomly generated polynomial , our blinding polynomial. is just another generator point on the curve. The dealer will now needs to distribute slightly different shares .

Shareholders may now verify their shares with:

This second method is known as "Pedersen's Verifiable Secret Sharing".

Bob just got hit by a bus, what now?#

Our good old friend disappeared along with his share, and now other bearers are scared of losing too many shares until they can't recover the secret. They could reiterate the dealing procedure by all sending their shares to a single person which then redistributes the new ones. However this is not feasible in the case where everyone distrusts each other. We need a multi-computational way of re-issuing a new share without someone ever recovering the secret.

We will need shareholders, denoted to re-issue a new share .

Each shareholder begins by computing their Lagrange multiplier:

After multiplying with their share , they randomly split it into so-called Lagrange-parts in order to distribute them to other bearers :

The exchange matrix can be represented as:

Where the ^th row corresponds to the Lagrange-parts that the shareholder will send and the ^th column to the Lagrange-parts the shareholder will receive.

Each shareholder computes the partial-share:

Where is the ^th Lagrange-part of . They respectively send to the new bearer , which finally computes his share:

This can be rewritten as:

Inception#

Another angle to tackle this problem from is to re-use Secret Sharing inside our Secret Sharing scheme (Inception, anyone?).

Let's say we have our recovery group , our new shareholders and for convenience.

1. Each shareholder generates a random polynomial of degree .
2. They each compute the auxiliary shares for .
3. Every shareholder receives the auxiliary shares from the recovery group.
4. Each shareholder computes the aggregated share and shares it to everyone in .
5. Each future bearer can interpolate the polynomial from the shares and compute their share

Let's take a look at the math:

But wait! We just learnt how to implement a secure, verifiable secret sharing scheme and we aren't even using it!

Verifiable Inception#

Let's review the protocol, this time including relevant checks to ensure the data we're receiving is genuine. We assume the original dealer was a good guy and already used Feldman's VSS, providing the commitments for the OG polynomial to everyone.

1. Each shareholder generates a random polynomial of degree .
2. They also compute and share for to see their commitments:
3. They each compute the auxiliary shares for , and shares them once they have received all other
4. Every shareholder receives the auxiliary shares from and checks whether they match
5. Before computing anything else, each shareholder commits to the upcoming polynomial and sends it to :
6. Each shareholder computes the aggregated share .
7. Each inductee first waits to receive all , checks that they are the same from everyone, and then receives .
8. Each future shareholder checks whether each given is genuine:
9. Each future bearer can interpolate the polynomial from the shares and compute their share

Single share issuing#

In the case where we only want to issue a single share, conduition proposed a clever way to remove the subtracting step at the end by adding a root at