Fair Coin No-Trust Protocol possible?

Question

Alice and Bob have divorced (Bob had an affair with Eve ). Now they quarrel about who gets the computer. They could throw a fair coin, but alas, they aren't at the same place. Neither do they trust each other or any mediator (otherwise they could both send a number to a third party, if the sum is even etc.).

Is there a no-trust protocol simulating a fair coin?

Answer 1

Yes, there is a no-trust protocol that simulates a fair coin flip. It's called the "Mental Poker" protocol, and it allows two parties to play a fair game of poker without revealing their cards to each other or a third party. Here's how it would work:

1. Alice and Bob agree on a large prime number, $p$ and a generator $g$ where $g$ is a primitive root modulo $p$.

2. Alice chooses a random secret number $a$ between $1$ and $p-1$ and sends Bob the value $A = g^a$ mod $p$.

3. Bob chooses a random secret number $b$ between $1$ and $p-1$ and sends Alice the value $B = g^b$ mod $p$.

4. Alice computes $K = B^a$ mod $p$.

5. Bob computes $K = A^b$ mod $p$.

Both Alice and Bob now have the same $K$, which is a shared secret. They can use $K$ to generate a random bit by computing $K$ mod $2$. If the result is $0$, they say the coin came up heads. If the result is $1$, they say the coin came up tails.

Answer 2

This is known as coin-flipping protocol.

Assuming parties are computationally bounded and there exists a collision-free hash function (function $h$ s.t. solving $h(a) = h(b), a \neq b$ is hard), there is a simple protocol: Alice generates a random bit $x_a$ as well as long random string $y_a$, and sends hash of $y_a\#x_a$ to Bob, Bob similarly sends hash of $y_b\#x_b$ to Alice. Then they reveal $x$ and $y$ to each other, check that everything was correct, and say that final answer is $y_a \oplus y_b$. If at least one of them was honest, the final result will be fair.

In case of computationally unbounded parties, we can't guarantee perfect fairness - best we can do with $r$ rounds of communication is $O(1 / r)$ bias, see "An optimally fair coin toss" by Moran, Naor, Segev.

Answer 3

A standard number theoretic approach:

$A$ selects two large primes ($p,q$) without revealing them. $A$ computes $N=pq$ and passes $N$ to $B$.

$B$ chooses an integer $0<m<N$, computes $m^2\pmod N$ and passes that to $A$.

$A$ extracts all $4$ square roots of $m^2\pmod N$. Here one is to imagine that $p,q$ are chosen to be of a scale where it is possible to do that, while $N$ is too large. Of course the square roots come in pairs, $\pm a, \pm b$.

$A$ then guesses which of those pairs $B$ used and passes the guess on to $B$. If $A$ is correct, $A$ wins. If $A$ is wrong, $B$ wins and $B$ can prove it by (easily) factoring $N$. That's a quick exercise given all the square, see, e.g., this question.

Note: It is possible for $B$ to "cheat" by pretending that $A$ guessed correctly even if $A$ was wrong. Of course, that's not the form of cheating people are generally worried about.