Coin flipping

Alice and Bob want to flip a coin (by telephone in Manuel Blum's 1981 paper) to decide who wins (in Blum's paper, who gets the car after a divorce).

Actually, each one flips a coin and if the came out equal (two heada or two tails) Bob wins.

How can this be done fairly and withou cheating when the two are far apart?.

Using computers: square roots of quadratic residues!

1. One of the two, say Bob, selects two large random primes $p$ and $q$ of the form $4k+3$ (Blum primes!) and then computes $n= pq$. He then sends $n$ to Alice.

2. Alice chooses a random $b$ and sends $a = b² mod n$ to Bob.

3. Bob computes the 4 square roots $\pm x$ and $\pm y$ of $a$, chooses one of them, let us call it $r$, and sends it to Alice.

4. Alice checks if $\pm r = b$. If so, then Bob wins. If not, he loses.

5. Alice proves her claim by disclosing $b$. (Observe that if Alice does not like the outcome she may simply do not finish the execution of this protocol, but that would be cheating)

To flip $m$ coins, do step 2. $m$ times, then step 3. $m$ times and so on. It has to be done in this way because as soon as Alice receives the square roots from Bob she will likely be able to factor $n$ (and so be able to change her choice of the $b$).