International Association
for Cryptologic Research

The security of homomorphic encryption over the integers and its variants depends on the hardness of the Approximate Common Divisor (ACD) problem. In this paper we review and compare existing algorithms to solve the ACD problem using lattices. In particular we consider the simultaneous Diophantine approximation method, the orthogonal lattice method, and a method based on multivariate polynomials and Coppersmith's algorithm that was studied in detail by Cohn and Heninger. We give a novel analysis of these algorithms that is appropriate for some of the recent variants of the ACD problem.

One of our main contributions is to compare the multivariate polynomial approach with other methods. We find that Cohn and Heninger made certain assumptions that give a misleading view of the best choices of parameters for that algorithm. Instead, the best parameters for practical cryptanalysis seem to be those for which the algorithm becomes the orthogonal lattice algorithm.

Another contribution is to consider a sample-amplification technique for ACD samples, and to consider a pre-processing algorithm similar to the Blum-Kalai-Wasserman (BKW) algorithm for learning parity with noise. We explain why, unlike in other settings, the BKW algorithm does not give an improvement over the lattice algorithms.