Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can be factored efficiently. The algorithm proceeds as follows:

Suppose that $B$ is a machine that returns a square root of any given square $a \in \mathbb{Z}_n$. $B$ may be adversarial and randomized, and is only constrained by the requirement that $B(a)^2 = a$ when $a \in \mathbb{Z}^*_n$ is a square. Then, provided one has private coins, you can interact with $B$ to factor $n$, by picking a uniformly random $y \in \mathbb{Z}_n^*$, and using the fact that with probability $1/2$, $\text{gcd}(B(y^2) + y, n) \in (1,n)$.$[2]$

This does not work if $B$ has access the coins you flipped to draw $y$, since it could just return $y$.

Question: Is there a different protocol that also works if your coins must be public?


  • This is superficially similar to $IP[k] \subset AM[k+2]$, but I don't think it is possible to reduce to this fact by using the decision problem version of factorization, since in that context the provers are much stronger than just polynomial time machines with access to $B$. The ideas used there could still be useful.
  • I don't think that asking for the square roots of a random set of residues in $\mathbb{Z}_n^*$ would be useful, since I can simulate this (if adversarial $B$ gives a random square root) by sampling random $x \in \mathbb{Z}_n^*$ and squaring them.
  • Perhaps there is a efficiently computable set of quadratic residues whose square roots would provide important information about $n$?

$[2]$: For completeness, the calculation follows from the observation that under the isomorphism $Z_n \cong Z_p \oplus Z_q$, the four square roots of $y^2$ are $(\pm x \mod p, \pm x \mod q)$, and from the point of $B$ $y$ could have been any of them. In two of the four cases for $y$, $x +y \in \{ (2x, 0), (0, 2x) \}$, so is either divisible by $p$ but not $q$, or vica versa. In both cases, we have that $x + y$ is not a multiple of $n$, and the gcd with $n$ is $\geq \min (p,q)$. ($p$ and $q$ are both odd.)

  • $\begingroup$ Can $B$ perform unlimited amounts of computation, or is it limited to something that's implementable in polytime given the factors of $n$? $\endgroup$ – D.W. Feb 13 '20 at 6:45
  • $\begingroup$ I ran into the same issue in arxiv.org/abs/1207.5220 . However, the solution in Lemma 3.3 is not applicable in your situation (while it uses the “adversarial” oracle model, the oracle more powerful: it solves a total search problem where the input data guarantee that a square root exists if the modulus is prime, and the oracle provides a factor of the modulus if a suitable square root doesn’t exist). $\endgroup$ – Emil Jeřábek Feb 13 '20 at 8:44
  • $\begingroup$ @D.W. All B can do is return square roots of what A queries, but do you mean how much power $B$ can use to decide the best adversarial strategy? Either formulation would be interesting to me -- this is just something I'm curious about, I don't have an application. $\endgroup$ – Lorenzo Najt Feb 13 '20 at 14:19
  • $\begingroup$ If the adversary is limited other than the ability to do square roots, one could try to generate $y$ inside a homomorphically encrypted circuit, producing both $y^2$ and an encrypted output that can be used to generate $y$ given a square root of $y^2$ as a key. I'm not sure if the details work, but this solution doesn't seem very satisfying even if they do. $\endgroup$ – Geoffrey Irving Feb 14 '20 at 12:10
  • $\begingroup$ Oops, that doesn’t work, since the adversary can run the encrypted circuit before giving you their square root. $\endgroup$ – Geoffrey Irving Feb 14 '20 at 13:12

Your Answer

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

Browse other questions tagged or ask your own question.