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.