Linear Program Polynomial Interpolation

Problem: Alice chooses a secret polynomial with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of for some integer of Bob’s choice. What is the minimal number of queries Bob needs to determine exactly?Solution: Two queries. The first is, and if we call, then the second query is.To someone who is familiar with polynomials, this may seem shocking, and I’ll explain why it works in a second. After all, it’s very easy to prove that if Bob gives Alice all of his queries at the same time (if the queries are not adaptive), then it’s impossible to discover what is using fewer than queries. This is due to a fact called polynomial interpolation, which we’ve seen on this blog before in the context of. Specifically, there is a unique single-variable degree polynomial passing through points (with distinct -values).

So if you knew the degree of, you could determine it easily. But Bob doesn’t know the degree of the polynomial, and there’s no way he can figure it out without adaptive queries!

Indeed, if Bob tries and gives a set of queries, Alice could have easily picked a polynomial of degree. So it’s literally impossible to solve this problem without adaptive queries.The lovely fact is that once you allow adaptiveness, the number of queries you need doesn’t even depend on the degree of the secret polynomial!Okay let’s get to the solution. It was crucial that our polynomial had nonnegative integer coefficients, because we’re going to do a tiny bit of number theory. First, note that is exactly the sum of the coefficients, and in particular is larger than any single coefficient.

So call this, and query. This gives us a number of the formAnd because is so big, we can compute easily by computing. Now set, and this has the form. We can compute modulus again to get, and repeat until we have all the coefficients.

We’ll stop once we get a that is zero.Addendum 2018-02-14: As a small technical note, this is a polynomial-time algorithm in the number of bits needed to write down. So this demonstrates the power of adaptive queries: we get from something which is uncomputable with any number of queries to something which is efficiently computable with a constant number of queries.The obvious follow-up question is: can you come up with an efficient algorithm if we allow the coefficients to be negative integers? Here’s a simple puzzle with a neat story.

Polynomial Interpolation Algorithm

A rich old woman is drafting her will and wants to distribute her expansive estate equally amongst her five children. But her children are very greedy, and the woman knows that if he leaves her will unprotected her children will resort to nefarious measures to try to get more than their fair share. In one fearful scenario, she worries that the older four children will team up to bully the youngest child entirely out of his claim! She desperately wants them to cooperate, so she decides to lock the will away, and the key is a secret integer. The question is, how can she distribute this secret number to her children so that the only way they can open the safe is if they are all present and willing?A mathematical way to say this is: how can she distribute some information to her children so that, given all of their separate pieces of information, they can reconstruct the key, but for every choice of fewer than 5 children, there is no way to reliably recover the key?

This is called the secret sharing problem. More generally, say we have an integer called the secret, a number of participants, and a number required for reconstruction. Then a secret sharing protocol is the data of a method for distributing information and a method for reconstructing the secret. The distributing method is an algorithm that accepts as input and produces as output a list of numbers. These are the numbers distributed to the participants. Then the reconstruction method is a function which accepts as input numbers and outputs a number. We want two properties to hold:. The reconstruction function outputs when given any of the numbers output by.

One cannot reliably reconstruct with fewer than of the numbers output by.The question is: does an efficient secret sharing protocol exist for every possible choice of? In fact it does, and the one we’ll describe in this post is far more secure than the word “reliable” suggests. It will be so hard as to be mathematically impossible to reconstruct the secret from fewer than the desired number of pieces.

Independently discovered by, the protocol we’ll see in this post is wonderfully simple, and as we describe it we’ll build up a program to implement it. This time we’ll work in the Haskell programming language, and you can from. And finally, a shout out to my friend who worked together with me on this post. She knows Haskell a lot better than I do.

Polynomial InterpolationThe key to the secret sharing protocol is a beautiful fact about polynomials. Specifically, if you give me points in the plane with distinct values, then there is a unique degree polynomial that passes through the points. Just as importantly (and as a byproduct of this fact), there are infinitely many degree polynomials that pass through the same points.

For example, if I give you the points, the only quadratic (degree 2) polynomial that passes through all of them is. The proof that you can always find such a polynomial is pretty painless, so let’s take it slowly and write a program as we go. Suppose you give me some list of points and no two values are the same. The proof has two parts. First we have to prove existence, that some degree polynomial passes through the points, and then we have to prove that the polynomial is unique. The uniqueness part is easier, so let’s do the existence part first. Let’s start with just one point.

What’s a degree zero polynomial that passes through it? Just the constant function. For two points it’s similarly easy, since we all probably remember from basic geometry that there’s a unique line passing through any two points.

But let’s write the line in a slightly different way:Why write it this way? Because now it should be obvious that the polynomial passes through our two points: if I plug in then the second term is zero and the first term is just, and likewise for.For example, if we’re given we get:Plugging in cancels the second term out, leaving, and plugging in cancels the first term, leaving.Now the hard step is generalizing this to three points. But the suggestive form above gives us a hint on how to continue.Notice that the numerators of the terms take on the form, that is, a product excluding. Thus, all terms will cancel out to 0 if we plug in, except one term, which has the formHere, the fraction on the right side of the term cancels out to 1 when is plugged in, leaving only, the desired result. Now that we’ve written the terms in this general product form, we can easily construct examples for any number of points. We just do a sum of terms that look like this, one for each value. Try writing this out as a summation, if you feel comfortable with notation.Let’s go further and write an algorithm to construct the polynomial for us.