Paper 2016/215

Algorithms for the Approximate Common Divisor Problem

Steven D. Galbraith, Shishay W. Gebregiyorgis, and Sean Murphy


The security of several homomorphic encryption schemes 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. One of our main goals is to compare the multivariate polynomial approach with other methods. We find that the multivariate polynomial approach is not better than the orthogonal lattice algorithm for practical cryptanalysis. 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. This is the full version of a paper published at ANTS-XII in 2016.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.Algorithmic Number Theory (ANTS-XII) 2016
Approximate common divisorslattice attacksorthogonal latticeCoppersmith's method
Contact author(s)
s galbraith @ auckland ac nz
2016-06-01: revised
2016-02-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Steven D.  Galbraith and Shishay W.  Gebregiyorgis and Sean Murphy},
      title = {Algorithms for the Approximate Common Divisor Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2016/215},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.