In Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Yuanmi Chen and Phong Q. Nguyen (preprint here) propose a new algorithm for solving the approximate GCD problem. It drops the complexity from to in the general case and from to in the partial case (one multiple of is given noise-free) which is a pretty big deal.
The algorithm is based on two key ideas (explained using the partial approximate GCD problem):
1. Noisy solving reduced to noise-free solving
Similar to Arora & Ge’s algorithm for solving LWE Chen and Nguyen reduce the approximate solving problem to a noise-free solving problem. In fact, the strategy is exactly the same (cf. also this post). Given noisy ideal elements where are generators of the ideal, are ring elements and are small noise terms, then
will be elements of the ideal spanned by if is big enough (depending on the exact setup we may drop the part). In the approximate GCD case is simply a small odd integer (often denoted ). Additionally, if we are given some sufficient “description” of some sufficiently big ideal (i.e., all elements of are in but not vice versa and is considerably bigger than ) then we can compute
which keeps the size of small-ish. This is the role of , the noise free multiple of in the partial approximate GCD problem. Now, one simply solves the noise free system . In the PAGCD case this means to compute a single GCD, in the multivariate polynomial case (including LWE) this means to compute a Gröbner basis (or linearise, which is the same thing for the cases we are concerned with). Hence, so far Arora&Ge and Chen&Nguyen are really the same thing (it should be mentioned that this ideal due to Nguyen was already mentioned in this paper) applied to different rings.
However, this is not really why the Chen & Nguyen algorithm is efficient (although this already provides a speed-up by a factor of 5).
2. Efficient multiplication
The key idea to drop the exponent from to is as follows. Instead of computing with integers we compute univariate polynomials mod , i.e. one defines
and notices that for :
i.e., we can reduce multiplications to multiplications and polynomial evaluations. It turns out, this can be done in . For the details read the paper.
But to get back to my previous point: It turns out the Arora&Ge perspective on noisy system solving is also useful for approximate GCDs. Which provides further evidence that it is useful to generalise LWE and AGCD to ideal theoretic problems in multivariate polynomial rings.