4.10 Fair Coin Flips

It’s story time with Joe Kilian [831]:

Alice and Bob wanted to flip a fair coin, but had no physical coin to flip. Alice offered a simple way of flipping a fair coin mentally.

“First, you think up a random bit, then I’ll think up a random bit. We’ll then exclusive-or the two bits together, ” she suggested.

“But what if one of us doesn’t flip a coin at random?” Bob asked.

“It doesn’t matter. As long as one of the bits is truly random, the exclusive-or of the bits should be truly random, ” Alice replied, and after a moment’s reflection, Bob agreed.

A short while later, Alice and Bob happened upon a book on artificial intelligence, lying abandoned by the roadside. A good citizen, Alice said, “One of us must pick this book up and find a suitable waste receptacle.” Bob agreed, and suggested they use their coin-flipping protocol to determine who would have to throw the book away.

“If the final bit is a 0, then you will pick the book up, and if it is a 1, then I will, ” said Alice. “What is your bit?”

Bob replied, “1.”

“Why, so is mine, ” said Alice, slyly, “I guess this isn’t your lucky day.”

Needless to say, this coin-flipping protocol had a serious bug. While it is true that a truly random bit, x, exclusive-ORed with any independently distributed bit, y, will yield a truly random bit, Alice’s protocol did not ensure that the two bits were distributed independently. In fact, it is not hard to verify that no mental protocol can allow two infinitely powerful parties to flip a fair coin. Alice and Bob were in trouble until they received a letter from an obscure graduate student in cryptography. The information in the letter was too theoretical to be of any earthly use to anyone, but the envelope the letter came in was extremely handy.

The next time Alice and Bob wished to flip a coin, they played a modified version of the original protocol. First, Bob decided on a bit, but instead of announcing it immediately, he wrote it down on a piece of paper and placed the paper in the envelope. Next, Alice announced her bit. Finally, Alice and Bob took Bob’s bit out of the envelope and computed the random bit. This bit was indeed truly random whenever at least one of them played honestly. Alice and Bob had a working protocol, the cryptographer’s dream of social relevance was fulfilled, and they all lived happily ever after.

Those envelopes sound a lot like bit-commitment blobs. When Manuel Blum introduced the problem of flipping a fair coin over a modem [194], he solved it using a bit-commitment protocol:

(1)  Alice commits to a random bit, using any of the bit-commitment schemes listed in Section 4.9.

(2)  Bob tries to guess the bit.

(3)  Alice reveals the bit to Bob. Bob wins the flip if he correctly guessed the bit.

In general, we need a protocol with these properties:

—  Alice must flip the coin before Bob guesses.

—  Alice must not be able to re-flip the coin after hearing Bob’s guess.

—  Bob must not be able to know how the coin landed before making his guess.

There are several ways in which we can do this.

Coin Flipping Using One-Way Functions

If Alice and Bob can agree on a one-way function, this protocol is simple:

(1)  Alice chooses a random number, x. She computes y = f(x), where f(x) is the one-way function.

(2)  Alice sends y to Bob.

(3)  Bob guesses whether x is even or odd and sends his guess to Alice.

(4)  If Bob’s guess is correct, the result of the coin flip is heads. If Bob’s guess is incorrect, the result of the coin flip is tails. Alice announces the result of the coin flip and sends x to Bob.

(5)  Bob confirms that y = f(x).

The security of this protocol rests in the one-way function. If Alice can find x and x´, such that x is even and x´ is odd, and y = f(x) = f(x´), then she can cheat Bob every time. The least significant bit of f(x) must also be uncorrelated with x. If not, Bob can cheat Alice at least some of the time. For example, if f(x) produces even numbers 75 percent of the time if x is even, Bob has an advantage. (Sometimes the least significant bit is not the best one to use in this application, because it can be easier to compute.)

Coin Flipping Using Public-Key Cryptography

This protocol works with either public-key cryptography or symmetric cryptography. The only requirement is that the algorithm commute. That is:

D_K1(E_K2(E_K1(M))) = E_K2(M)

In general, this property is not true for symmetric algorithms, but it is true for some public-key algorithms (RSA with identical moduli, for example). This is the protocol:

(1)  Alice and Bob each generate a public-key/private-key key pair.

(2)  Alice generates two messages, one indicating heads and the other indicating tails. These messages should contain some unique random string, so that she can verify their authenticity later in the protocol. Alice encrypts both messages with her public key and sends them to Bob in a random order.

E_A(M₁), E_A(M₂)

(3)  Bob, who cannot read either message, chooses one at random. (He can sing “eeny meeny miney moe, ” engage a malicious computer intent on subverting the protocol, or consult the I Ching—it doesn’t matter.) He encrypts it with his public key and sends it back to Alice.

E_B(E_A(M))

M is either M₁ or M₂.

(4)  Alice, who cannot read the message sent back to her, decrypts it with her private key and then sends it back to Bob.

D_A(E_B(E_A(M))) = E_B(M₁) if M = M₁, or

E_B(M₂) if M = M₂

(5)  Bob decrypts the message with his private key to reveal the result of the coin flip. He sends the decrypted message to Alice.

D_B(E_B(M₁)) = M₁ or D_B(E_B(M₂)) = M₂

(6)  Alice reads the result of the coin flip and verifies that the random string is correct.

(7)  Both Alice and Bob reveal their key pairs so that both can verify that the other did not cheat.