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.
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
Share 2 – (x, y) where x = 2
y = 1954 + 43*2 + 12*2^2 = 2088
Share 3 – (x, y) where x = 3
y = 1954 + 43*3 + 12*3^2 = 2191
Share 4 – (x, y) where x = 4
y = 1954 + 43*4 + 12*4^2 = 2318
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:
Then we draw the corresponding parabola:
Then we find the point at x=0, whose y value is the secret:
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.