Approximate common divisors via lattices
Henry Cohn, Nadia Heninger · The Open Book Series · 2013
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 ˇ.mC1/=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 n " approximation algorithm with " < 2=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.