Fair Coin Flip

Many ages ago I owned and operated the site electronicliberty.com with a friend.  Below is a somewhat comical article we wrote on Fair Coin Flip that existed on that site.  It first existed as a group research paper we were suppose to write in the TSM program at MSU and we decided to gamble and submit it in story format.  Our professor said we should have failed for not following directions, but it was too good so he gave us a “B”.    I thought I would open up the time capsule and share some  of these oldies but goodies.  It is also available on the WaybackMachine.

The Fair Coin Flip encryption protocol was designed to allow two untrusted parties to communicate with each other in a secure and “trustworthy” manner. This article demonstrates the protocol step by step in an entertaining story format.

Fair Coin Flip

It all started one evening when two students were on the phone debating how they should write a paper on the Fair Coin Flip protocol.
Derek being the more responsible of the two suggested that they immediately convene to a writing conducive environment and write the paper together. Craig suggested an alternative, he would go to sleep and Derek would write the paper. Derek being a quick witted fellow soon realized that this proposal was not fair. However, he was intrigued at the idea of only one person writing the paper, because he had other things he wanted to do as well. After a short pause in the conversation Derek suggested that they flip a coin to decide who would be the unlucky student to write the paper.
Craig was also intrigued by this proposition because he was of a gambling persuasion and did not mind letting the dice fly. Taking initiative Craig exclaimed, “That sounds wonderful, I have a coin right here. Call it in the air.” Derek yelled into the phone, “Tails.”

The coin landed and Craig quickly stated that he was sorry but the coin had indeed landed on Heads and that he was going to bed. Derek was somewhat flustered at the recent events, but collected himself and began on the daunting task of writing a paper about Fair Coin Flips.

One page into writing the paper on Fair Coin Flips, Derek came to the realization that based on the information he had read there was a possibility that the process that had taken place earlier over the phone may not have been fair. He trusted Craig and did not question that then, but now he realized that Craig’s desire to go to sleep could have persuaded him to lie. Derek also realized that there was nothing in the previous protocol that ensured him that the flip was random and fair. Although, Craig was a trusted friend there was the possibility that he had cheated and that he should be the one doing the paper. Once again Derek contacted Craig. Craig answered his phone, and inquired as to why Derek was ruining his sleep. Derek quickly explained his doubts as to whether or not the events that had taken place earlier had been fair and that they needed to redo the coin flip. Craig was not at all happy about this proposition, but did feel somewhat guilty because he had in fact cheated on the coin toss. Since Craig had not done any research about the Fair Coin Flip Derek took it upon himself to describe the problem that presented itself.

Derek and Craig had come across a common problem. How could they flip a coin over the phone and make it fair? M. Blum was also fascinated with this same problem. He realized that there must be something in place to make the result random even if one of the parties cheated. He believed that this process could be solved with the Exclusive Or process. Now we go back to the story.

Craig was quite perplexed and not entirely focused on what was going on, but he agreed that in the spirit of fairness that they should come up with a solution that left both parties satisfied that the coin flip was fair. Derek presented a new solution to provide them with a fair coin flip. Derek said, “Craig, do you remember a few weeks ago when we did the lab report over ‘Exclusive Or’.” Craig vaguely remembered the process and Derek quickly updated him on how they would use the Exclusive Or process to make the coin flip fair. He helped Craig remember that Exclusive Or was based on alternate bits. They would be easily applicable to a coin since heads and tails could be represented by alternate bits (0 and 1). He quickly refreshed Craig on how the Exclusive Or process calculations were made by showing the four different combinations of two alternate bits. The total combinations are easily calculated by taking the number of possibilities and raising it to a power equal to the sample size. The Exclusive Or operation applies to two bits. Each bit has two possibilities. This means that the total possibilities is 2^2 which is equal to 4. The Exclusive Or operations then result as follows.

The Exclusive Or process works like this:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

As stated before, by M. Blum, in the article, “Coin Flipping By Telephone: A Protocol for Solving Impossible Problems”, in the proceedings of the 24th IEEE computer conference, published in 1982, presented a simple protocol for coin flips ( http://www.disappearing-inc.com/F/faircointoss.html ). Blum’s protocol was highly recognized and was used in networking protocols to determine which party would complete which side of the handshake. This was the same protocol that Derek intended to use. Derek proposed that each of them would flip a coin at the same time while on the phone. After they had flipped the coins they would take the results of the flips and XOR them. The outcome of this process would represent the fair coin flip result. Derek quickly made things simple by saying that Heads would be equal to one and that Tails would be equal to 0. Craig pondered over Derek’s proposal and decided to put it to a test. After all, if one of them truly gave a random answer then the outcome of the XOR would be truly random and thus fair. They also agreed that after the XOR process that a result of 1 would mean that Craig would have to do the paper and a final result of 0 would mean that Derek would have to do the paper.

Derek and Craig each procured a coin and flipped them simultaneously. Derek quickly asked Craig what result he had. Craig responded that he had indeed flipped Tails. Derek told Craig that the result of his coin flip had been Heads and therefore after doing the XOR process it meant that Craig was now going to have to do the paper.

To make certain that the process had indeed been legitimate Craig wrote out the process mathematically.

Heads = 1 = Derek Sleeps
Tails = 0 = Craig Sleeps

Craig’s Flip = Tails = 0
Derek’s Flip = Heads = 1
XOR = 1
After seeing that the math was correct Craig realized that he was now going to have to write the paper. He turned on his computer and downloaded the portion of the paper that Derek had done and started writing.

After adding two more pages to the previous page that Derek had written, Craig realized that there was a significant flaw in the protocol that they had followed for the second coin flip. Craig immediately realized that his night of sleep could have been unfairly taken away from him due to Derek’s previous knowledge of the flaw. After all, Derek did seem strangely excited to put the paper off on Craig and sleep. So once again Craig called Derek and explained his discontent with the previous protocol that they had followed. Craig explained that they needed a secure system that fulfilled the criteria set forth by Manuel Blum, outlined as the following:

1) Craig must make the coin flip before Derek makes his guess.
2) Craig must not be able to change his answer after hearing Derek’s guess.
3) Derek must not be able to know the result of the coin flip before he makes his guess.

So once again they needed to find a system that would result in a fair coin flip for both of them. Derek formulated a revised fair coin flip protocol that incorporated the one way hash program that they had written previously. The idea for the protocol came from an articled he had read by Joe Kilian titled, “Uses of Randomness in Algorithms and Protocols”, from MIT press in 1990. Kilian realized that there had to be something truly random in the protocol in order for the outcome to be completely fair. Derek used this theory of randomness coupled with a one way hash function. This protocol would require these things:

1. Derek would choose a number at random between -infinity and infinity (which equals R), assuming that the number was totally random.
2. Derek would then put the number (R) into the one way hash generator (F) and send the result to Craig (Y).
3. Craig would then decide whether or not he thought the random number was even or odd. Thus, giving him a 50/50 chance at guessing the right number. The same chances of a fair coin flip.
4. Derek would then send the result of the coin flip to Craig.
5. Derek would also send the random number (R) to Craig.
6. Craig would then input the random number into the one way hash and see if his guess was correct and be assured that the process was done fairly.
Craig agreed that this protocol seemed secure, but learning from the two previous experiences opted to find out the flaws, if any, before they put the protocol into practice. He came up with these flaws:

1) If the one way hash generator could have two inputs that resulted in the same hash it would be possible for Derek to send that hash to him and then pick whichever input would result in his best interest after Craig had sent his guess to Derek. Derek will then be able to cheat Craig all of the time.
2) If the one way hash generator’s result has any correlation with the input and Craig is aware of this flaw, his probability of guessing the number increases beyond 50/50 thus, resulting in an unfair coin flip. Craig will be able to cheat Derek some of the time.

Ex) Suppose that experimentation shows that when an odd number is put into a given hash it will generate an even numbered hash more often than an odd number hash. This means that when an even numbered hash result is sent, the recipient knows that the input was probably odd and thus increases his chances of guessing correctly. We know that a his chances should be 50% if all is truly fair, but since his chances have increased we know that he can cheat the sender based on odds. He will not be able to guess correctly every time, but having knowledge of correlation between an input and the corresponding hash does create an advantage.

Craig realized that if either of them were capable of finding two inputs that would result in the same hash, or finding the correlation between the input and the corresponding hash that they would not need to do this research paper and therefore it was very likely that a fair coin flip would result. He was confident that the knowledge it would take to exploit these flaws was beyond their current capacity, but Craig set forth to find a solution that was flawless. After all eight hours of sleep was at stake. Craig proposed that they incorporate the use of PGP (Pretty Good Privacy). He had also read the article by Kilian and understood that by using keys they could eliminate one of the party’s ability to make his decision based on the others party’s decision. He decided that they must follow these guidelines:

1. Derek will generate two messages one that contains a Heads and a random number value (M1) and one that contains a Tails value and a random number (M2). Derek will then encrypt (Ed) each message using his public key (provided by PGP) and send both to Craig.
2. Craig will then choose one of the messages at random and encrypt (Ec) his answer with his public key (provided by PGP) and send it to Derek.
3. Derek will then decrypt (Dd) his public key encryption with his private key and send that back to Craig.
4. Craig can then decrypt (Dc) using his public key encryption with his private key and see the result.
5. Craig then sends the result back to Derek and he can verify that the message is equal to one of the two messages that he sent initially.
6. Craig and Derek then reveal their private keys to each other to assure that there was no cheating.
Derek thought that the system was very secure and the only flaw with this protocol would be if either party knew the other’s private key. He explained these flaws as follows:

1. If Craig knew Derek’s private key prior to making his guess, Craig would be able to decrypt the messages and then chose the one that best suited his desires. He would then re-encrypt it with Derek’s public key (which everyone has access to) and then encrypts it with his own private key. Craig has cheated the system and Derek will never know.
2. If Derek knew Craig’s public key prior to sending the messages he could force Craig into choosing whichever value he wanted. For instance, if he wanted Craig to chose Heads he would send both messages as Tails from the beginning. Craig would then chose at random and send his answer back to Derek. Derek would then decrypt the answer with Craig’s private key and his own to reveal the original message. He then changes Tails to Heads and encrypts it with Craig’s public key and sends it back. Derek has cheated the system and Craig will never know.
Derek did not think that it was very probable that Craig had acquired his Private Key, nor did Craig think that Derek had his Private Key. Therefore they both decided that this would be a totally secure and fair way to decide who should write the paper. Before they flipped the coin they both realized that throughout the arduous process of trying to decide who would be left to write the paper on the fair coin flip, they had indeed acquired all of the information necessary to write a stellar paper.

Now we will recap the events that took place during Derek and Craig’s expedition to achieving the fair coin flip from remote locations. This can be done using XOR, One way Hash functions, or Public-Key Private-Key Cryptography. With XOR we realized that there were many flaws when only using two parties (Craig and Derek). This was because one of the participants could make their decision based on their knowledge of the other participants answer. This problem could have been resolved by having a trusted third party in the middle to hold the answers, concealing them from both parties. Then this trusted third party could use the XOR process and then produce the fair results. Assuming that there are only two parties available then the one way hash or public-key private-key cryptography would have to suffice.

The one way hash and public-key private-key protocols do have some flaws, but the chances of someone being able to exploit these flaws are minuscule. Therefore, each of these methods can be considered a secure way to perform a fair coin flip from remote locations between two parties. The idea of a fair coin flip gave way to a new method of security and it has evolved into a newer method that expands the fair coin flip into a multi party conversation. The end result being Mental Poker.

When Blum came up with the idea for fair coin flipping he actually developed a new thought process to approach network security. This thought process is what allows un-trusted parties to develop a line of communication without a bias. The analogy of the coin flip done while all parties are physically present is the perfect state of fairness and randomness at work. Therefore, it was necessary to develop a protocol that could produce this same amount of fairness and randomness without the need for both parties to witness it. Using the one way hash and public-key/private-key methods it is not necessary for either participant to trust the other because the protocol erases the need for trust. In effect, producing the same amount of fairness that is necessary to do a real-time coin flip. In conclusion: the fair coin flip thought process can be applied to anything and is necessary for developing successful protocols that deal with the issues of trust.

Schneier, Bruce. Applied Cryptography New York John Wile and Sons Inc. 1996
http://www.disappearing-inc.com/F/faircointoss.html February 20, 2004


2 thoughts on “Fair Coin Flip

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s