Our results fit into a broader context of analogies between cryptanalysis and coding theory. The multivariate approximate common divisor problem is the number-theoretic analogue of noisy multivariate polynomial interpolation, and we develop a corresponding lattice-based algorithm for the latter problem. In particular, it specializes to a lattice-based list decoding algorithm for Parvaresh-Vardy and Guruswami-Rudra codes, which are multivariate extensions of Reed-Solomon codes. This yields a new proof of the list decoding radii for these codes.
Category / Keywords: foundations / Coppersmith's algorithm, lattice basis reduction, approximate common divisors, fully homomorphic encryption, list decoding, Parvaresh-Vardy codes, noisy polynomial interpolation Date: received 12 Aug 2011, last revised 13 Mar 2012 Contact author: nadiah at cs ucsd edu Available format(s): PDF | BibTeX Citation Version: 20120314:015506 (All versions of this report) Short URL: ia.cr/2011/437