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:

[ Cryptology ePrint archive ]