Paper 2011/437

Approximate common divisors via lattices

Henry Cohn and Nadia Heninger


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^2}$ to $N^{\beta^{(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 $2^{\sqrt{n}}$ approximation algorithm for lattice basis reduction in $n$ dimensions could be used to break these parameters. We have implemented our 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 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Coppersmith's algorithmlattice basis reductionapproximate common divisorsfully homomorphic encryptionlist decodingParvaresh-Vardy codesnoisy polynomial interpolation
Contact author(s)
nadiah @ cs ucsd edu
2012-03-14: revised
2011-08-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Henry Cohn and Nadia Heninger},
      title = {Approximate common divisors via lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2011/437},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.