A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the FHE Based on the GACD problem

Abstract. In this paper, we propose a new algorithm for solving the general approximate common divisors (GACD) problems, which is based on lattice reduction algorithms on certain special lattices and linear equation solving algorithms over integers. Through both theoretical arguments and experimental data, we show that our new algorithm works in polynomial time but under roughly the following condition: – There is a positive integer t such that γ + η t + + ρ < η; t H – We have more than t GACD samples. or equivalently H(η − ρ) 2 − 4(γ + η)> 0 – We have more than t = ⌈ H(η−ρ)− H2 (η−ρ) 2−4H(γ+η) ⌉ GACD samples