(Very) Basic Shamir’s Secret Sharing
source link: https://qvault.io/2019/12/26/very-basic-shamirs-secret-sharing/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By @wagslane (twitter)
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:
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!
Lane on Twitter: @wagslane
Lane on Dev.to: wagslane
Lane on Medium: @wagslane
Download Qvault:https://qvault.io
Star our Github: https://github.com/q-vault/qvault
Recommend
-
66
Consider a scenario in which you are tasked with managing the security of a bank’s vault. The vault is considered impenetrable without a key, which you are given on your first day on the job. Your goal is to securely mana...
-
20
With S imple S hamir's S ecret S haring (s4) I want to provide you an easy to use interface for this beautiful little peace of math. s4 is open source and provided as it is. You can fi...
-
11
To sleep the disks or not: M1 Mini (very basic question) ...
-
13
Sharing. The simple secret to saving the planet?Sharing could be the secret ingredient to smarter communities, a stronger economy and a more resilient planet.If humans continue to behave the s...
-
1
Sharing: The simple secret to saving the planet?Sharing could be the secret ingredient to smarter communities, a stronger economy, and a more resilient planet.
-
4
Disclosing Shamir’s Secret Sharing vulnerabilities and announcing ZKDocs By Filipe Casal and Jim Miller Trail of Bits is publicly disclosing two bugs that affect Shamir’s Secret Sharing i...
-
5
Parliament: A Threshold Secret Sharing ServiceMaking it easy to protect high-value secrets.Written by Tobias Lauinger. High-value secrets need proper protection. A w...
-
8
Comment Electric cars have a very dirty secret The technological flaws of battery-powered vehicles have not gone away
-
3
Shamir's Secret Sharing Scheme Shamir's Secret Sharing Scheme What is "Secret Sharing"? Citing from the Wikipedia article about
-
10
January 23, 2023 A Very Basic Scraper/Aggregator Site in Next.js with Go Cloud Functions and Supabase Wouldn’t it be neat to have aggregated data (for a website, daily email, push...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK