filename        : noisy
title           : Noisy Polynomial Interpolation and Noisy Chinese Remaindering
author          : Daniel Bleichenbacher and Phong Nguyen
type            : inproceedings
organization    : Lucent Technologies, Ecole normale superieur
booktitle       : Advances in Cryptology -- Proceedings of EUROCRYPT '2000 
series          : Lecture Notes in Computer Science
publisher       : Springer-Verlag, Berlin
editor          : B. Preneel
volume          : 1807
pages           : 53 -- 69
keywords        : cryptanalysis, lattice basis reduction, noisy polynomial interpolation, chinese remainering
abstract        :  

The noisy polynomial interpolation problem is a new intractability
assumption which was 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 most of the practical 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 well-known
duality between polynomials and integers.