#### Vol. 1, No. 1, 2013

 Recent Volumes 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index MSP Books and Monographs Other MSP Publications
Approximate common divisors via lattices

### Henry Cohn and Nadia Heninger

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