## Noisy Polynomial Interpolation
and Noisy Chinese Remaindering

### Phong Nguyen

## (Joint work with Daniel Bleichenbacher (Bell Labs),
to appear at Eurocrypt' 2000.)

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