Noisy Polynomial Interpolation and Noisy Chinese R

Authors: Daniel Bleichenbacher Phong Q Nguyen

Publish Date: 2000/5/14

Volume: , Issue: , Pages: 53-69

PDF Link

Abstract

The noisy polynomial interpolation problem is a new intractability assumption introduced last year in oblivious polynomial evaluation It also appeared independently in password identification schemes due to its connection with secret sharing schemes based on Lagrange’s polynomial interpolation This paper presents new algorithms to solve the noisy polynomial interpolation problem In particular we prove a reduction from noisy polynomial interpolation to the lattice shortest vector problem when the parameters satisfy a certain condition that we make explicit Standard lattice reduction techniques appear to solve many instances of the problem It follows that noisy polynomial interpolation is much easier than expected We therefore suggest simple modifications to several cryptographic schemes recently proposed in order to change the intractability assumption We also discuss analogous methods for the related noisy Chinese remaindering problem arising from the wellknown analogy between polynomials and integers

Keywords: