In fall of 2021 I had the pleasure of taking an graduate cryptography class with UCLA’s finest professor Rafail Ostrovsky. The whole class was fascinating, I did not realize how deep cryptography could go until that class, but one of the more fascinating topics was that of Multi Party Computation (MPC). The idea isn’t too difficult, a secret is “split up” between a number of parties such that no one person knows this secret, some number of people depending on the scheme have to work together to unlock this secret. MPC involves these parties working together to do computation on this secret without ever giving up any information about the secret to anyone. The idea seems like magic and in this series of posts I’ll be going step by step through one of the more interesting means to do this.

But first we have to talk about something a little more basic. How exactly is it that we split up a secret between multiple parties in this way?

A simple case

Lets first try two people. Suppose I am living with two roommates (lets call them Ben and Jerry) and I was able to source a rare tub of my favorite ice cream. I come back the next day and discover to my horror someone ate half the tub of my ice cream. Now I don’t mind my roommates eating a spoonful of my ice cream, but it seems they ate “only a spoonful”. Having interrogated them, neither confesses to the crime and like any normal person, I buy myself a lock my ice cream up, however I still would like my two roommates to be able to open it together for dinner (I sadly will be a little late to open it for them), I know that at least one can be trusted to look after my beloved ice cream, and if both of them are together it is safe.

I have one combination number, lets say 3141, and I have to tell each of them some kind of secret such that separately they cannot open the lock, but together they can. Any normal person would of course give one the first two digits of the combination and the other the second two but this isn’t good enough, knowing two digits, means they can guess the other two digits of the lock with 100 tries, not good enough. But I am not an ordinary person I am an insane cryptographer, and I know a little trick.

I pull out a piece of graph paper and put a point at \((0, 3141)\). I draw a random line going through this point and get the line \( y = 1267x + 3141 \). I plug in \(x = 1\) and \(x = 2\) and get \((1, 4408)\) and \((2, 5675)\). I give one pair to Ben and one pair to Jerry and explain what I did without disclosing the number.

So what exactly have I done here. The astute among you may remember that two points is enough to make a line. On their own I haven’t given neither Ben nor Jerry anything near enough information to find out what lies at \(x = 0\). However together they can draw the line and figure out what lies there, and the treasures that lie in the fridge with it.

Great, my ice cream is safe. But where does this get us.

Suppose I wanted to add a third person to this mix, my good buddy Stephen. In this case we have 3 people and I want any 2 to be able to open it. Well I can abuse this trick once again, I can grab another point on this line, say \((3, 6942)\), and give it to Stephen. Now once again any of the two of them is able to open the lock and taste the malt goodness inside, with each other’s supervision of course.

This scheme is a simple case of what is known as Shamir’s Secret Sharing, SSS. Simple and elegant. We can get a little more complicated, but to do that we have to learn a little something called Lagrange interpolation.

Lagrange Interpolation: Bending the polynomial to our will

Somehow this method never showed up in my classes until taking this cryptography course and it’s a shame because it’s very elegant and shows a few unexpected things about polynomials. Just as in the above case of a line where we can take two points and construct a line, we can do this with \(k\) number of points for an \(k-1\) degree polynomial. In other words, we can take a few points a construct a polynomial that goes through them, the more points we have the higher the degree of polynomial. But how? How do we get a polynomial that passes through \((1, a), (2, b), (3, c)\)?

A natural first approach would be to think about the points which we already know how to set a polynomial through, the x axis. Every high schooler knows that we can create a polynomial going through \((1, 0), (2, 0), (3, 0)\) by just creating \(y = (x - 1)(x - 2)(x - 3)\). The problem is that since this method relies one of the terms multiplied being zero to zero all the others out, we can’t really use it. Or can we?

Its not too difficult to create a polynomial that goes through one point. We can take any old polynomial (as long as its not 0 at a) and have it go through \((2, b)\) by taking the value of \(P(2)\) and scaling it up or down to be equal to \(b\), in other words \(P(2) \times (\frac{b}{P(2)}) = b\). Combining this with what we have above is impossible through since the polynomial must be nonzero at 2 of course, beside that we are free to choose whatever polynomial we want. So what if we instead tried to get rid of what is making it 0 at 2.

If we have \(P(x) = (x - a)(x - c)\) we can scale this up by using \(P(x) \times (\frac{b}{P(2)}) = \)\( (x - 1)(x - 3) \times (\frac{b}{(2 - 1)(2 - 3)}) = \)\( (x-1)(x-3) \times b\). This is a polynomial that goes through \((2, b)\) and through \((1, 0), (3, 0)\). This gives us a method to create a polynomial going through one point and going through as many other “zero points” as we want, call these singleton polynomials.

Of course we can add other polynomials to this, we can add a polynomial that contains \((1, a)\), although this will interfere with our already set \((2, b)\)… unless the added polynomial contains \((2, 0)\). Fortunately we have a method for creating a polynomial containing a point and as many other zeros as we want.

Which brings us finally to our method. We create a bunch of these singleton polynomials, one for each point we want, setting zeroes for all the other points so that they don’t interfere, and just add them together. Each added polynomial sets one point, badabing badaboom we have our polynomial going through these points.

Which finally is what we call the method of Lagrange Interpolation.

$$ \ell(x) = \sum_{j=0}^k y_j \prod_{\frac{0 \leq m \leq k}{ m \neq j}} \frac{x-x_m}{x_j-x_m} $$

Some interesting properties

First thing one might ask when finding out about this method is about the degree of the resulting polynomial, as we can see if we have \(k\) points we create a series of polynomials of \(k-1\) degree and add them together, creating an \(k-1\) polynomial. We can of course create a higher degree polynomial if we so choose, all we have to do is add more binomial terms to any of the added equations.

This also leads to another question, we can add whatever other points to create infinite other polynomials of higher degree going through these points, but what about the simple case, how many \(k-1\) polynomials going through these points are there? This method doesn’t give us any flexibility to change the resulting polynomial without increasing its degree, its a consistent method which gives the same result every time for the same inputs. Is this just a property of the method itself, or is it fact that there is exactly one polynomial of \(k-1\) degree for any \(k\) points?

It turns out that this is fact, under what is known as the Interpolation Theorem, the solution to finding an \(k-1\) degree polynomial going through \(k\) points is unique. And the proof of it is pretty simple, suppose two such polynomials \(i\) and \(j\) exist, \(i - j\) would bring all those points down to 0, in other words we have a polynomial of degree \(k-1\) that has \(k\) zeroes, which contradicts the Fundamental Theorem of Algebra.

Armed with these facts, we can return to our sharing scheme.

Shamir’s Secret Sharing

From here our scheme finally begins to develop in full. Suppose we have \(SSS(n, k)\) where \(n\) is the number of parties and \(k\) is the minimum number of those parties we need to come together in order to unlock a secret \(S\).

Given that \(k\) is the number of points here needed to uniquely identify a polynomial we start out this scheme by creating a random polynomial of degree \(k-1\). We make sure it passes through our “secret point” by convention and for ease being along the y-axis, in other words \((0, S)\), we can just generate a few random coefficients to our polynomial and have the last term without an \(x\) be \(S\). Given this polynomial, we sample \(n\) points and distribute them among the parties.

At this point we are done. Should any \(n\) parties come together, they can recreate the polynomial and find the y-intercept, \(S\).

Security Considerations, Conclusions, and Next Steps

So far we have used normal arithmetic for this scheme, in reality there are some complications, it would work well if we could use real numbers, but we don’t live in such a world, we have to use usually natural numbers or rational numbers. This opens us up to some attacks as this itself allows an attacker to leak information about the secret with every additional point they get. We can fix this by taking this method over a finite field, but I won’t get into these intricacies here.

So I was aware of SSS for a few years but really only came to understand it and its beautiful simplicity when I took the aforementioned cryptography course. Polynomial interpolation as well was a subject I never touched at and it goes a lot deeper than what I mentioned here, Newton has his own method of polynomial interpolation as well and I’m sure theres a good number of more methods. Lagrange’s method (apparently erroneously named as he wasn’t the first to discover it), is once again beautifully simple, one that in hindsight you look and and think “geez why didn’t I think of that.” And now no one can steal your ice cream.

This was a basic introduction for what I hope to build on, my goal for these next posts is to build an Multi Party Computation scheme using SSS and just explore its uses more.

As usual, for any comments, mistakes, or just to chat feel free to email me at maksymovi@maksym.pro