shamirsecretlibrary

(Very) Basic Shamir’s Secret Sharing

By @wagslane (twitter)

We use an algorithm called Adi Shamir’s secret sharing in order to share ownership of a secret among a group of participants. Then, in order to calculate the original secret, a minimum number of shares must be used.

Example Problem

To illustrate, let us imagine that a family of four shares a Bitcoin wallet. This Bitcoin wallet contains a single private key that all members of the family co-own. Because they share it, any of them can use that single key to spend all of the Bitcoins.

The family has a problem: if they each keep a copy, then only one of them needs to be hacked 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). So they create four shares and set a threshold of three, with the Bitcoin key as the original secret. Now, their plan has the following properties:

  • They have not stored the bitcoin key in one place, thus making it harder to steal
  • Members of the family need to cooperate to spend the Bitcoin
  • If a family member dies or loses their share, the other three members can still reconstruct the key

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 Maths – 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:

  • Only one line can be drawn between two points
  • Only one possible parabola crosses through the same three points
  • Only one cubic curve passes through the same four points
  • An infinite number of lines can be drawn through the same point
  • An infinite number of parabolas can be drawn through the same two points

The Maths – 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 thus 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)

Reconstruction

Each participant in our scheme now owns one (x,y) point (share), and we set our threshold to 3. Remember that 3 points can describe 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 shares 1, 2, and 4. First, we plot them:

plotted graph points

Then we draw the corresponding parabola:

corresponding parabola

Then we find the point at x=0, whose y value is the secret:

secret y value

Secret = 1954!

Note: I left out some details and restrictions in the name of simplicity, so if you want to learn more there is much more to learn on the subject.

More about Bitcoin and Security from Qvault:
Trustworthy vs Trustless Apps
(Very) Basic Intro To Elliptic Curve Cryptography
Top 10 Online Crypto Communities 2020

Thanks For Reading!

Follow us on Twitter @q_vault if you have any questions or comments

Take game-like coding courses on Qvault Classroom

Subscribe to our Newsletter for more educational articles

%d bloggers like this: