Shamir’s Secret Sharing — A numeric example walkthrough
Shamir’s Secret Sharing algorithm is an old cryptography algorithm (1979) invented by the Israeli cryptographer Adi Shamir (co-inventor of RSA) for sharing a secret across multiple parties [1]. I repeatedly stumbled upon it in many research papers (mainly for MPC) so I thought that it could be useful to write an explanatory post about it as it is also a very straightforward algorithm to understand.
Shamir’s Secret Sharing Scheme
More particularly Shamir Secret Sharing Scheme (SSSS) enables to split a secret S in n parts such that with any k-out-of-n pieces you can reconstruct the original secret S, but with any k-1 pieces no information is exposed about S. That is conventionally called a (n, k) threshold scheme.
At first this may seem counterproductive in the context of secure data transmission because if there is a secure way of distributing a secret S amongst participants what is the point of using this scheme. The original purpose of the scheme is to enhance practicality and convenience when multiple parties are required to perform an authorised action. For instance consider the following problem statement from [2]:
Eleven scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry?
The answer to the above is that 462 locks are needed and also 252 keys per scientist. Obviously this is not practical. Furthermore, consider a more realistic scenario: A company that develops software signs its software deliverable with its RSA secret key in order to verify its authenticity. A possible approach would be to give a copy of the key to all of the senior developers and any of them can use that to sign each release. However, that’s easy to abuse. On the other hand, multiple keys can be issued and distributed to developers and each release would require all of them to sign it. This provides powerful safety about the authenticity of the software but it is very inconvenient.
Putting all this into the context of SSSS a secret key S can be split into N parts (and distributed to N senior developers/scientists) such that any k out of N are required to reconstruct the secret key. Immediately, the inconvenience is eliminated and even more, there is room for drop outs (i.e. senior developer leaves company). Such a fascinating scheme. Nothing less expected from the co-inventor of RSA.
How does it work?
The primary idea behind the scheme is that any k points can define a polynomial of k-1 degree. To give you some examples: given two points you can define a line equation, given 3 points you can define a parabola equation and so on and so forth.
Preparation
Given the above, let’s go ahead and try to work how the scheme works with numeric values. Let us say that our secret message is the text “SeCrEt” converting this to hex we have 0x536543724574 and continuously to decimal this is equivalent to 91694388364660. Thus S = 91694388364660, also let the N = 5 and k =3. That is, we will split the text “SeCrEt” into 5 pieces and with any 3 of them we can reconstruct the text.
First, we sample k-1 random numbers {a₁, a₂…, a₍ₖ₋₁₎} from a finite field of size p where:
such that aᵢ < p and a₀ = S. Then those are used to generate the polynomial:
Back to our example we choose p = 91994388364979. Then we generate random numbers:
And as a result the following polynomial is generated:
The next step is to construct the N pieces that are distributed to the participants. Each piece is simply a point on the polynomial just defined. Each point D can be calculated in an iterative manner:
In our case we need 5 points so we calculate them as follows:
These are then distributed to the participants of the scheme.
Reconstruction
In order to reconstruct the original secret from any k-out-of-n parts, we need to recreate the polynomial that we defined in the beginning. This can be achieved with the Lagrange Polynomial Interpolation. This is simply a formula named after the Italian mathematician Joseph Louis Lagrange for interpolating a polynomial of a degree less than n that passes through n points.
Initially, the Lagrange Basis Polynomials need to be calculated. The formula for the basis polynomials is defined as follows:
Then, given n points, the interpolated polynomial is a linear combination of the above basis polynomials as shown below:
Applying this to our example we randomly select 3 out of the 5 points we derived above:
(x0, y0)=(1, 9285275391624), (x1, y1)=(2, 27078320587385), (x2, y2)=(4, 87287720390361)
Then the basis polynomials become:
And the interpolated polynomial is derived from:
Therefore:
Note that since we are working over the Finite Field Z₉₁₉₉₄₃₈₈₃₆₄₉₇₉ the negative -300000000319 can be changed to +91694388364660. And guess what… if this number looks familiar you are right! This is our secret.
We have just walked through the whole operation of the scheme manually and retrieved our secret back.
Conclusion
I really hope that walking through the whole algorithm step by step helped you get a better understanding about the way it works. Hope you enjoyed it guys.
