Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
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β, this improves the size of the error tolerated from Nβ2 to Nβ(m+1)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 2nε approximation algorithm with ε < 23 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