Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values
arXiv:1401.1331v118 citations
Originality Synthesis-oriented
AI Analysis
This addresses a specific cryptographic problem for secure key distribution, but appears incremental as it modifies an existing noisy polynomial interpolation problem.
The paper tackles the problem of recovering an unknown polynomial from noisy modular evaluations over a short interval, motivated by a key distribution scheme, and presents results on interpolation and approximation in finite fields.
Motivated by a recently introduced HIMMO key distribution scheme, we consider a modification of the noisy polynomial interpolation problem of recovering an unknown polynomial $f(X) \in Z[X]$ from approximate values of the residues of $f(t)$ modulo a prime $p$ at polynomially many points $t$ taken from a short interval.