Noisy Polynomial Interpolation and Noisy Chinese Remaindering
Daniel Bleichenbacher
Bell Laboratories
Last year Naor and Pinkas proposed a protocol for oblivious
polynomial evaluation, that is based on a new intractability
assumption, called the noisy polynomial interpolation problem.
In this talk I present a new algorithm to solve
the noisy polynomial interpolation problem using lattice basis
reduction algorithm.
It follows that noisy polynomial interpolation is much
easier than expected and that several cryptographic schemes that
have recently been proposed need some simple modifications.
Further I'll also discuss analogous methods for the related noisy
Chinese remaindering problem arising from the well-known analogy
between polynomials and integers.
The paper is joint work with Phong Nguyen.