Why is Approximate GCD a hard problem? There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.

The paper Algorithms for the Approximate Common Divisor Problem surveys several lattice reduction based algorithms for solving AGCD. All of them require $t &gt; \frac{\gamma - \eta} {\eta - \rho}$ samples to solve the $(\gamma, \eta, \rho)$-AGCD problem by reducing a particular $t \times t$ lattice.

In Section 5.2 of Fully Homomorphic Encryption over the Integers, the authors state a "rule of thumb" that lattice reduction algorithms acting on a $t \times t$ lattice take time roughly $2^{t/k}$ to output a $2^k$ approximation of the shortest vector.

However, LLL lattice reduction is known to run in polynomial time with respect to both the dimension of the lattice and the input sizes. Concretely, for the DGHV scheme where $(\gamma, \eta, \rho)$ ~ $ (\lambda^5, \lambda^2, \lambda)$, a quick estimation yields that $L^2$ lattice reduction can break DGHV in time $\lambda^{25}$ with memory $\lambda^{11}$ given $\lambda^{3}$ samples.

So why does the aforementioned paper treat the runtime of lattice attacks on AGCD as exponential?
The answer is that just because your algorithm is polynomial time doesn't mean it's fast.

The paper Algorithms for the Approximate Common Divisor Problem claims in section 3.1 that a lattice dimension $&gt;800$ "should be large enough to prevent any practical lattice attack".

As a completely non-rigorous yet enlightening demonstration, we can compare the complexity of a brute-force the noise" approach with the lattice-based methods for $(\lambda^5,\lambda^2, \lambda)$-GCD.

The "brute-force the noise" approach involves $\mathcal{\tilde O}(2^{\frac{3}{2} \rho })$ multiplication/remainder operations on numbers with $\approx \gamma$ bits, where $\mathcal{\tilde O}$ is the usual notation hiding poly-logarithmic factors. So let's say it takes time $\propto \gamma \cdot 2^{\frac{3}{2} \rho } \sim\ \lambda^5 \cdot 2^{\frac{3}{2} \lambda } $.

The SDA lattice algorithm using fpLLL (aka $L^2$ lattice reduction) takes time $\mathcal{\tilde O}(\gamma^2 \cdot t^5) \sim \lambda^{25}$, where $t$ is the dimension of the lattice.

Let's compare these two asymptotic results for the choices of parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys. (See below for more details.)
At the "small" level, the time estimation for "brute-force the noise" is $6 \cdot 10^{16}$, and for SDA is $4 \cdot 10^{25}$.
At the "large" level, the time estimation for "brute-force the noise" is $7 \cdot 10^{24}$, and for SDA is $2 \cdot 10^{34}$.

So we'd need the coefficient hidden in $\mathcal{\tilde O}$ to be a billion times smaller for SDA than for "brute force" for lattice reduction to be practical -- and we just don't have that.



However, I cannot justify the "rule-of-thumb" asserted in Fully Homomorphic Encryption over the Integers and used in Fully Homomorphic Encryption over the Integers with Shorter Public Keys that LLL takes time exponential in $t$.

Experimentally, the runtime will appear to be exponential until your sizes  are large enough that the asymptotic behavior dominates.



Note that the reason for the inadequacy of LLL is not because it only gives an exponential approximation to the shortest vector. As Nyugen notes in Predicting Lattice Reduction:


  The most important fact is that asymptotically, all the algorithms known seem to only achieve an exponential approximation factor as predicted by theory, but the exponentiation bases turn out to be extremely close to 1, much closer than what theory is able to prove.


Furthermore, Algorithms for the Approximate Common Divisor Problem examine this limitation and find that the only effect is to require a mild increase in the number of samples (and hence the lattice dimension). This is because increasing the lattice dimension increases the size of the second shortest (independent) vector in the lattice. If the ratio between the sizes of the target vector and second shortest vector is sufficiently small, then LLL will find the target vector.

We can see this concretely for the parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.
At the "small" level, $(\gamma, \eta, \rho) = (.86 \cdot 10^5, 1632, 24)$.
Ignoring the exponential approximation factor tells us we need $535$ samples. Accounting for it yields $546$ samples.
At the "large" level, $(\gamma, \eta, \rho) = (19 \cdot 10^6, 2652, 39)$.
Ignoring the exponential approximation factor tells us we need $7272$ samples. Accounting for it yields $9042$ samples.

Thus, for heuristic analysis of the lattice-based algorithms applied to AGCD, we can get away with pretending that LLL solves the Shortest Vector Problem.