Paper 2016/215

Algorithms for the Approximate Common Divisor Problem

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Algorithmic Number Theory (ANTS-XII) 2016
Keywords
Approximate common divisorslattice attacksorthogonal latticeCoppersmith's method
Contact author(s)
s galbraith @ auckland ac nz
History
2016-06-01: revised
2016-02-29: received
See all versions
Short URL
https://ia.cr/2016/215
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/215,
      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{https://eprint.iacr.org/2016/215}},
      url = {https://eprint.iacr.org/2016/215}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.