Shamir Secret Sharing in a Nutshell

How to split a secret among multiple persons, so that only any subset of n people can recover it ?

04/12/2024 · 15 min read · sapling 🪴

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.

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 to the blinding polynomial. This way, we have:

When interpolating , the blinding polynomials cancel out and we directly get :

Note that we could try to add multiple roots: , but then all the new shareholders would have access to the new shares.

You could also apply the same verifying scheme as before to this method.

We have a problem

When recovering the secret, we need to trust a single recoverer to do so and all send him all of our shares. But what if we all wanted to recover the secret at the same time?

One may naively try to implement a simple broadcast or pairwise exchange protocol, but if a single malicious actor wanted to prevent the others from also recovering the secret, he could just wait for everyone to send their share, and never send his. He will have all the shares needed, while the others can’t do anything.

If everyone distrusts each other, we will have this strange situation where no one wants to send their share first. One may prove that they own a valid share with a Zero-Knowledge Proof ZKP, but will never be able to prove that he’s actually going to send it to the others.

One “solution” to this problem (in my opinion the easiest to implement) is to set a pre-defined order in which shareholders need to reveal their shares, after which it is verified each time by the others. If the share is invalid or the bearer fails to send it within a given time, the others can post a complaint against this user and abort the process.

Commitments-based ordering

After each shareholder has shared his commitment and it has been verified by everyone else, the order of reveal is defined by the value of each commitment. Let’s recall our commitments for :

One cannot manipulate the value of as it is verifiable by the others with

The probability of a malicious actor being placed last in the queue and thus fool everyone is for recoverers if we suppose that is pseudorandom. Not that good.

Incremental recovery

Let’s instead require each bearer to first send their share to everyone placed before them in the pre-defined order.

We have a single shared state that needs to be kept up-to-date for everyone at each round. This is to keep track of who has and who hasn’t sent their share yet. The state consisting of every sent share does not need to be shared as everyone can keep track of the broadcasts to received.

This way, a single malicious shareholder cannot dupe the rest of the group. But what if two malicious actors and tried hijacking the recovery ?

1. initiates
2. sends to , and gets accepted:
3. joins normally as well, he gets access to
4. joins, and so on for other
5. only sends his share to , which sends him back (or not)

In this case, (and ) are the only ones able to recover the secret. This isn’t of any good either…

TODO: find out if this is actually feasible?

References / Suggested readings

• Issuing New Shamir Secret Shares Using Multi-Party Computation
  conduition.io

• Novel Secret Sharing and Commitment Schemes for Cryptographic Applications
  Mehrdad Nojoumian
  dspacemainprd01.lib.uwaterloo.ca [PDF]

• A Share-Correctable Protocol for the Shamir Threshold Scheme and Its Application to Participant Enrollment
  Raylin Tso, Ying Miao, Takeshi Okamoto and Eiji Okamoto
  citeseerx.ist.psu.edu [PDF]

• Feldman’s Verifiable Secret Sharing for a Dishonest Majority
  Yi-Hsiu Chen and Yehuda Lindell
  eprint.iacr.org [PDF]

• Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography
  Masayuki Abe and Serge Fehr
  eprint.iacr.org [PDF]