Secure Coin Tossing

By David Phillips

June 4, 2009

We have two (very bored) people named Alice and Bob who are in geographically different places and talking to each other on the phone. 

They decide to amuse themselves by playing a coin flipping game where one of them flips a coin and the other guesses which side of the coin lands it lands on.  Alice decides to flip the coin first and does so.  Bob makes his choice of “heads” or “tails”.  Alice tells Bob whether or not he got it right.  If Bob gets calls it correctly then he scores a point, otherwise, Alice gets the point.

This system works great when everybody is honest.  What if Alice is not honest?  Bob is not physically present to see which side the coin actually lands on.  It would be trivially easy for Alice to lie whenever Bob gets it right and steal Bob’s points.

We need a system that ensures fairness such that nobody can cheat.  We can solve this problem using cryptographic primitives in the following ways:

Solution 1)                    

Alice picks a string S at random from the set {“HEADS”, “TAILS”}.

                        Alice generates a random integer to use as an encryption key K.

                        Alice encrypts S using K to produce some garbled cipher text C as follows:

                        C = E(S, K)

Where E is some encryption algorithm and C is the cipher text produced by encrypting s with the key K.

Alice sends C to Bob.  To Bob, C is just some meaningless garbled text.  However, it proves that Alice has committed to some result of the coin flip which she cannot change after Bob makes his guess.

Bob chooses string G from the set {“HEADS”, “TAILS”} and sends it to Alice .

Bob decrypts C using K as follows:

S = D(C,K)

Where D is some decryption algorithm and C is the cipher text produced by encrypting S with the key K.

Bob compares S (Alice's decrypted commiteed result) to G (Bob's guess) to confirm whether or not he won the coin toss.

Solution 2 BAD)

Alice generates a random number R.

                        Alice generates a random key K.

                        Alice encrypts R using K to produce C as follows:

                        C = E(R, K)

Where E is some encryption algorithm and C is the cipher text produced by encrypting R with the key K.

Alice sends C to Bob.

Bob guesses G as “even” or “odd” and sends it to Alice .

Alice sends K to Bob.

Bob decrypts C using K as follows:

R = D(C,K)

Where D is some decryption algorithm and C is the cipher text produced by encrypting R with the key K.

Bob compares R to G to confirm whether or not he won the coin toss.

Alice can cheat this algorithm by doing the following:

Alice generates 2 values e, o where e is even and o is odd.

Alice carefully selects 2 keys K1, K2 such that

E(e, K1) = C

E(o, K2 ) = C

Where E is some encryption algorithm and C is the cipher text produced by encrypting e, o with one of the keys K1, K2 .

Alice sends C to Bob.

Bob guesses G as “even” or “odd” and sends it to Alice .

Alice examines G.

If G is “even”, then Alice sends Bob K2 and Bob finds the o upon decrypting his C with K2 .

If G is “odd”, then Alice sends Bob K1 and Bob finds the e upon decrypting his C with K1.

Solution 3)

                        Alice generates a random number r.

                        Alice computes the hash of r as follows:

                                    h = H(r)

Where h is the hash value produced by hashing algorithm H with input r.

                        Alice sends h to Bob.

                        Bob guesses G as “even” or “odd” and sends it to Alice .

                        Alice sends r to Bob.

                        Bob hashes r and verifies that the result matches h as follows:

                                    h” = H(r)

                                    assert(h” = = h)

The reason Alice can cheat using the encryption scheme is because it is trivially easy to find two unique values that map to the same cipher text using two different keys.  For example, if Alice randomly picks e, K1 and computes C = E(e,K1) then she can trivially calculate another number o that will encrypt to the same cipher text C under a different key K2 by calculating o = D(C, K2 ).  Alice just has to keep trying different even numbers for e until she finds an odd o which she should have a 50% chance of achieving on each try so she should be able to find an even/odd pair fairly quickly.

The advantage of using the hashing scheme is that it is very difficult to find two input values that map to the same hash value as hash functions are designed to be collision resistant.  In order for Alice to successfully cheat the hash scheme, she would have to find an even and odd number that both map to the same hash value which could take a very long time and in practice is not a feasible action for Alice to attempt.  Therefore, the hashing scheme provides better protection to this kind of problem.