# Fast attack on approximate GCD problem?

This question is about the approximate GCD problem which is defined as follows: Given any number of the approximate multiples $a_i = p \cdot q_i + r_i$ of $p$, where $p$, $q_i$ and $r_i$ are integers, the problem is to find the hidden common divisor $p$. Note that $q_i$ and $r_i$ change in each $a_i$.

I've recently read “Practical Fully Homomorphic Encryption without Noise Reduction” by Liu, about a fast symmetric FHE scheme, which is based on the approximate GCD problem. Now the paper claims that it reaches 128-bit security by increasing the linear search space's size to $>2^{128}$.

Is there any attack on the approximate GCD problem, that is faster than brute-force (trying out all possible approximate GCDs)?

As an example set of (brute-force secure?) parameters, I'd say that $\log_2q_i\approx64\approx\log_2r_i$ and $\log_2p\approx 128$ should be secure against brute force as one would need $2^{128}$ tries for retrieving $p$ or would have to try more than $2^{64}*2^{64}=2^{128}$ values for $q_i$ and $r_i$.

• @D.W., I hope the sample parameters are valid and out of reach for exhaustive search. I think the "structure" I choose is valid and hope actually used in real FHE schemes. The question aims at AGCD FHE instances (most of which I don't know) so these instances should be considered when reading the question. – SEJPM Jul 27 '15 at 12:38
• OK. There are lattice-based algorithms for this problem (Cohn & Heninger), continued fraction based methods, and more. Have you done a literature search? Did you check Google Scholar? I think you'll find some stuff there -- you might want to do a literature search, compile everything you find, then answer your own question with a summary of the known attacks. – D.W. Jul 27 '15 at 16:11

The insight behind this is that the decryption process for a fixed private key is entirely linear; the system attempts to make decryption without the key infeasible by restricting all plaintexts to be within an $N-1$ dimension subspace (where the ciphertexts are vectors of size $N$); however if the attacker knows $N-1$ linearly independent ciphertexts, and the values they correspond to, then he can, for any ciphertext within that $N-1$ dimension subspace, find the linear combination of the known ciphertexts that make it up (and hence deduce the plaintext that corresponds to it). Since any valid ciphertext will be within that linear subspace (that's inherent in the system), that means that we can decrypt anything.