Learn computer science by building real projects with modern technologies

Shamir’s Secret Sharing Step-By-Step

By Lane Wagner on Aug 18, 2020

Adi Shamir’s Secret Sharing is a cryptographic algorithm that allows distinct parties to jointly share ownership of a single secret by holding shares. The original secret can only be reconstructed by using a minimum number of shares, which allows different parties to cooperate without the need to fully trust one another.

Example Problem

To illustrate, let’s imagine that a family of four all share a single Bitcoin wallet. This Bitcoin wallet contains a single private key that all members of the family co-own. Because there is a single key, any of the family members can use that key to spend all of the Bitcoins.

The family has a problem: If they each keep a copy, then only one of their copies needs to be compromised to have all the coins stolen. If only one of them keeps the key, then that person may lose it or decide to double-cross the other family members.

Luckily, one of the family members is also a cryptographer. Instead of naively sharing the original key, they use SSS (Shamir’s secret sharing). The family creates four shares and sets a threshold of three, with the Bitcoin key as the original secret. Now, their plan has the following properties:

Learn Go by writing Go code

I'm a senior engineer learning Go, and the pace of Boot.dev's Go courses have been perfect for me. The diverse community in Discord is a blast, and other members are quick to help out with detailed answers and explanations.

- Daniel Gerep from Cassia, Brasil

Understanding the Threshold

Every Shamir sharing scheme has a total number of shares and a threshold. The threshold is the number of shares required to reconstruct the original secret. For example, with five shares and a threshold of three, you only need three of the five shares to calculate the original secret.

The Math - Lines

One of the fundamental mathematical properties used in Shamir’s secret sharing is the fact that it takes k points to define a polynomial of degree k - 1. For example:

The Math - Walkthrough

Let us construct a scheme to share our secret 1954 (S) with 4 (n) shares and a threshold of 3 (k).

First, we randomly choose k - 1 positive integers, so in our case, 2 positive integers. We randomly choose 43 and 12.

Then, we build a polynomial of the form

y = a0 + a1*x + a2*x^2

Where a0 is the secret, and a1 and a2 are our randomly chosen integers. We are left with:

y = 1954 + 43x + 12x^2

Then, we use this formula to create 4 points (shares) that we give to each participant.

Share 1

(x, y) where x = 1

y = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

Share 2

(x, y) where x = 2

y = 1954 + 43*2 + 12*2^2 = 2088

(2, 2088)

Share 3

(x, y) where x = 3

y = 1954 + 43*3 + 12*3^2 = 2191

(3, 2191)

Share 4

(x, y) where x = 4

y = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

Learn to code by writing code

I was a field service engineer and I wanted to learn to code, but work and family limited my options. Since completing the computer science track on Boot.dev, I now have a job offer in hand and will be starting my career as a software developer in the coming months.

- Özgür Yildirim from Germany

Reconstruction

Each participant in our scheme now owns one (x,y) point, which is a single share. Remember that we set our threshold to 3 and that 3 points define a parabola (polynomial of degree 2) perfectly. That means that if we use three points, we can draw a parabola and calculate a0 (the secret). Let’s assume we have control of shares 1, 2, and 4.

Step 1 - Plot the points (shares) that we control

shamirs secret sharing no line

Step 2 - Draw the corresponding parabola

shamirs secret sharing

Step 3 - Find the point where x=0. It’s y value is the secret

shamirs secret sharing shares

In our case, the secret is 1954.

It’s not actually that simple. We need finite fields.

While the example we worked through above is great for demonstration purposes, it actually isn’t very secure. For each share that an attacker obtains, they actually are gaining more and more information about the secret. While two points don’t perfectly describe a parabola, they still leak critical information about the parabola.

The solution lies in finite field arithmetic. By plotting the function on a finite field of sufficient size, the graph of the polynomial becomes disjointed and scattered, which means the attacker is unable to make educated guesses about the pathing of the underlying function.

Adi Shamir

Adi Shamir is an Israeli cryptographer famous for Shamir’s Secret Sharing, but he is also a co-inventor of the widely used RSA algorithm that the vast majority of the internet is built upon. Shamir was born in Tel Aviv and earned an undergraduate degree in math from the university there. Later he obtained his master’s and Ph.D. degrees in Computer Science from the Weizmann Institute in 1975 and 1977 respectively.

Learn to code by building real projects

Related Reading