# Is the polynomial reconstruction problem really “intractable”?

In the family of the believed (experts haven't come yet with a solution) intractable problems in cryptography belongs the Polynomial Reconstruction problem in which an attacker is given $n$ points in which at least $t$ belong to the evaluation of a polynomial $p$ of degree $k$ and the attacker wishes to reconstruct $p$. (where $n>t>k$) The problem has been the basing building block for crypto primitives as public key encryption, block cipher, and oblivious polynomial evaluation.

The reduction for the security proof comes from decoding random reed-solomon codes. My question is the following: Why this is treated as an intractable problem as a very naive idea is to reconstruct the polynomial $p$ by simple Lagrange interpolation after picking up all the ${t} \choose{n}$ elements ?

-
If I'm not mistaken the Polynomial Reconstruction Problem requires solutions with polynomials over a field, rather than real solutions that Lagrange interpolation produces. However I very well might be mistaken. –  orlp Jul 23 '13 at 16:42
Well to reconstruct the polynomial, you can perform Lagrange interpolation (it works over a field) if you can guess a subset than only contains correct points. The hardness of the problem essentially comes from the fact that you need to enumerate many subsets to get one which avoids all bad points. –  minar Jul 23 '13 at 17:22

You suggested trying all subsets of size $t$ and applying Lagrange interpolation to them. However, for the size of parameters we use in cryptography, this would take far too long: the running time would be exponential, and in particular, the computation would take longer than your lifetime.

In fact, that's one of the criteria we use for picking the $k,t,n$ parameters. We pick them so that the kind of attack you outline will be infeasible (and so that all other known attacks will be infeasible as well).

(A small optimization: you don't need to try all subsets of size $t$. It's enough to randomly try subsets of size $k+1$, apply Lagrange interpolation, and keep trying until you find one where the resulting polynomial agrees with at least $t$ of the points. However, this iterative process still takes exponential time before you can reasonably expect to find a valid solution. There are ${t \choose k+1}$ good subsets out of all ${n \choose k+1}$ possibilities, so this will require about ${n \choose k+1}/{t \choose k+1}$ iterations. For the parameter choices that we use in cryptography this is still exponentially large: too large to finish in your lifetime.)

-

The polynomial $p$ of degree $k$ can be reconstructed if at least $k+1$ correct points are known (that is, we know that $(x_i,y_i), 0 \leq i \leq k$ are correct meaning that $y_i = p(x_i), 0 \leq i \leq k$), and in this case, Lagrangian interpolation works. If the points are being made available one at a time instead of all at once, Newtonian interpolation is an even better method for on-line interpolation.

If an adversary finds out $n$ points of which at least $t > k$ points are correct (though the adversary does not know which $t$ points are correct), then the adversary can use Reed-Solomon decoding techniques to determine $p$ as long as $t \geq \frac{n-(k+1)}{2}$, that is, among the $n-(k+1)$ "extra points", there are at least as many correct points as there are incorrect points. The Reed-Solomon decoding process will also tell the adversary which of the points are incorrect. Note that the adversary knows the values of $k$ and $n$ but not necessarily the value of $t$ but can still use the Reed-Solomon decoding process, and this process is guaranteed to find $p$ (as well as $t$) and to identify the incorrect points as long as there are at least as many correct extra points as incorrect points.

What happens when there are fewer correct extra points than incorrect points? Well, the adversary does not know this and can launch the Reed-Solomon decoding process but the process will recover $p$ only in extraordinarily rare circumstances. The process will find some polynomial $\hat{p}$ but the adversary can readily determine that this is not the right answer by checking whether $\hat{p}(x_i)$ equals $y_i$ for most of the points (as it should for the correct $p$).

-