# 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

## 2 Answers

This doesn't address your question; however the algorithm in the paper is broken. The paper does show that recovering the key requires you to solve the approximate GCD problem (which may be difficult); what they don't show is whether recoverying the plaintext requires solving a hard problem. It turns out that it isn't that difficult at all (a bit of linear algebra), and hence the attacker can get at what he really wants (after all, the only reason we're interested in the private key is because the key would give us access to the data).

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.

This doesn't address the question of "is approximate GCD a hard problem"; however it does break that specific cryptosystem.

Another issue with the mentioned paper is that a single value is always encrypted into the same linear subspace for a fixed key. If it is used in database encryption, encrypting a column of true/false values say, all the encrypted values will lie in two different linear subspaces. These can be separated and the data values can be reconstructed up to a linear transformation, allowing them to be clustered. You'll end up with a group of all the true values, and a group of all the false values, but you won't know which is which without other information...

• So the scheme would fall due to a known-plaintext attack? – SEJPM Oct 15 '15 at 16:23