How to perform a fair coin toss experiment over phone?

Here's one way to do it. Let's call the two parties Alice and Bob (as is popular to do in cryptography and theoretical computer science more broadly these days).

Alice and Bob agree on a secure hash function $h$. Alice chooses a random string $r_A$ and Bob chooses a random string $r_B$. Bob tells Alice $r_B$.

Now, Alice flips a coin, call the result $x$. Alice sends $h(x,r_A,r_B)$ to Bob and asks Bob to call the toss. Let's say Bob calls $y$. Then Alice tells Bob $(x,r_A)$ and he can verify himself that $x = y$ by checking that $h(x,r_A,r_B) = h(y,r_A,r_B)$. In this way if Bob called it wrong, then Alice can prove that he was wrong.

Obviously, if Bob calls the coin flip correctly, then the two hashes match. Moreover, it's extremely hard for Alice to cheat because if Bob says "tails" for example when the coin toss was indeed "tails" but Alice wants to trick him into thinking it was "heads", she'd have to come up with a random string $r$ such that $h(H,r,r_B) = h(T,r_A,r_B)$, which is hard by the assumption that $h$ is a secure hash function and the fact that Bob chose $r_B$. Essentially, the purpose of $r_A$ and $h$ are to make Alice "commit" to her initial toss $x$. The point of $r_B$ is so that, without it, Alice might pick some $r_A$ for which she knows another string $r$ which might let her lie.

This was answered by Manuel Blum in 1983.

http://dl.acm.org/citation.cfm?id=1008911

Blum proposed a scheme that is similar in security to RSA.

Edit: Here is a summary of Blum's approach.

1. Alice chooses two large prime numbers $p$ and $q$, with the property $p \equiv 3 \mod 4$ and $q \equiv 3 \mod 4$. She computes the number $n = pq$ and reads it to Bob over the phone. She keeps the numbers $p$ and $q$ secret.

2. Bob chooses a random integer $x$ between $1$ and $n$. He computes the square $a = x^2 \mod n$ and reads it to Alice over the phone. He keeps the number $x$ secret.

3. Since Alice knows the factorization of n, she can compute the square roots of $a$ modulo $n$. There are four such square roots, let's say $x$ and $n-x$ and $x'$ and $n-x'$. Alice can compute them all, but she does not know which number Bob has chosen. Alice chooses one of these square roots and reads it to Bob over the phone.

4. Bob compares the number read to him over the phone to the number that he chose. If Alice communicated the number $x$ or $n-x$, he says to Alice "you win, but you must now tell me the factors $p$ and $q$". Then Alice reads the factors $p$ and $q$ to him over the phone, and Bob can check that they are both prime numbers and that $n = pq$. The game is over, and Alice has won.

5. If Alice communicated the number $x'$ or $n-x'$, Bob can use this information and the fact that he knows the other square root, namely $x$, to find the factors of $n$. He does this, and he says to Alice "you lose, here are your factors". The game is over, and Bob has won.

One person imagines a number $x$, computes its hash, and speaks that hash into the telephone, promising that the value of $x$ to be revealed later hashes to the spoken hash. The other person then calls the shot, which is a bit. Then the first person reveals $x$, the second verifies that its hash corresponds to what was heard over the telephone, and if the lowest bit of $x$ matches the shot then the coin is HEADS; otherwise the coin is TAILS.