Using Blum’s Protocol
Previously, we implemented a fair coin toss on Bitcoin using XOR. We introduce an alternative way of implementing it using Blum’s original coin tossing protocol¹.
It consists of the following steps:
- Alice chooses prime numbers p and q. He tells Bob N = p * q. Alice chooses p and q to be extremely large so that Bob cannot feasibly find them from N.
- Bob chooses x between 0 and N. He calculates b = x² mod N. He tells Alice b. This step is similar to calling the outcome before a coin toss; you pick an outcome and commit to it.²
- Alice calculates the four square roots of b modulo N. These are x, y, -x and -y. He chooses one of the pairs {x,-x} or {y,-y}, and tells it to Bob. This step corresponds to the physical flipping of the coin.
- If Alice chooses {x,-x}, Bob wins, and he proves it easily by telling Alice x, which he would not have been able to find unless he chose it in step 2, since he does not know p and q.
- If Alice chooses {y,-y}, then she wins. Bob cannot find y, so he cannot trick Alice by telling her y.
[1] Coin Flipping by Telephone: A Protocol for Solving Impossible Problems. Blum (CRYPTO 1981).
[2] x and N have to be coprime to ensure 4 square roots.
