Cryptology ePrint Archive: Report 2016/215
Algorithms for the Approximate Common Divisor Problem
Steven D. Galbraith and 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.
Category / Keywords: Approximate common divisors, lattice attacks, orthogonal lattice, Coppersmith's method
Original Publication (with major differences): Algorithmic Number Theory (ANTS-XII) 2016
Date: received 29 Feb 2016, last revised 1 Jun 2016
Contact author: s galbraith at auckland ac nz
Available format(s): PDF | BibTeX Citation
Version: 20160601:223750 (All versions of this report)
Short URL: ia.cr/2016/215
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]