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 pointsOnly one possible parabola crosses through the same three pointsOnly one cubic curve passes through the same four pointsAn infinite number of lines can be drawn through the same pointAn 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
<code style="box-sizing: border-box; font-family: Consolas, "Andale Mono WT", "Andale Mono", "Lucida Console", "Lucida Sans Typewriter", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Liberation Mono", "Nimbus Mono L", Monaco, "Courier New", Courier, monospace; color: rgb(255, 255, 255); background-color: transparent; border: 0px; padding: 0px; font-size: 0.85em; border-radius: 3px;">y = a0 + a1*x + a2*x^2</code>Where a0 is the secret, and a1 and a2 are our randomly chosen integers. This leaves us with:
<code style="box-sizing: border-box; font-family: Consolas, "Andale Mono WT", "Andale Mono", "Lucida Console", "Lucida Sans Typewriter", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Liberation Mono", "Nimbus Mono L", Monaco, "Courier New", Courier, monospace; color: rgb(255, 255, 255); background-color: transparent; border: 0px; padding: 0px; font-size: 0.85em; border-radius: 3px;">y = 1954 + 43x + 12x^2</code>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:
Then we draw the corresponding parabola:
Then we find the point at x=0, whose y value is the secret:
Secret = 1954!
Note: Some details and restrictions were left out in the name of simplicity, so if you want to learn more there is much more to learn on the subject.
Thanks for reading! If you have questions or comments just hit me up on twitter!
Originally published on Qvault
- Lane on Twitter: @wagslane
- Download Qvault: https://qvault.io
- Star our Github: https://github.com/q-vault/qvault