Vol. 1, No. 1, 2013

 Recent Volumes 1: ANTS X
 The Open Book Series About the Series Ethics Statement
Approximate common divisors via lattices

Vol. 1 (2013), No. 1, 271–293
Abstract

We analyze the multivariate generalization of Howgrave-Graham’s algorithm for the approximate common divisor problem. In the $m$-variable case with modulus $N$ and approximate common divisor of size ${N}^{\beta }$, this improves the size of the error tolerated from ${N}^{{\beta }^{\mathfrak{2}}}$ to ${N}^{{\beta }^{\left(m+\mathfrak{1}\right)∕m}}$, under a commonly used heuristic assumption. This gives a more detailed analysis of the hardness assumption underlying the recent fully homomorphic cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While these results do not challenge the suggested parameters, a ${\mathfrak{2}}^{{n}^{\epsilon }}$ approximation algorithm with $\epsilon <\mathfrak{2}∕\mathfrak{3}$ for lattice basis reduction in $n$ dimensions could be used to break these parameters. We have implemented the algorithm, and it performs better in practice than the theoretical analysis suggests.

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 multivariate polynomial reconstruction, 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.

Keywords
Coppersmith's algorithm, lattice basis reduction, fully homomorphic encryption, approximate common divisors, list decoding, Parvaresh-Vardy codes, noisy polynomial reconstruction
Mathematical Subject Classification 2010
Primary: 11Y16
Secondary: 94A60, 94B35
Milestones
Published: 14 November 2013
Authors
 Henry Cohn Microsoft Research New England One Memorial Drive Cambridge, MA 02142 United States Nadia Heninger Department of Computer Science Princeton University Princeton, NJ 08540 United States Department of Computer and Information Science 3330 Walnut St. Philadelphia, PA 19104 United States