In Advances in Cryptology -- Proceedings of EUROCRYPT '00
(May 14 -- 18, 2000, Bruges, Belgium),
B. Preneel (Ed.),
vol. 1807 of
Lecture Notes in Computer Science,
Springer-Verlag.
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.