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
-
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},
url = {https://eprint.iacr.org/2016/215}
}
