Algorithms for the approximate common divisor problem

Steven Galbraith, Shishay Gebregiyorgis, Sean Murphy

Research output: Contribution to journalArticlepeer-review

195 Downloads (Pure)


The security of several homomorphic encryption schemes depends on the hardness of variants of the Approximate Common Divisor (ACD) problem. We survey and compare a number of lattice-based algorithms for the ACD problem, with particular attention to some very recently proposed variants of the ACD problem. 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.

We also briefly discuss a sample-amplification technique for ACD samples and a pre-processing algorithm similar to the Blum-Kalai-Wasserman (BKW) algorithm for learning parity with noise. The details of this work are given in the full version of the paper.
Original languageEnglish
Pages (from-to)58-72
Number of pages15
JournalLMS Journal of Computation and Mathematics
Issue numberA
Early online date26 Aug 2016
Publication statusPublished - 26 Aug 2016

Cite this