Shamir's Secret Sharing Unraveled

Overview

Have you ever heard the phrases Key Sharding or Secret Sharing in the context of any of the popular crytocurrencies Bitcoin or Ether ???

Interested in understanding what it means and how it works ??? If, yes, read on ...

Alice is wealthy individual, owning lots of Bitcoins in her digital wallet, which holds her account consisting of a private key and a public key. Alice uses her private key only when spending her Bitcoins. She wants to backup her private key so that in an event of any disaster, she is able to restore her private key from the backup. Without the private key Alice will not be able to spend the Bitcoins she owns.

Imagine Alice is able to securely split her private key into unique parts using an algorithm and backup those parts in different secure locations. In order to restore the original private key, the various unique parts need to come together in a specific order using an algorithm. How cool that would be ???

This is exactly what Key Sharding or Secret Sharing is, and the algorithm behind that is called Shamir's Secret Sharing.

The basic idea behind Shamir's Secret Sharing is to split a secret into n unique parts such that, knowing any combination of k parts (also known as the Threshold), where k <= n, is enough to recreate the original secret. This approach is often referred to as k -of-n threshold scheme in the cryptographic circles.

Under-the-hood Shamir's Secret Sharing leverages a polynomial equation f(x) of degree k-1, such that the secret that is split into k parts, all lie along the path of the polynomial, with f(0) representing the secret.

Sounds complicated ??? We will see that it is not as we develop an intuition by looking at simple use-cases.

In order to keep things simple, let us assume Alice's private key is a 4-digit pin 1420.

2-of-2 Scheme

Alice desires to backup her secret pin by splitting the pin into two parts (k = 2) and sharing each part with one of her two friends Bob and Charlie. Note that Alice could have shared a third part with another friend Dave. This would be the 2-of-3 schema, with k = 2 as the threshold. In other words, Alice would need any two of the three parts to reconstruct her secret pin.

Using Shamir's Secret Sharing schema, this implies a polynomial equation of degree (k - 1) = 1.

A polynomial of degree 1 is a line with an equation of the form:

where a₀ and a₁ are the coefficients of the first-degree polynomial (equation of a line).

Since f(0) is the secret 1420, we can deduce the value for the coefficient a₀ = 1420 and write the equation as follows:

Next, Alice will pick a random value for the coefficient a₁ = 80 to arrive at the final equation as follows:

Substituting x = 1, we get f(1) = 1500, for x = 2, we get f(2) = 1580, for x = 3, we get f(3) = 1660 and so on. The points (1, 1500), (2, 1580), (3, 1660), etc., all lie along the path of the Equation.3 from above.

Alice can now share the value 1660 with Bob and the value 1580 with Charlie for safe-keeping. Alice will retain the information of the x values corresponding to the parts shared with Bob and Charlie.

To restore the original secret pin, Alice will get the value 1660 from Bob and the value 1580 from Charlie and plug the values into the Equation.1 along with the corresponding x values [(x=3, f(3)=1660), (x=2, f(2)=1580)] to arrive at the following system of equations:

Solving the equations (1) and (2) from above, we can deduce the value for the coefficient a₀ = 1420 and the value for coefficient a₁ = 80.

Plugging the value of these coefficients into the Equation.1, Alice will be able to arrive at the equation that is the same as Equation.3 from above. The value for f(0) represents the original secret pin.

Makes sense ??? No ??? If not, let us look at one more example to drive the point home.

3-of-3 Scheme

This time Alice wants to backup her secret pin by splitting the pin into three parts (k = 3) and sharing each part with one of her three friends Bob, Charlie and Dave. Note that Alice could have shared a fourth and a fifth part with two friends Eva and Frank. This would be the 3-of-5 schema, with k = 3 as the threshold. In other words, Alice would need any three of the five parts to reconstruct her secret pin.

Per Shamir's Secret Sharing schema, this implies a polynomial equation of degree (k - 1) = 2.

A polynomial of degree 2 is a quadratic equation of the form:

where a₀, a₁, and a ₂ are the coefficients of the second-degree polynomial (a quadratic equation).

Since f(0) is the secret 1420, we can deduce the value for the coefficient a₀ = 1420 and write the equation as follows:

Let us say, Alice picks random values for the coefficients a₁ = 40 and a₂ = 20 to arrive at the final equation as follows:

Substituting x = 1, we get f(1) = 1480, for x = 2, we get f(2) = 1580, for x = 3, we get f(3) = 1720 and so on. The points (1, 1480), (2, 1580), (3, 1720), etc., all lie along the path of the Equation.7 from above.

Alice can now share the value 1580 with Bob, the value 1480 with Charlie, and the value 1720 with Dave for safe-keeping. Alice will retain the information of the x values corresponding to the parts shared with Bob, Charlie, and Dave.

To restore the original secret pin, Alice will get the value 1580 from Bob, the value 1480 from Charlie, and the value 1720 from Dave and plug the values into the Equation.5 along with the corresponding x values [(x=3, f(3)=1720), (x=2, f(2)=1580), (x=1, f(1)=1480)] to arrive at the following system of equations:

Solving the equations (1), (2), and (3) from above, we can deduce the value for the coefficient a₀ = 1420, the value for the coefficient a₁ = 40 and the value for coefficient a₂ = 20.

Plugging the value of these coefficients into the Equation.5, Alice will be able to arrive at the equation that is the same as Equation.7 from above. The value for f(0) represents the original secret pin.

k-of-n Scheme

In general, if Alice wants to backup her secret by splitting the it into k parts, then this implies a polynomial equation of degree (k-1) of the form:

Since f(0) will be the secret, we can deduce the value for the coefficient a₀ to be the secret. Then, Alice will pick random values for all the remaining coefficients a₁ through a_(k-1).

Substituting different values for x, Alice can pick a set of k parts [(a, f(a)), (b, f(b)), ... (k, f(k))] and store those parts in k different secure locations.

Then comes the fun part when reconstructing the original secret. To restore the original secret, one can substitute each of the points [(a, f(a)), (b, f(b)), ... (k, f(k))] into the Equation.9 and solve the k different system of equations to determine the values of the coefficients a₀ through a_(k-1). This is the approach we took for the two cases we explored (2-of-2 and 3-of-3 schemes). There is another approach called Lagrange Polynomial Interpolation for reconstructing the original polynomial.

Given k points, the general form of Lagrange Polynomial Interpolation is as follows:

where L_i(x) is as follows:

Let us apply Lagrange Polynomial Interpolation to our example from the 2-of-2 scheme.

From our 2-of-2 scheme example, the 2 points are as follows:

Given the 2 points, the equation for Lagrange Polynomial Interpolation is as follows:

Substituting the values for f(x₀) and f(x₁) into the Equation.13 from above, we get:

The value for L₀(x) can be computed as follows:

Similaryly, the value for L₁(x) can be computed as follows:

Substituting the values for L₀(x) and L₁(x) into the Equation.14 from above, we get:

Expanding and simplifying the Equation.17 from above, we get:

BINGO !!! This is the same as the Equation.3 that Alice started with.

Practical Application

We started with the premise that Alice wants to securely split her Bitcoin private key into unique parts and backup those parts in different secure locations for safe-keeping.

We then went on to unravel the approach to Key Sharding using one of the popular algorithm's called Shamir's Secret Sharing.

In this section, we will demonstrate Key Sharding using one of the Python modules called secretsharing.

To install the Python module secretsharing, open a terminal window and execute the following command:

$ pip install secretsharing

The following would be a typical output:

Output.1

Collecting secretsharing
  Downloading https://files.pythonhosted.org/packages/d3/53/97909e19fe623c6dfdb7f881c1ec119627c34419d973d094e002738fd984/secretsharing-0.2.6.tar.gz
Building wheels for collected packages: secretsharing
  Running setup.py bdist_wheel for secretsharing ... done
  Stored in directory: /root/.cache/pip/wheels/09/c6/4a/c97772071806a92c6e60a6aa5811dfb25c909ca29f37b03127
Successfully built secretsharing
Installing collected packages: secretsharing
Successfully installed secretsharing-0.2.6

Next, start Python's REPL by executing the following command:

$ python

The following would be a typical output:

Output.2

Python 2.7.15rc1 (default, Apr 15 2018, 21:51:34) 
[GCC 7.3.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>

For this demonstration, let us assume Alice's Bitcoin private key is cU1BVGodVHwP7BrSQhdHMLzugxr1a1Wq3CS5PzJ1V3L68krfd5D8.

WARNING

Never ever share your Bitcoin private key.

We will use the 3-of-5 threshold scheme for this demonstration.

To split the Bitcoin private key, execute the following Python code:

>>> from secretsharing import BitcoinToB58SecretSharer

>>> parts = BitcoinToB58SecretSharer.split_secret("cU1BVGodVHwP7BrSQhdHMLzugxr1a1Wq3CS5PzJ1V3L68krfd5D8", 3, 5)

>>> parts

The following would be a typical output:

Output.3

['2-29MZK9DCsXSjtUYU8aB3Puo3HLecrF9HDvWo7gdFf2CS5T5XnRGVJ5s', '3-CzbwpHTgc1aMPBMCcaLpEgPkqfdsKowcvLNwG2oaDYBxVDqti77KRMp', '4-87EeRSktAyAaywsfvpnNRDxWCNjnJKoK8yse3Nor9dpC1MMM8Unzyko', '5-CvmngcGqsh5BUt3WnMf4kFcHB561s1KdqdYj3pSayXEzu8dmSyieSYz', '6-21hF3nqXQtSQ5sw6U8oYR4E5x9YuvduK4WrNhFuHAzJWuGfHGAV9LUD']

Alice can now share the three parts as follows:

• Bob: '2-29MZK9DCsXSjtUYU8aB3Puo3HLecrF9HDvWo7gdFf2CS5T5XnRGVJ5s'

• Charlie: '4-87EeRSktAyAaywsfvpnNRDxWCNjnJKoK8yse3Nor9dpC1MMM8Unzyko'

• Dave: '6-21hF3nqXQtSQ5sw6U8oYR4E5x9YuvduK4WrNhFuHAzJWuGfHGAV9LUD'

To reconstruct the Bitcoin private key from the parts shared with Bob, Charlie, and Dave, execute the following Python code:

>>> BitcoinToB58SecretSharer.recover_secret(['2-29MZK9DCsXSjtUYU8aB3Puo3HLecrF9HDvWo7gdFf2CS5T5XnRGVJ5s', '4-87EeRSktAyAaywsfvpnNRDxWCNjnJKoK8yse3Nor9dpC1MMM8Unzyko', '6-21hF3nqXQtSQ5sw6U8oYR4E5x9YuvduK4WrNhFuHAzJWuGfHGAV9LUD'])

The following would be a typical output:

Output.4

'cU1BVGodVHwP7BrSQhdHMLzugxr1a1Wq3CS5PzJ1V3L68krfd5D8'

Hooray !!! We have successfully demonstrated the concept of Key Sharding using Shamir's Secret Sharing algorithm.

© PolarSPARC