Flipping Coins over the Telephone

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

  1. 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.

  2. 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.

  3. 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.

  4. 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:

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: