We study algorithms to solve the following problem: Let $P$ be a $k$ degree polynomial over a finite field $F$. Then given $n > k+1$ sets, each containing $m-1$ random elements and one element which is the value of $P$ at a known point, the problem is to recover the polynomial $P$, provided that the solution is unique. This problem is a new intractability assumption introduced by Naor and Pinkas at STOC'99 for oblivious polynomial evaluation. It also appeared in some password identification schemes, due to its connection with secret sharing schemes based on Lagrange's polynomial interpolation. The problem is related to the polynomial reconstruction problem used in generalized Reed-Solomon list decoding. But it seems to be easier, at least in practice: indeed, we prove that there exists a reduction from noisy polynomial interpolation to the shortest vector problem in a lattice, when the parameters satisfy a certain condition that we make explicit. We also study an analogous problem with integers instead of polynomials, which is related to the problem of Chinese remaindering with errors.
Gates 498, 3/21/00, 4:15 PM