# Can quantum algorithms solve the approximate GCD hard problem efficiently?

Some cryptographic schemes are based on the hardness of this problem. The answer to this question determines if those schemes are quantum resistant or not. There are a number similar questions but they consider the classic security not the quantum security. Thank you

In the $$(\gamma, \eta, \rho)$$-AGCD problem, all the samples are of the form $$x_i := pq_i + r_i$$

for $$q_i$$ uniform from $$[0, 2^\gamma / p [ ~ \cap \mathbb Z$$;

$$r_i$$ uniform from $$]-2^\rho, 2^\rho [ ~ \cap \mathbb Z$$;

and $$p$$ a fixed random prime of $$\eta$$ bits.

This problem is believed to be quantum secure. See, for instance, this paper published in PKC 2017.

Moreover, a variant of the AGCD problem in which the noise term is sampled from a continuous Gaussian distribution, then it is rounded to integer (instead of being uniform in the integer interval from $$-2^\rho$$ to $$2^\rho$$) was proven to be basically equivalent to the LWE (see this paper published in EUROCRYPT 2015), and LWE is also believed to be quatum secure.

However, you have to be careful with other variants of the AGCD problem that are commonly used. For example, the "first is noiseless" variant (known by noise-free AGCD), in which $$x_0 := pq_0$$, that is, a multiple of $$p$$ without noise, is used in several papers and is obviously not quantum secure, as one can quantumly factor $$x_0$$.