Fast attack on approximate GCD problem?

Question

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

Answer 1

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.

Answer 2

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