# 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 > \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?

• My quick educated guess is that LLL reduction does not give a good enough solution (i.e., short enough vectors) to break DGHV. Remember that LLL only gives an exponential (in the dimension) approximation to the shortest vector. Breaking DGHV would require a much smaller approximation, and thus much higher running time—exponential in $\lambda$, if all the calculations are right. – Chris Peikert Oct 2 '18 at 21:58
• It gives the right answer iff t > the bound I stated – robertkin Oct 2 '18 at 21:59
• But here “Reducing a $t$-dimensional lattice” does not mean just running LLL on it; you need a shorter vector than LLL would give, which requires more time to find. Your calculations don’t appear to have accounted for the approximation factor required to break DGHV. – Chris Peikert Oct 2 '18 at 22:02
• From page 5, the bound on t is obtained by comparing the gap between the sizes of our target vector and the next independent shortest vector in the lattice. LLL solves the AGCD if the ratio of their norms is greater than $2^{t/2}$, because LLL is guaranteed to find a vector within that bound of the shortest vector. – robertkin Oct 2 '18 at 22:44
• As far as I can tell your explanation below appears to make sense. It’s a bit puzzling because I had thought that the formulas were claimed to yield (asymptotically) exponential $2^\lambda$ security for parameters that were polynomial in $\lambda$. But LLL has a polynomial running time for such parameters. – Chris Peikert Dec 6 '18 at 2:02

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 $$>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.