(Very) Basic Shamir’s Secret Sharing

#bitcoin #cryptography #passwords #programming

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

Example Problem

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. That single key can be used 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 a cryptographer. Instead of naively sharing the original key, they use SSS (Shamir’s secret sharing). Four shares are created, and a threshold of three is set, with the Bitcoin key as the original secret. Now, their plan has the following properties:

The Bitcoin key is not stored in one place, 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. With five shares and a threshold of three, only three of the five shares need to be used 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).

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

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. This leaves us with:

y = 1954 + 43x + 12x^2

We use this formula to create 4 points (shares) that will be given 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 our threshold was set 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: