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.

- The Situation
- Description of the Protocol
- Part I: Committing Alice's Secret Bit
- Step 1: Choosing the protocol parameters
- Step 2:Picking a Random Linear Code
- Steps 3,4,5: Committing Alice's Secret Bit
- Step 6: Sending over the Channel
- Part II: Unveiling the Secret Bit
- Preventing Cheating

**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 *x _{b}* such
that

Later, when she wants to reveal her bit, Alice announces the original
codeword *x _{b}* to Bob (over a clear channel - not the noisy
one!). Bob can easily find out

**Protocol 1: Commiting Alice's bit**

- Alice and Bob together agree on the parameters of the protocol (explained in the next section)
- Alice and Bob together agree on a random linear code
- Alice and Bob together agree on a random vector
*m*(same length as codewords) - Alice chooses her secret bit
*b* - Alice picks a (random) codeword
*x*such that_{b}*x*·_{b}*m*=*b* - Alice sends
*x*over the noisy channel to Bob, who receives_{b}*x*._{b}'

**Protocol 2: Revealing Alice's bit**

- Alice announces
*x*to Bob over a clear channel_{b} - Bob tests to make sure Alice isn't cheating (the test is based on the
received word
*x*and is explained later)_{b}' - If Alice passes the test, Bob knows with almost absolute certainty
that
*x*·_{b}*m*was the bit Alice initially had in mind

The test Bob applies is to count the number of positions in which *x _{b}*
and

[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:

- Error probability of channel (
*p*) - This protocol assumes we are using a binary
symmetric channel.
*p*is the probability that a bit will be flipped when it is sent through the channel. This probability is the same for all bits sent throught the channel. In most situations, this parameter cannot be fixed by Alice or Bob - it is inherent to the channel they are using. - Number of uses of the channel (
*n*) - The only thing actually sent throught the noisy channel is Alice's
codeword
*x*. Hence, the number of times the channel is used (_{b}*n*) is exactly the length of the code Alice and Bob agree on in step 2 of protocol 1.

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(n*^{2}*)*
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:

*p*should be between 0 and 0.5 (exclusively).*n*should be between 250 and 350 (this will let you see the results of the protocol as we step through it).

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.

- Pick Alice's secret bit using the check boxes.
- Generate the vectors
*m*and*x*by using the buttons marked "m" and "x", respectively.

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:

*x*is a codeword- Distance between
*x*and*x'*is roughly*p***n*

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.