|Previous||Table of Contents||Next|
Its story time with Joe Kilian :
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 Ill think up a random bit. Well then exclusive-or the two bits together, she suggested.
But what if one of us doesnt flip a coin at random? Bob asked.
It doesnt 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 moments 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 isnt 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, Alices 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 Bobs 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 cryptographers 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 , he solved it using a bit-commitment protocol:
In general, we need a protocol with these properties:
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:
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:
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:
|Previous||Table of Contents||Next|