The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$.

I would like to know how the difficulty of the problem changes when modular reduction is incorporated.

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

I could not find information on this version of the problem when searching for the term "Modular AGCD", but I am not sure what to refer to it as. It may a negligible difference between the two that does not warrant classification as a separate problem, but I am not sure. Intuitively, it seems that the variant with the modulus would be more difficult to solve. But I would like quantitative details on any differences, if there are any.


Poncho's answer highlights the fact that the sizes of the parameters are important when discussing the hardness of the problem. I am interested in the problem with the following parameter sizes:

  • $x$ is a 1792-bit prime
  • $p$ is a uniformly random 1792-bit integer
  • Each $q_i$ is a 1536-bit integer with the 1280 most significant bits uniformly random
    • The next lower 255 bits are set to 0, and the least significant bit is set to 1
  • Each $e_i$ is a 1024-bit random integer

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

Actually, if $p$ is relatively prime to $x$, and the $q_i$ values are uniformly distributed over $[0, x-1]$, then it is strictly harder than the AGCD problem, in that it is informationally secure (rather than computationally secure), that is, even if we assume that attacker has unbounded computational capabilities, he still cannot recover $p$.

The demonstration is actually fairly simple; even if we assume that attacker knows $e_i$, then for any sample value $s = pq_i + e_i \bmod x$, for any potential value $p'$, there exists a unique $q'_i$ value, namely, $p'^{-1}(s - e_i) \bmod x$ that would yield the observed sample $s$, hence the attacker gains no information about the relative probability of any candidate value $p$ (except for whether it's relatively prime to $x$)

  • $\begingroup$ This highlights the fact that I neglected to specify constraints on the parameter sizes in my question. I will update my question accordingly - I apologize for any inconvenience. Your answer is certainly correct to the question as currently stated, so +1 for that. $\endgroup$ – Ella Rose Mar 5 '18 at 22:08

My intuition would be no. Suppose we have an efficient solver for modular AGCD, let's call it $\mathcal{A}$. Given some samples $p_1, p_2, ... p_j$ with $p_i = pq_i + e_i \bmod{x}$ we can use $\mathcal{A}(p_1, p_2, ... p_j, x)$ to recover $p$.

This implies that there is an efficient solver for AGCD, let's call it $\mathcal{B}$. We can construct $\mathcal{B}$ from $\mathcal{A}$. Given some samples $p_1, p_2, ... p_x$ with $p_i = pq_i + e_i$ we can define $\mathcal{B}(p_1, p_2, ... p_j)$ as:

  1. randomly sample a random prime integer $x$
  2. use $\mathcal{A}(p_1, p_2, ... p_i, x)$ to give us $p \bmod{x}$.
  3. repeat steps 1 and 2 with different $x$, and then use CRT to combine the congruences to recover $p$.

If we assume that AGCD has no efficient solver $\mathcal{B}$, then this implies there can be no efficient solver $\mathcal{A}$ for modular AGCD (since $\mathcal{A}$ can be used to trivially construct $\mathcal{B}$). This implies modular AGCD is at least as hard as AGCD.


Here's a way you can adapt ideas from this paper


which will give you size restrictions on the $e_i, q_i$ which makes the problem hard. Suppose we know $x,a_i$ satisfy

$$a_i\equiv p(2^kq_i+1)+e_i \mod x,$$

where $q_i,e_i,p,x$ satisfy

$$|q_i|\le Q, \quad |e_i|\le E, \quad p, \ x\sim X$$

$Q,E$ are small with respect to $X$ and $k$ is some known integer. By shifting each $a_i$ by some $a_0$ we generate $a_i'$ of the form

$$a'_i\equiv p2^kq'_i+e_i' \mod{x}.$$


$$p'\equiv 2^kp \mod x, \quad |p'|\le x,$$

We will proceed assuming $p'$ is not small. This will hold with a large probability. Note this can be rewritten


For each $i$ consider the polynomials


The above setup implies each $P_i$ has a root $k_i,y_i$

$$P_i(k_i,y_i)\equiv 0 \mod{p'}, \quad |k_i|\le 2Q, |y_i|\le 2E.$$

Now proceed as in Section 2 of the above mentioned paper. Multiply powers of $P_i(k_i,y_i)^{e_i},$ together to generate a number of polynomials $Q$ satisfying

$$Q(k_1,y_1,\dots,k_r,y_r)\equiv 0 \mod{p'^{M}},$$

for some large $M$ with $k_1,y_1,\dots,k_r,y_r$ small. Lattice reduction then gives a number of polynomials with small coefficients with the same root modulo $p'^{M}$ and hence a root over the integers. Finding this root allows recovery of $p'$ and hence $p$. It is possible to work out conditions on $Q,E$ which will make this possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.