Polynomials and Secret Sharing

How (mostly) high school-level math allows splitting responsibility

There are many pieces of mathematics that you’ll hear students complain are “inapplicable to real life.”¹ Algebra is a surprisingly common one, despite the fact that it is incredibly useful in every STEM field, for a start.² And while I do think that there are some topics in the algebra curriculum that are probably outdated, students will complain about studying, say, polynomials, which are actually very applied.

Let me give you a very non-standard application of polynomials: secret sharing. We will mostly stick to high-school level math… except that there will be a surprise twist at the end that will force us to venture a bit beyond.

We’ll start with a toy example. Suppose that you are the manager of a bank. You have a cache of money coming that needs to be locked away in the safe, but you won’t be there when the delivery is made. You will have to ask your tellers to unlock the safe for you. Unfortunately, you don’t trust any single one of them enough to just give them a key, out of fear that they might steal something. However, you feel quite confident that if three of them are watching each other, then none of them will attempt anything. So, what you would like to do is to set up a system where each of them has part of a key that doesn’t allow them to open the safe by itself, but if any three of them get together, then they can open the safe.

This is the basic idea behind secret sharing—you want to distribute a share of a secret between a number of recipients, such that no one of them can determine the secret by themself, but if some specified number of them get together, then they can. This has very practical application in computer security, because you might have a number of different servers, users, or devices that you would like to collectively have access to secure information, such as someone’s banking information, or perhaps a database of passwords. However, you might be wary that some might be malicious or become compromised, so you set things up so that only several working together can actually do the desired task.

For example, let’s suppose that I lose login information for some repository. I can designate a number of users ahead of time who each hold a share of my password. If enough of them agree, I will be able to restore the lost information. Observe that there is a measure of security (no one user will be able to get into my files) and redundancy (if one user loses their share, I can simply find someone else).

Now, how do you actually make secret sharing work? Well, this is where polynomials come into play. There are a couple of different schemes, but the original one, and the one that is probably still the most widely used, is Shamir’s Secret Sharing. Here’s a simplified version of it: suppose that you want any k shares to be able to recover the password, which is some integer N. You make the complete key a k−1 degree polynomial, where N is the constant term—so, for instance, in the example above, where we want three tellers to be able to open the safe, maybe the password is 1043, so we might make the secret polynomial be

\(3X^2−531X+1043.\)

Each of the shares will be a point on this polynomial—so, if there are six tellers, you might give each of them one of the following points:

\(\begin{align*} (−3,&2663),\\ (−2,&2117), \\ (−1,&1577), \\ (1,&515), \\ (2,&−7), \\ (3,&−523). \end{align*} \)

Here’s the kicker: no one teller can figure out from their one point what the original quadratic polynomial was. No two tellers can figure out what the original quadratic polynomial was. But if any three of them come together, they can work out that there is a unique quadratic polynomial passing through all three points, and from that, they can work out that the password is 1043.

What is at the heart of this? The core observation is that there is a unique degree ≤d polynomial through any d+1 points. Therefore, if you know at least d+1 points on the graph of the polynomial, you can reconstruct it uniquely and find its constant term. But if you know fewer than d+1 points, then this is flatly impossible.

Below is an illustration of how you can find a unique cubic through any four points. The corresponding secret key is highlighted in orange.

Okay, but how can we prove that there is a unique such polynomial, and how can we construct it?

Let’s start by proving that there can’t be two such polynomials. Specifically, suppose that I have d+1 points (x₁,y₁), (x₂,y₂),… (x_d+1,y_d+1) with x₁<x₂<…<x_d+1, and I have two polynomials P₁, P₂ of degree ≤d that pass through these points: that is, for i=1,2,…,d+1, I have that

\(P_1(x_i)=y_i=P_2(x_i).\)

Well, suppose I subtract these two polynomials, and consider the new polynomial Q=P₁-P₂. Then for i=1,2,…,d+1, we will have

\(Q(x_i)=P_1(x_i)-P_2(x_i)=0.\)

But that is to say that Q has at least d+1 roots. On the other hand, Q is a polynomial of degree ≤d. And now we have a bit of a problem, because a non-zero polynomial of degree ≤d can have at most d roots. That means that Q=0 identically, which in turn means that P₁=P₂.

So, there is at most one such polynomial. We still need to find an example. We’ll construct one using Lagrange polynomials.

We start by considering a simpler problem than trying to fit a polynomial through (x₁,y₁), (x₂,y₂),… (x_d+1,y_d+1): let’s assume that all but one of the y_i’s are zero, and the remaining one (call it y_j) is 1. That means, of course, that all of the x_i’s (other than x_j) are zeros of this polynomial. So, as a first attempt, we might consider defining the polynomial

\(P_j(X) := \prod_{i \neq j} (X-x_i).\)

(The product notation here just means that we are multiplying together all terms of the form X-x_i other than when i=j.) This has the correct behavior in that P_j(x_i)=0 for all i≠j. But

\(P_j(x_j) = \prod_{i \neq j} (x_j-x_i),\)

and there is no reason whatsoever to expect it to be 1. Thankfully, that doesn’t matter: whatever it is, it isn’t 0, which means that we can divide by it. And this allows us to define what we might call the j-th basis polynomial:

\(B_j(X) := P_j(X)/P_j(x_j).\)

This has the correct behavior for all of the x_i’s. Below is an example of these four basis polynomials for cubics, where x₁=-6, x₂=-4, x₃=1, and x₄=5.

But here’s the trick: if we understand how to construct these basis polynomials, getting a polynomial through any d+1 points is very straightforward. It is just

\(L(X):=\sum_{i=1}^{d+1} y_i B_i(X).\)

Do you see why it is the right thing? Think about what happens when we evaluate L(x_j). For almost all i—specifically, for all i≠j—B_i(x_j)=0, which means that those terms don’t contribute anything. But when i=j, we get slightly different behavior: B_j(x_j)=1, which means that the j-th term in the summation contributes a factor of y_j. Putting all of that together, we see that L(x_j)=y_j for all j, as requested.

We have found a way to compute our interpolating polynomial!

Observe that—as promised—the mathematics involved has been comparatively simple, at a level where a clever high-school student should be able to follow it. But now I must reveal that there has been a subtle lie woven throughout this discussion: I have probably made you believe that we were working with real numbers (certainly, that is how I have illustrated it), but that is actually not a good idea for how to implement Shamir’s protocol.

To better understand why, let’s see what happens if we try to produce our polynomial by randomly choosing each coefficient.

Do you see some of the issues here? First, while we may select our coefficients to be small integers, polynomials grow quickly.³ So, we should expect that the values at our randomly selected points will be much, much larger than our coefficients, on average.

This is a cumbersome logistical problem, but manageable. The bigger issue is this: knowing the location of even a single point on this polynomial can give me more information than I am supposed to. For example, let’s say that I know that the coefficients were chosen randomly from -10 to 10 to form a cubic P, and I know that P(19)=159. What can I conclude from this?

Well, first of all, can it be that the X³ coefficient is non-zero? No, because if

\(P(X)=c_0+c_1 X+c_2 X^2 + c_3 X^3\)

then

\(\begin{align*} |P(19)|&\geq\left|c_3 19^3\right|-\left|c_0 + c_1 19 +c_2 19^2\right| \\ &\geq 19^3-\left(10+10\cdot 19+ 10\cdot 19^2\right) \\ &=6859-3810=3049, \end{align*}\)

which is too big. Therefore, c₃=0. In fact, by the same reasoning, c₂=0 as well:

\(\begin{align*} |P(19)|&\geq\left|c_2 19^2\right|-\left|c_0 + c_1 19\right| \\ &\geq 19^2-\left(10+10\cdot 19\right) \\ &=361-200=161. \end{align*}\)

So, now I know that c₀+19c₁=159. What can I do to reduce this further? Let’s use modular arithmetic: this is just like regular addition and multiplication of integers, except that we consider everything up to multiples of some chosen modulus N—that is, we think of two integers a and b to be “the same” modulo N if a-b is a multiple of N. So, for instance, 15=7=-1 mod 8.

You can define addition and multiplication modulo N as normal. So, we can compute something like 19+4=23=15=7 mod 8. You can check that it doesn’t matter if we switch out by a multiple of 8 before or after doing the operation. (In this example, 19+4=11+4=3+4=7 mod 8, in agreement with our other calculation.) I’ll skip doing it here, although it isn’t hard if you are willing to do a bit of algebra.

Now, observe that c₀+19c₁=159 modulo 19 is the same thing as c₀=7 mod 19. So that means that c₀=7+19k for some integer k. But we know that c₀ is between -10 and 10! Ergo, c₀=7—simply knowing a single point on our polynomial (and knowing how it was constructed) was enough to completely determine the secret key!

That is completely unacceptable. Thankfully, the tool that we introduced at the very end is precisely our salvation: we’re going to replace integer (or real) arithmetic with modular arithmetic. That is, rather than considering polynomials P with integer coefficients, we will consider polynomials P considered modulo N, for some large integer N.

What N should we choose? If you know a bit about how numbers are stored in a computer, you will likely suggest taking N to be a large power of 2.

But there is a potential problem with this idea. We have proved that there is a unique real polynomial of degree d that will pass through any d+1 points. Is it true that there is a unique polynomial modulo N of degree d that will pass through any d+1 points?

It is not.

Suppose that I am looking for a quadratic polynomial P such that P(1)=P(3)=P(5)=0 mod 8. So we have 3 points and a polynomial of degree 2—naively, we expect to find exactly one polynomial that will satisfy this condition. It is easy to see that P=0 will work. But there are others! Here is the full list:

\(\begin{array}{c} 3 X^2-3 \\ -X^2+4 X-3 \\ 2 X^2-2 \\ -2 X^2+4 X-2 \\ X^2-1 \\ -3 X^2+4 X-1 \\ 0 \\ 4 X^2+4 X \\ 1-X^2 \\ 3 X^2+4 X+1 \\ 2-2 X^2 \\ 2 X^2+4 X+2 \\ 3-3 X^2 \\ X^2+4 X+3 \\ 4 X^2+4 \\ 4 X+4 \end{array}\)

That’s a lot more than one might expect! I’m not going to go through all of them, but let’s double-check one of the easier ones, X²-1:

\(\begin{align*} 1^2-1 &= 0 \pmod 8 \\ 3^2-1 &= 8 = 0 \pmod 8 \\ 5^2-1 &= 24 = 0 \pmod 8. \end{align*}\)

So does that break the whole scheme before we have even gotten it off the ground? Thankfully, no.

There is a handy trick: take N to be a prime number. In that case, a whole host of nice things become true.

1. In arithmetic modulo a prime p, you can not only add, subtract, and multiply, but you can also divide by anything that isn’t 0 (modulo p). (The formal term is that arithmetic modulo p forms a field.)

2. For any two polynomials A,B≠0 modulo p, there exist polynomials Q, R such that A=BQ+R and the degree of R is less than the degree of B.

3. A non-zero polynomial of degree d can have at most d roots.

4. There is a unique polynomial of degree d through any d+1 points, and it is the Lagrange interpolating polynomial.

The first fact isn’t so difficult—I would demonstrate the proof in the first two weeks of an elementary number theory course. The second fact takes more setup, but not much more. I will eventually get to posting my number theory notes, but I’m delaying this for now.

The third fact is an immediate consequence of the second: if P is a polynomial with a root at a, then I know that P=(X-a)Q+R, and since the degree of R is less than X-a, it must be a constant. Plugging in X=a, I see that actually R=0. If I repeat this for the other roots, I will find that P=c(X-a₁)(X-a₂)…(X-a_k). If k is greater than the degree of P, this is a problem: the degree of the left-hand side is smaller than the degree of the right-hand side! This is impossible, hence P=0.

To prove the fourth fact, just go through our proof of this in the case where we were dealing with real polynomials and check that facts (1), (2), and (3) fill in all of the possible holes when adapting this for polynomials modulo p.

And that’s it! With this small change, Shamir secret sharing works exactly as it is supposed to. You choose a polynomial modulo p of degree d uniformly at random (just select each coefficient 0,1,…,p-1 randomly), and then choose some subset of points to give as shares. Knowing fewer than d+1 points really does tell you nothing about the value of this polynomial at zero: each possibility is equally likely.

1. As a side note, I am always skeptical of the extent to which any such complaint should be taken seriously: it suggests that if this were something very practical, then students would gladly study it. But I have yet to see a single person be excited about learning taxes, and almost everyone in my generation devoured the Harry Potter books, even though it is unlikely that knowing what “Expelliarmus” does will ever be useful.

2. Although, many people do algebra without recognizing that is what they are doing. I find this surprisingly common among some programmers, particularly. I’m once again reminded of Joshua Gross’s story of how calling Boolean logic “Boolean algebra” had a quantifiably negative effect on the test scores of his students.

3. Okay, okay. In the grand scheme of things, even in computer science, polynomials are some of the slower-growing functions. But, still, if you are trying to keep all of your variables and coefficients within a common range, having something that grows appreciably faster than linear is going to be an issue.