<p><strong>Background:</strong> There is a well known argument (due to <a href="http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf" rel="noreferrer">Rabin</a>) that demonstrates that if one has access to an machine that computes square roots of elements in <span class="math-container">$\mathbb{Z}_n$</span>, with <span class="math-container">$n = pq$</span>, then <span class="math-container">$n$</span> can be factored efficiently. The algorithm proceeds as follows:</p>

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

<p>This does not work if <span class="math-container">$B$</span> has access the coins you flipped to draw <span class="math-container">$y$</span>, since it could just return <span class="math-container">$y$</span>.</p>

<p><strong>Question:</strong> Is there a different protocol that also works if your coins must be public?</p>

<p><strong>Thoughts:</strong> </p>

<ul>
<li>This is superficially similar to <span class="math-container">$IP[k] \subset AM[k+2]$</span>, 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 <span class="math-container">$B$</span>. The ideas used there could still be useful.</li>
<li>I don't think that asking for the square roots of a random set of residues in <span class="math-container">$\mathbb{Z}_n^*$</span> would be useful, since I can simulate this (if adversarial <span class="math-container">$B$</span> gives a random square root) by sampling random <span class="math-container">$x \in \mathbb{Z}_n^*$</span> and squaring them.</li>
<li>Perhaps there is a efficiently computable set of quadratic residues whose square roots would provide important information about <span class="math-container">$n$</span>? </li>
</ul>

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

CC BY-SA 4.0
2020-02-13T06:45:51.277Z
Can $B$ perform unlimited amounts of computation, or is it limited to something that's implementable in polytime given the factors of $n$?
D.W.
CC BY-SA 4.0
2020-02-13T08:44:51.533Z
I ran into the same issue in https://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).
Emil Jeřábek
CC BY-SA 4.0
2020-02-13T14:19:08.210Z
@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.
Elle Najt
CC BY-SA 4.0
2020-02-14T12:10:57.450Z
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.
Geoffrey Irving
CC BY-SA 4.0
2020-02-14T13:12:57.847Z
Oops, that doesn’t work, since the adversary can run the encrypted circuit before giving you their square root.
Geoffrey Irving
<interactive-proofs><comp-number-theory>
Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?
Elle Najt
# Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?

(Asked by: username_0 on 2020-02-12)

**Background:** There is a well known argument (due to [Rabin](http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf)) 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?

**Thoughts:**

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

**Tags:** interactive-proofs, comp-number-theory
> **Comments:**
> **username_1**: Can $B$ perform unlimited amounts of computation, or is it limited to something that's implementable in polytime given the factors of $n$?  
> **username_2**: I ran into the same issue in https://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).  
> **username_0**: @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.  
> **username_3**: 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.  
> **username_3**: Oops, that doesn’t work, since the adversary can run the encrypted circuit before giving you their square root.  

---

## 0 answers

