| | |
The equivalence (in a computational sense) of factoring $n$ and finding four distinct square roots of some $y\pmod{n}$ gives us a way to fairly flip a coin over the telephone. The following describes how this is done.
The important thing to remember as one reads what is below, is that all of the calculations and verifications described can be computed quickly, even when the values of the variables are very large (as they involve things like finding the greatest common divisor via the Euclidean Algorithm, finding large powers via successive squares, etc.).
Alice chooses two large random primes $p$ and $q$, both congruent to $3\pmod{4}$, sending only $n$, the value of their product, to Bob. The values of $p$ and $q$ she keeps secret.
Bob chooses a random integer $x$ and computes $y \equiv x^2\pmod{n}$. He sends the value of $y$ to Alice, but keeps $x$ secret.
Alice uses her knowledge of $p$ and $q$ to find the four square roots of $y$: $\pm a, \pm b$. She knows $x$ must be one of them, but as they all have a square of $y$ she is unable to determine which one. So she picks one at random (perhaps via the toss of a coin), and sends this square root to Bob.
Without loss of generality, suppose Bob had originally chosen $x = a$. He of course realizes that both $\pm a$ solve $x^2 \equiv y\pmod{p}$.
We now have two cases:
If Alice sends $\pm b$, Bob now knows all four roots to $x^2 \equiv y\pmod{n}$: $\pm a, \pm b$. He can use these four values to factor $n$ quickly. If this situation happens, we say Bob has won the toss -- a point that Alice can confirm provided Bob sends the values of $p$ and $q$ to Alice for verification.
If Alice sends $\pm a$, Bob hasn't gained any additional information, and so factoring $n$ remains difficult. In this case, we say Bob has lost.
It is clear that since Bob is sending $p$ and $q$ to Alice to verify that he did indeed have a factorization of $n$, that he can't lie about that to win the coin toss. However, one might wonder if there are other ways that either Bob or Alice might try to lie or sabotage the scenario to unfairly win the toss:
Alice might send an $n$ that is not the product of two distinct primes.
Bob can protect against Alice giving him a prime $n$ by testing a sufficient number of randomly chosen powers from $2^{n-1}, 3^{n-1}, 5^{n-1}, \ldots \pmod{n}$ until he finds one that does not equal $1$ (and is thus a Fermat witness). Finding such a witness guarantees $n$ has at least $2$ factors.
If $n$ is the product of $3$ or more primes, then the chances that Alice sends Bob the information he needs to factor $n$ (and thus win the toss) actually increases. To see this, note that if $n$ is the product of $3$ primes, then the various combinations of congruences involved in using the Chinese Remainder Theorem produce $8$ square roots. Thus, Alice has a $3/4$ chance of giving Bob the information he needs to win.Suppose Bob sends some $y$ to Alice that has no square root. Alice will, of course, discover this in the course of calculating all $4$ square roots of $y$ using the prime factorization of $n$. (i.e., She won't be able to produce any roots at all.)
It would be equally foolish for Bob to send some random $y$, as then -- no matter what Alice sends him -- he won't have enough information to factor $n$. Remember, he needs $4$ distinct square roots total to do this, and in the best case he only gets two from Alice.
Suppose Alice tries to cheat by sending Bob some random number rather than a square root of $y$. Surely this would prevent Bob from gaining the information he needs to factor $n$. However, Bob can trivially check this by squaring the value Alice sends him to make sure it yields $y$.