Task

Data Dictionary

Teacher's Tools

Blinding

Certificates

Digital Signatures

Key Distribution

Public Key

Secret Splitting

Security Basics

Symmetric Key

An example of this could be a student's authorization to launch a set of balloons if he gets an 'A' in accounting..  The command could be:

Launch Balloons 

The commitment could be to a location.  Let us assume the location is:

Quinnipiac College

There are certain conditions that the student is concerned about:

1. He doesn't want the college to know he is going to launch the balloons..

2. He is unsure of his target.  He will only launch the balloons if he gets an A in Accounting.

3. He can't launch the balloons.  He must tell someone else to do this.

4. If he gets in A in accounting class, he wants to launch the balloons quickly.

The bit commitment protocol is a method of accomplishing this task.   Consider the following:

1. The receiver sends the sender a random string.  A string is a set of punctuation marks, letters, and numbers.

2. The sender creates a new message with the random string and the bit that it wishes to commit to in the future.

3. The sender encrypts the message with a random key.

4. The sender sends the encrypted message to the receiver.

At this point, the receiver cannot decrypt the message.  It does not know what the key is.  When the sender decides to commit the bit, the following protocol can be followed:

1. The sender and receiver agree on symmetric keys.

2. The sender encrypts the key it used to encrypt the random string and bit it wished to commit to with the symmetric key.

3. The sender sends the encrypted key to the receiver.

4. The receiver decrypts the message using the symmetric key.  This leaves the key that was used in the bit commitment protocol.

5. The receiver uses this key to decrypt the random string and bit that the sender wishes to commit to.

6. The receiver compares the value of the random string to the one it had generated to make certain the message is authentic.

7. The bit is now revealed and committed to.

Obviously, the bit could be several bytes or another message.  The same protocol would work.

Applying the analogy of the student and the balloon leads to the following protocol:

1. The balloon launcher sends the student the command sequence to launch the balloon.  Let us assume that this command is "Launch the balloons."

2. The sender creates the message "Launch the balloons at Quinnipiac College."   "At Quinnipiac College" is the bit that the student wishes to commit to at a later date.

3. The student encrypts the "Launch the balloons at Quinnipiac College" message with a random key.

4. The student sends the encrypted message to the balloon launcher.

The balloon launcher cannot interpret the message since it does not have the random key.  Therefore, the balloon cannot be launched until a later period of time.

When the student gets an A+ in accounting, he can launch the balloon through the following steps.

1. The student and balloon launcher agree on symmetric keys.

2. The student encrypts the key it used to encrypt "Launch the balloons at Quinnipiac College" with the symmetric key.   The encrypted key is the key that was used in step 3 of the previous protocol.

3. The student sends the encrypted key to the balloon launcher.

4. The balloon launcher decrypts the message using the symmetric key.  This leaves the key that was used in the bit commitment protocol.

5. The balloon launcher uses this key to decrypt "Launch the balloons at Quinnipiac College."

6. The balloon launcher recognizes the command "Launch the balloons" since it had sent it to the student.

7. The target, "Quinnipiac College" is revealed and committed to.  The balloons are launched and the party begins!

All of the student's concerns are addressed.

1. He doesn't want the college to know it is a target.  Quinnipiac College can't realize it is a target because the data is sent to the balloon launcher in an encrypted format.  The college doesn't have the key, so it can't decrypt it.  The college also does not have access to the symmetric key shared by the student and the launch center.

2. He is unsure of his target.  He will only launch the balloons if he gets an A in his accounting class.  The student authorizes the launch after he has sent the command to launch.  But, the student prevents the balloon launcher from firing ahead of schedule because the balloon launcher cannot interpret the command.

3. He can't launch the balloons.  He must tell someone else to do this.  Clearly, the balloon launcher is pulling the trigger.

4. If he aces his accounting class, he wants to launch the balloons quickly.  The sequence is quick because the command to launch has already been given. It just needs to be interpreted.

Another method of implementing the bit commitment protocol is to use one way functions.  The protocol is described below:

1. The sender generates two random strings.

2. The sender composes a message of the two random strings and the bit it wishes to commit to.

3. The sender uses a one way function on the message.  The one way function will be a hash in this instance.

4. The sender sends the hash to the receiver.

5. The sender passes one of the random strings to the receiver.

Since a one way function was used, the receiver cannot decode the message and determine the value of the bit.   When the sender determines that it is time to commit the bit, the following protocol is used:

1. The sender sends the message of two random strings and bit it wishes to commit to.

2. The receiver gets the message and calculates its hash.

3. The receiver compares the hash with the original hash it received.

4. The receiver compares one of the random strings to the one it had previously received.  If they are equal, then the second random string is used to determine the value of the bit.  The bit is then committed to.

The second random string is kept secret until the bit commitment occurs to prevent the receiver from trying different bit values to calculate the hash.  If it found the bit values, then the bit commitment could occur too early in time.

To better explain this scenario, let's assume that a student, Tom,  wants to go out with a girl, Jen, at a coffee shop if his ex-girlfriend isn't working there.  Tom wants Jen to reserve the evening, but doesn't want to tell her where they are going.

1. Tom generates two random strings.  The strings are "I want to go out with you tonight" and "since my ex-girlfriend isn't working there tonight."

2. Tom composes a message of the two random strings and the bit it wishes to commit to.  Therefore, the message is "I want to go out with you tonight at the coffee shop since my ex-girlfriend is working there tonight."

3. Tom uses a one way function on the message.  The one way function will be a hash in this instance.

4. Tom sends the hash to Jen.

5. Tom sends one of his strings to Jen.  He sends, "I want to go out with you tonight."

At this point, Jen knows that Tom wants to go out with her tonight.  But Jen doesn't know where.   Tom confirms that his ex-girlfriend won't be there, so he needs to tell Jen.

1. Tom sends "I want to go out with you tonight at the coffee shop since my ex-girlfriend isn't working there tonight." 

2. Jen gets the message and calculates its hash.

3. Jen compares the hash with the original hash it received.  It is identical.

4. Jen recognizes the string, "I want to go out with you tonight."  She understands that Tom's ex-girlfriend isn't working tonight and that she should meet him at the coffee shop.

Jen would have a tough time guessing that the coffee shop is where they are going.  This is because there is a good amount of unknown data in the hash.  The coffee shop and the fact that the ex-girlfriend isn't working are both part of the hash.  It would take too long for Jen to try and calculate this hash. If there was a large amount of data being committed to, then the fact that Tom's ex-girlfriend wasn't working could be left out of the hash.

For more information:

1. "Background for Bit Commitment" by Claude Crepeau is available at http://www.cs.mcgill.ca/~crepeau/CRYPTO/BCDemo/BCbackground.html. March 15, 1998