Paper 2011/437

Approximate common divisors via lattices

Henry Cohn and Nadia Heninger

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^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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Coppersmith's algorithmlattice basis reductionapproximate common divisorsfully homomorphic encryptionlist decodingParvaresh-Vardy codesnoisy polynomial interpolation
Contact author(s)
nadiah @ cs ucsd edu
History
2012-03-14: revised
2011-08-15: received
See all versions
Short URL
https://ia.cr/2011/437
License
Creative Commons Attribution
CC BY

BibTeX

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