Shamir's Secret Sharing in Go

Concept

Imagine you have a secret that you want to distribute among some friends, but no individual should know the secret, they must all come together to re-create the secret. How might we do this?

Algorithm attempt 1

Lets say the secret is the number 3214 and you have four friends. One idea is to give each friend a different digit in the number. Then one person would get (0,3), which tells them the 0th digit is 3. Another friend gets (2,1), and when the two friends come together they know the secret looks something like 3_1_. This secret sharing algorithm has some issues though. If three of the four friends come together, they are very close to knowing the secret and may be able to brute-force/guess the final digit, which we don't want. We also run into an issue if we have more friends then digits since we can't give everyone a unique digit.

Algorithm attempt 2

Perhaps the next solution is to give everyone a random number such that the sum of all these numbers are your secret. So for the secret 3214 and four friends, the parts of the secret (called shares) might look like 5, 1022, 40, and 2147. This algorithm is independent of the number of friends we have, which solves one of our problems. But there is still the issue that as more friends come together they get closer to discovering our secret since they know the lower bound.

Algorithm attempt 3

We will still use the random numbers that sum to our secret, but this time we'll do it modulo some number. This means if we use modulo 10000, then our shares could look like 3566, 20, 9831, and 9797 (since (3566+20+983+9797)%10000 = 3214). Now when three of the four friends come together they have no clue what the secret might be, they don't even have a lower bound.

This satisfies all the properties we wanted up to this point, but our secret holder decides there's a new property they want. Our secret holder wants the secret to be re-created if any two of his four friends come together (how many people must come together to create the secret is called the threshold, in this case the threshold is two). All the previous algorithms do not work within these new requirements, so lets think up some new algorithms.

Algorithm attempt 4

Perhaps if we give everyone most of the secret, but each person is missing a unique piece. Example shares could look like 3_14, _214, 32_4, and 321_. Now when any two people come together they can recreate the secret. This satisfies our new property, but has all the issues from before: the solution can be brute forced, and you're secret must be split-able among the number of friends you have.

Although this algorithm is not what we are looking for, its still interesting to consider how you might adapt it for different thresholds.

It is easiest to simplify the problem as handing out bit masks of the secret, so if we consider the share 0110, then the person would have the second and third digit of the secret. When multiple shares are brought together, you simply OR the bitmasks to check if you get all 1s, which would mean you have uncovered the entire secret. How do we generate the bit masks such that when N (the threshold) people come together they get all 1s, but when N-1 people come together they will always be a 0 left? Its not immediately obvious that this is even possible outside of the trivial cases.

The trivial cases are a threshold of everyone and a threshold of 2. For everyone, you just hand out a different digit to each person, that way all people need to come together to have all the digits. For N=2, everyone has the entire secret, except a single digit, unique to each individual. Now when anyone comes together they will be missing different digits and can exchange them with one another to complete the secret.

The next simplest case is a threshold of 3 among 4 people. This problem is fun to consider on your own, so take a moment before looking at the solution below. Verify that any two masks will always leave out some of the secret, but any three will always complete it.

000111
011001
101010
110100

This can be generalized to any threshold N and any number of people K. You generate the masks by enumerating all combinations of N-1 0s along the columns of the masks (so start with N-1 zeros and K-N+1 1s, then add a new column for each new enumeration until all combinations are exhausted). The resulting rows are the masks.

Since there are at most N-1 0s in a column, this construction ensures that there can not exist any combination of N masks which will be missing a digit. But how does this ensure that there will always be a digit missing for any N-1 combinations of masks? Consider for a moment, sometimes an example can help, below is N=3 K=6.

000001111111111
011110000111111
101110111000111
110111011011001
111011101101010
111101110110100

Because we made sure to exhaust all enumerations of N-1 0s in the columns, then for any N-1 masks we bring together, one of their columns must contain all zeros, for that is an enumeration (if we look at the remaining masks they will all haves 1s in that same column).

Here's a one-liner in python to generate the N threshold masks for K people.

print('\n'.join(map(''.join, zip(*[[str(1-(j in c)) for j in range(K)] for c in combinations(range(K), N-1)]))))

And now for the very clever solution developed by Adi Shamir.

Shamir's Secret Sharing Algorithm

To introduce the core concept, let's start with the most basic example. You want a threshold of 2 for the secret 3214. We encode that secret in a line, which can be done a number of ways, lets encode it as the y-intercept. The slope we pick at random, say 2, so we get the line y=3214+2x. Now we can hand out points on the line (the shares) to our friends. If any two of our friends come together they can recreate the line and discover our secret. For example, you hand out points on the line (1, 3216), (5, 3224), and (10, 3234).

So if (5, 3224), and (10, 3234) are brought together we can recover the secret b by plugging one of the points into y=(3234-3224)/(10-5)*x+b to solve for b.

Note that we can hand out as many shares as we want, even handing out shares at a later date (being mindful not to hand out the same point twice), so there is no dependency on the number of friends we have.

For larger thresholds we use the general fact that N points uniquely defines a N-1 degree polynomial. So for a threshold of N we take our secret and encode it in a N-1 degree polynomial.

It turns out this is not perfectly secure since when N-1 people come together they can solve for a finite range that the secret must exist in. An example is a bit complicated, but the solution is not. We again use a modulus for our polynomials, which makes the algorithm secure (and the code easier). By picking a modulus that is prime we create what is known as a field, allowing for division to be defined, which will be necessary to solve our system of equations.

Below we see intuitively how taking the modulus makes predictions difficult. We see all the integer points on the polynomial 5+x+x^2 mod 101. Given any of the 2 blue points, nothing can be said about the underlying polynomial.

Now that we are doing operations on polynomials we are able to do Secure Multi-party Computation. This means lots of people can have a secret, and everyone can get the sum of everyone's secret without ever learning anyone's secret. But its not just summing, it turns out that once you define AND, NOT and OR (or just NAND) on polynomials it becomes Turing complete and everyone can calculate arbitrary functions on inputs that are secret. This is how the Danish Sugar Beet Auction was run.

Code

The first thing we need are operations in the modulus space we are working with. This is a bit tricky since we are actually already in a modulus space due to computers having limited space for each number. Below we see the new basic math operations that handle overflow in a modulus space.

And now we need a polynomial defined using these math operations. We need to be able to generate points from polynomials (generating shares), and polynomials from points (recovering the secret). This requires some basic operations on polynomials which we will skip (it's boring and long, but a link to the repo is at the end of the article if you want to see). Note that these are not the secure multi-party computation functions, those would need to look slightly different to ensure the secret is kept invariant.

And to generate points we simply need an evaluation function, and to generate polynomials we use Lagrange interpolation.

Although there turns out to be a more computationally efficient algorithm to generate the y-intercept given the points on the polynomial.

And now to place a simple API on top of these polynomials we can create a Secret Sharing library. Note that here we encode the secret in the coeffiecients of the polynomials, which means for very large secrets you need higher degree polynomials (each coefficient can only store so much of the secret), but you can maintain the threshold by handing out more shares to each individual.

And below is an example using the Secret Sharing library, and following that is an example of a secure multi-party computation.

The full repo can be found here.

While I have shown you the sum operation for secure multi-party computation, multiplication is more difficult, but if you want to calculate arbitrary functions for secure multi-party computation, it will be necessary.

Now you can share secrets that require a threshold of people to recreate, which has many applications. A fun one to try is to "store" a password across multiple devices, where each device has a share of the password. If you have 8 devices, then perhaps use a threshold of 6 (devices can break sometimes), and whenever you want the password you query each device. This means you no longer have a single point of failure for your passwords. Someone would have to either hack 5 of your 8 devices to break in, or disable 3 of your 8 devices to launch a denial of service attack. This is a lot better then a single device that can be hacked or broken.