Secret sharing with maths

February 1st, 2019

I’m currently working my way through Jeremy Kun’s A Programmer’s Introduction to Mathematics. One of the exercises in Chapter 2 asks you to create a web app to implement secret sharing using polynomial interpolation. I went a little overboard and made PolyShare. I put a bit more effort into the app than strictly required to answer the book question and this post goes into some of the details.

What does it do?

The app keeps a number secret, but allows you to create as many tokens (called shares) as you want. The twist is that not all the shares are required to decode the number. You can decide how many people need to be together to decode the secret.

In the book the example secret is the code to a safe containing a will. Each child is given a token but not all of them need to be present to obtain the safe code. You could also use this for scavenger hunt type games where contestents have to find say six locations out of ten. It doesn’t matter which six they find as any combination will be able to get the secret. However having just five does not give them any more information than having zero so they can’t guess.

The Tech

The app is a Create React App single page app that runs entirely in the browser. No backend APIs are needed so it’s all nicely self contained. It’s hosted on S3 via a CloudFront distribution setup using code very similar to the code I wrote about earlier.

This was my first time using CRA in over a year and I found it smoother and easier to use than before. I’m very impressed by it and will be happy to use it again when I’ve a problem that fits.

I decided to add Typescript into the mix too so I could compare it with Flow which I’d used previously. The documentation for CRA and Typescript was excellent. Almost every time I had a problem or wanted to know how to do something the answer wasn’t too hard to find and understand.

The Math

The following theorem underlies the process. Don’t worry if it makes your eyes glaze over, go and buy the book! I’m not going to prove it here but try and explain how things work and how they’re implemented in the code.

Theorem 2.2. For any integer n \geq 0 and any list of n + 1 points (x_0,y_0),(x_1,y_1),...,(x_n,y_n) in \Reals^2 with x_0 < x_1 < ··· < x_n, there exists a unique degree n polynomial p(x) such that p(x_i) = y_i for all i.

When trying to understand a theorem the book recommends an approach that reminds me of wrapping characterisation tests around a piece of legacy code you don’t understand. That’s been a very helpful way of thinking for me and prevented me running scared from the math!

The degree of a polynomial is the value of the highest power of x. So for 1 + 2x + 3x^2 the degree would be 2 and for 6x^4 + 3x^{10} it would be 10.

What the theorem says is that if you have say 3 points then there is a unique degree 2 polynomial that goes through those points. (As long as those points all have different x values.)

Modular arithmetic

The worked examples in the book don’t use modular arithmetic for simplicity. However this is a requirement for any “real” system that uses this method. It ensures that information about the value of x doesn’t leak into the share values. It also ensure that if a group without enough shares tries to decode the secret then they get a random number that tells them nothing about what the actual secret is. Using a prime number for the modulus makes the maths easier.

The algorithm

Generating the shares

Let say the number we want to protect is 9, we want to generate five tokens and only require three to decode. We’re going to use 11 as our modulus value.

As we want three people to be able to decode the first step is generating a degree 2 polynomial with random co-efficients in the range 0-11 apart from the constant co-efficient. This gets set to the secret value. e.g. f(x) = 2x^2 + 6x + 9.

This means that when x is 0 then the value will be our secret, 9.

To create the tokens we set x to 1, 2, 3, 4 and 5 and work out the values:

\begin{aligned} x = 1, f(x) = 2(1^2) + 6(1) + 9 = 17 &= 6 \mod 11\\ x = 2, f(x) = 2(2^2) + 6(2) + 9 = 29 &= 7 \mod 11\\ x = 3, f(x) = 2(3^2) + 6(3) + 9 = 45 &= 1 \mod 11\\ x = 4, f(x) = 2(4^2) + 6(4) + 9 = 65 &= 10 \mod 11\\ x = 5, f(x) = 2(5^2) + 6(5) + 9 = 89 &= 1 \mod 11 \end{aligned}

This gives us 5 points: (1, 6), (2, 7), (3, 1), (4, 10), (5, 1)

These are the shares to distribute to whoever we want. We know from the theorem above we can use any three to reconstruct the polynomial used to create them.

Reconstructing the secret

The code in the book uses Lagrange polynomials to reconstruct the original polynomial and find the value when x is 0.

I ported this to JS and tweaked it to handle the modular arithmetic.

If two people get together and try to decode the secret then they will get an answer but it won’t be the correct one. According to the book it can be proven that the value they get will not be related to the

Conclusion

This was fun to do! It’s definitely helped make the math more “real” and it was nice to see how Create React App has come along since the last time I used it.