This demonstration is separated into different steps, some of which are animated with Java applets. If you decide to skip any step of the simulation, the applets you have skipped will automatically supply any required information if you use an applet further on.
Disclaimer: This demonstration contains strong technical language and explicit mathematics. While an effort has been made to censor out offensively mathematical terms, viewers' discretion is advised. If you feel uncomfortable with any term in this Web page, feel free to ignore it and just read the stuff written in normal English (you can look at the pictures too).
[Top] [Overview] [Background] [Bibliography]
This is a protocol for Bit Commitment (explained in the background page). Alice has a bit which she wants to keep secret from Bob for now. However, she intends to reveal it to Bob at some time in the future. At that point, Bob would like to be able to make sure that the bit Alice reveals to him is really the bit she has now. Hence, she must commit her bit to Bob in such a way that he cannot know what it is but she cannot change her mind between the moment that she commits it and the moment she reveals it.
In our situation, Alice and Bob are connected by two channels: a clear channel and a noisy one (a binary symmetric channel). The protocol presented here uses the uncertainty introduced by the channel to ensure that Alice's bit remains secret while not allowing her to change her mind.
[Top] [Overview] [Background] [Bibliography]
The essential idea of the protocol is as follows: Alice and Bob will agree on a random linear code of a fixed length n and also on a random n-bit boolean vector which we will call m. To commit her bit (we will call the secret bit b), Alice randomly picks a codeword xb such that xb · m = b. She then sends the word to Bob over the noisy channel.
Later, when she wants to reveal her bit, Alice announces the original codeword xb to Bob (over a clear channel - not the noisy one!). Bob can easily find out b by calculating xb · m. More formally, we have:
Protocol 1: Commiting Alice's bit
Protocol 2: Revealing Alice's bit
The test Bob applies is to count the number of positions in which xb and xb' differ, i.e the number of errors that occurred during transmission. Exactly how he uses that information and why it is significant is explained in the section Why Alice Can't Cheat.
[Top] [Overview] [Background] [Bibliography]
What follows is a detailed explanation of each step of the protocol which allows you to play around with the protocol and hopefully understand why it works so well.
[Top] [Overview] [Background] [Bibliography]
There are several parameters for this protocol. Chosen properly, they ensure that neither Alice nor Bob has a significant chance of being able to cheat. For more info, see the detailed analysis provided.
For this demonstration, there are only two important parameters:
The higher n is, the lower the chances are that the protocol will fail. Alice and Bob are free to choose n as large as they like, however they will pay a price: if n is very high, the protocol will take a long time to execute (for all you computer scientists out there: there are Omega(n) uses of the channel and Omega(n2) computational steps needed in the protocol). The good news is that the error probabilites decrease much more quickly than the execution time increases. Hence, arbitrarily small error probabilites are acheivable with reasonably small values of n.
For this demonstration, you can choose which values of p and n to use. Keep in mind that:
To set them, enter your values in the approriate fields below and click on the button marked "Set parameters". The applet will tell you if the values aren't appropriate. At any point in the demonstration, you can come back and reset them.
[Top] [Overview] [Background] [Bibliography]
Once Alice and Bob have agreed on the parameters for the simulation, the next step is to create an appropriate code. As it happens, picking a linear code at random provides a code whose minimum distance will be very good with high probability. See error-correcting codes for more information.
The dimension (see ECC) of the code required is calculated based on p and n. It is high enough so that Bob doesn't know too much about Alice's secret bit. What's more, the minimum distance will be high enough so that Alice can't change her mind once she has sent her codeword to Bob.
The applet below will let you pick a code at random. For those who like math, the applet will display the generator matrix at first, but you can also view the parity matrix by clicking on the appropriate button. The matrix is displayed as a bitmap where black pixels represent 1's and white pixels represent 0's.
Notice that the matrices always contain the identity matrix. This guarantees that the dimension of the code is high and allows fast calculation of the parity matrix.
Remark: Once Alice and Bob agree together on the dimension of the code, it should be Bob who generates it. If Alice generated it, she could intentionnaly give it a bad (i.e. small) minimum distance and thus make it too easy for her to cheat. See Why Alice can't cheat for more information.
[Top] [Overview] [Background] [Bibliography]
Once the code is generated and shared between Alice and Bob, Alice can commit her bit. She first chooses a random n-bit vector m. A quick check permits her to know whether this is a good choice of m. She then picks codewords at random until she finds one (called x in the applet below) for which x · m is equal to the bit in her head.
The applet below will let you do this.
The vectors are displayed using a bar code in which white bars represent 1's and black bars represent 0's. Each bar is one pixel wide.
[Top] [Overview] [Background] [Bibliography]
The last step in protocol 1 is to actually commit the secret bit by sending x over the noisy channel. The following applet will let you do this. Just click "Send X" to see what word x' Bob receives. Notice that the applet calculates the number of errors which occur during the transmission. This will be important when we come to the next stage: unveiling Alice's secret bit.
[Top] [Overview] [Background] [Bibliography]
We are now going to jump to the future - the moment at which Alice decides she wants to reveal (unveil) her up-till-now secret bit. She announces (over a clear channel - no noise) her codeword x to Bob. Bob then calculates the number of positions in which x and x' differ. He uses this to determine whether or not Alice is cheating.
If Alice is honest, we expect there to be about p * n errors. This is because each bit sent through the channel will be flipped with probability p. Because there are n bits sent, roughly p * n bits will be flipped. This is explained in more detail in the background page under the Law of Large Numbers. If we think of the number of differences between two words to be how "far" apart they are, Bob expects x to be somewhere near the circle of radius p * n centered around his word x'.
 |
| Bob expects Alice's codeword x to be on the blue circle |
|---|
Because of the Law of Large Numbers, the distance (number of errors) between x and x' will almost surely be near p * n. Hence, Bob will only believe Alice if the number of errors does not stray from its expected value by more than a certain threshhold (the exact value of which is determined by the parameters chosen at the beginning of protocol 1).
It is clear that if Alice is honest, she will almost surely pass the test. Why a dishonest Alice would fail is explained in the next section. For the moment, you can try running the unveiling procedure for an honest Alice by pressing on the "Unveil" button below.
Remark: Because in this demonstration n is relatively low, it is possible that Bob will refuse Alice's word, even though she's honest. This is because there is a chance that an exceptionally high number of errors occurred. Just go back to the previous applet and click "Send X" again. In a real situation, n would be high enough that the chances of this occurring would be very small.
This ends the explanation of the actual protocols. We will now look at why they are secure, i.e. why neither Alice nor Bob has a reasonable chance of cheating.
[Top] [Overview] [Background] [Bibliography]
When we use a bit commitment protocol, there are two kinds of treachery which we must guard against: we've got to make sure Alice cannot change her mind between the moment she commits and the moment she unveils (otherwise she never really committed to anything!) and we must ensure that Bob can't learn anything useful about Alice's secret bit until she unveils it to him. We look at both possibilities now.
[Top] [Overview] [Background] [Bibliography]
Let's say Alice is dishonest and would like to be able to change her mind about her committed bit. During the committing protocol (Part I), she sent a word x to Bob through the noisy channel. At unveiling time, she would like to convince Bob that she actually sent a different word y (from now on we will call y the fraudulent word). Remember that she never sees the word x' which Bob received - all Alice knows is that approximately p * n errors occurred. We can visualize the situation (explained in the background page): Alice expects x' to be somewhere on the red circle.
 |
 |
| The real situation | What Alice sees |
|---|
Conversely, Bob expects Alice's word to be within about p * n of his word x' (bottom left). Superimposing Alice and Bob's views gives the image on the bottom right.
|
 |
| What Bob sees | Superimposed views |
|---|
Bob will only believe Alice if the fraudulent word y is on the blue circle. But Alice doesn't know exactly where that blue circle is - only that its center x' is somewhere on the red circle. In fact, the only way she could pick y so that Bob will believe her is to pick her fraudulent word y very near to x, the word she originally sent.
This is where the use of a code comes in. Remember that Bob chose a code with a good minumum distance (see Step 2). In the drawing, the green circle shows where the nearest codewords to x are. The code guarantees that no two codewords are very close together (remember that "close" means that there aren't too many differences between the two words - click here for more info). It is thus impossible for Alice to choose y and be sure that Bob will believe her.
The picture is a little misleading, because it tries to flatten the situation into two dimensions. It turns out that when we work in n dimensions (remember the words in question have n bits in which to differ) the probability that Alice can will choose a good y is extremely small. See the error analysis for more details.
The following applet puts you in the shoes of dishonest Alice. Try cheating a few times to see how well you do!
[Top] [Overview] [Background] [Bibliography]
We must also guarantee that Bob cannot learn anything useful about Alice's secret bit from the word he received through the noisy channel (x'). To do this we use a technique called privacy amplification. The principle is simple: Bob knows a certain amount about Alice's codeword x which she sent to him through the binary symmetric channel. The information he has comes from two sources:
Click anywhere in this applet to have it calculate roughly how amny possibilities for x Bob has in our scenario:
What we see is that despite Bob's (significant) knowledge about x, he still does not know it exactly. It is that tiny bit of uncertainty that will be his downfall. This is where the use of the random vector m comes in. Scalar multiplication by m acts as a hash function, that is it assigns to each codeword a hash value - either 0 or 1 (in our case this is the value of x · m). Alice chose x so that its hash value was her secret bit. Over the whole code, exactly half of the codewords will hash to 0 and the other half to 1. Privacy amplification guarantees us that on average this will also be true of the codewords which Bob has left as possibilities, i.e. roughly one half of them will hash to 0 and the other half to 1. This means that Bob's chances of having any really useful information are very slim.
Another way to picture privacy amplification is to see the hash function (the random vector m) as somehow "distilling" Bob's uncertainty. It takes his relatively small uncertainty about x and distills from it more "concentrated" uncertainty about the hash value of x. This process is illustrated below.
The end result of all this is that Bob's chances of being able to learn much about Alice's secret bit before she unveils it are very small. This means that over all, the protocol is secure.
The security of this protocol rests on the properties of the binary symmetric channel. If the channel isn't really a perfect binary symmetric channel or if one of the players knows a better approximation of the real error probability than does the other, cheating is possible. The best implementations of a BSC would hence be based on phenomena too complex to control or even predict, such as weather patterns. In fact, in a recent cryptographic key distribution scheme based on noisy channels the author suggested using satellite transmissions through the atmosphere to emulate a binary symmtric channel. However, no such implementations yet exist.