Previous

Table of Contents

Next

To make this work, Alice had to switch envelopes at the end of the trick. However, cryptographic protocols can provide a method immune from any sleight of hand. Why is this useful? Here’s a more mundane story:

Stockbroker Alice wants to convince investor Bob that her method of picking winning stocks is sound.

Bob: “Pick five stocks for me. If they are all winners, I’ll give you my business.”

Alice: “If I pick five stocks for you, you could invest in them without paying me. Why don’t I show you the stocks I picked last month?”

Bob: “How do I know you didn’t change last month’s picks after you knew their outcome? If you tell me your picks now, I’ll know that you can’t change them. I won’t invest in those stocks until after I’ve purchased your method. Trust me.”

Alice: “I’d rather show you my picks from last month. I didn’t change them. Trust me.”

Alice wants to commit to a prediction (i.e., a bit or series of bits) but does not want to reveal her prediction until sometime later. Bob, on the other hand, wants to make sure that Alice cannot change her mind after she has committed to her prediction.

Bit Commitment Using Symmetric Cryptography

This bit-commitment protocol uses symmetric cryptography:

(1)  Bob generates a random-bit string, R, and sends it to Alice.

R

(2)  Alice creates a message consisting of the bit she wishes to commit to, b (it can actually be several bits), and Bob’s random string. She encrypts it with some random key, K, and sends the result back to Bob.

E_K(R,b)

That is the commitment portion of the protocol. Bob cannot decrypt the message, so he does not know what the bit is.

When it comes time for Alice to reveal her bit, the protocol continues:

(3)  Alice sends Bob the key.

(4)  Bob decrypts the message to reveal the bit. He checks his random string to verify the bit’s validity.

If the message did not contain Bob’s random string, Alice could secretly decrypt the message she handed Bob with a variety of keys until she found one that gave her a bit other than the one she committed to. Since the bit has only two possible values, she is certain to find one after only a few tries. Bob’s random string prevents her from using this attack; she has to find a new message that not only has her bit inverted, but also has Bob’s random string exactly reproduced. If the encryption algorithm is good, the chance of her finding this is minuscule. Alice cannot change her bit after she commits to it.

Bit Commitment Using One-Way Functions

This protocol uses one-way functions:

(1)  Alice generates two random-bit strings, R₁ and R₂.

R₁,R₂

(2)  Alice creates a message consisting of her random strings and the bit she wishes to commit to (it can actually be several bits).

(R₁,R₂,b)

(3)  Alice computes the one-way function on the message and sends the result, as well as one of the random strings, to Bob.

H(R₁,R₂,b),R₁

This transmission from Alice is evidence of commitment. Alice’s one-way function in step (3) prevents Bob from inverting the function and determining the bit.

When it comes time for Alice to reveal her bit, the protocol continues:

(4)  Alice sends Bob the original message.

(R₁,R₂,b)

(5)  Bob computes the one-way function on the message and compares it and R₁, with the value and random string he received in step (3). If they match, the bit is valid.

The benefit of this protocol over the previous one is that Bob does not have to send any messages. Alice sends Bob one message to commit to a bit and another message to reveal the bit.

Bob’s random string isn’t required because the result of Alice’s commitment is a message operated on by a one-way function. Alice cannot cheat and find another message (R₁,R₂´,b´), such that H(R₁,R₂´,b´) = H(R₁,R₂,b). By sending Bob R₁ she is committing to the value of b. If Alice didn’t keep R₂ secret, then Bob could compute both H(R₁,R_2,b) and H(R₁,R₂,b´) and see which was equal to what he received from Alice.

Bit Commitment Using Pseudo-Random-Sequence Generators

This protocol is even easier [1137]:

(1)  Bob generates a random-bit string and sends it to Alice.

R_B

(2)  Alice generates a random seed for a pseudo-random-bit generator. Then, for every bit in Bob’s random-bit string, she sends Bob either:

(a) the output of the generator if Bob’s bit is 0, or

(b) the XOR of output of the generator and her bit, if Bob’s bit is 1.

When it comes time for Alice to reveal her bit, the protocol continues:

(3)  Alice sends Bob her random seed.

(4)  Bob completes step (2) to confirm that Alice was acting fairly.

If Bob’s random-bit string is long enough, and the pseudo-random-bit generator is unpredictable, then there is no practical way Alice can cheat.

Blobs

These strings that Alice sends to Bob to commit to a bit are sometimes called blobs. A blob is a sequence of bits, although there is no reason in the protocols why it has to be. As Gilles Brassard said, “They could be made out of fairy dust if this were useful” [236]. Blobs have these four properties:

1.  Alice can commit to blobs. By committing to a blob, she is committing to a bit.

2.  Alice can open any blob she has committed to. When she opens a blob, she can convince Bob of the value of the bit she committed to when she committed to the blob. Thus, she cannot choose to open any blob as either a zero or a one.

3.  Bob cannot learn how Alice is able to open any unopened blob she has committed to. This is true even after Alice has opened other blobs.

4.  Blobs do not carry any information other than the bit Alice committed to. The blobs themselves, as well as the process by which Alice commits to and opens them, are uncorrelated to anything else that Alice might wish to keep secret from Bob.

Previous

Table of Contents

Next