Bob now has one of the two messages from Alice and Alice does not know which one he was able to read successfully. Unfortunately, if the protocol stopped here it would be possible for Alice to cheat. Another step is necessary.

(6)  After the protocol is complete and both possible results of the transfer are known, Alice must give Bob her private keys so that he can verify that she did not cheat. After all, she could have encrypted the same message with both keys in step (4).

At this point, of course, Bob can figure out the second message.

The protocol is secure against an attack by Alice because she has no way of knowing which of the two DES keys is the real one. She encrypts them both, but Bob only successfully recovers one of them—until step (6). It is secure against an attack by Bob because, before step (6), he cannot get Alice’s private keys to determine the DES key that the other message was encrypted in. This may still seem like nothing more than a more complicated way to flip coins over a modem, but it has extensive implications when used in more complicated protocols.

Of course, nothing stops Alice from sending Bob two completely useless messages: “Nyah Nyah” and “You sucker.” This protocol guarantees that Alice sends Bob one of two messages; it does nothing to ensure that Bob wants to receive either of them.

Other oblivious transfer protocols are found in the literature. Some of them are noninteractive, meaning that Alice can publish her two messages and Bob can learn only one of them. He can do this on his own; he doesn’t have to communicate with Alice [105].

No one really cares about being able to do oblivious transfer in practice, but the notion is an important building block for other protocols. Although there are many types of oblivious transfer—I have two secrets and you get one; I have n secrets and you get one; I have one secret which you get with probability 1/2; and so on—they are all equivalent [245,391,395].

5.6 Oblivious Signatures

Honestly, I can’t think of a good use for these, but there are two kinds [346]:

1.  Alice has n different messages. Bob can choose one of the n messages for Alice to sign, and Alice will have no way of knowing which one she signed.

2.  Alice has one message. Bob can choose one of n keys for Alice to use in signing the message, and Alice will have no way of knowing which key she used.

It’s a neat idea; I’m sure it has a use somewhere.

5.7 Simultaneous Contract Signing

Contract Signing with an Arbitrator

Alice and Bob want to enter into a contract. They’ve agreed on the wording, but neither wishes to sign unless the other signs as well. Face to face, this is easy: Both sign together. Over a distance, they could use an arbitrator.

(1)  Alice signs a copy of the contract and sends it to Trent.

(2)  Bob signs a copy of the contract and sends it to Trent.

(3)  Trent sends a message to both Alice and Bob indicating that the other has signed the contract.

(4)  Alice signs two copies of the contract and sends them to Bob.

(5)  Bob signs both copies of the contract, keeps one for himself, and sends the other to Alice.

(6)  Alice and Bob both inform Trent that they each have a copy of the contract signed by both of them.

(7)  Trent tears up his two copies of the contract with only one signature each.

This protocol works because Trent prevents either of the parties from cheating. If Bob were to refuse to sign the contract in step (5), Alice could appeal to Trent for a copy of the contract already signed by Bob. If Alice were to refuse to sign in step (4), Bob could do the same. When Trent indicates that he received both contracts in step (3), both Alice and Bob know that the other is bound by the contract. If Trent does not receive both contracts in steps (1) and (2), he tears up the one he received and neither party is bound.

Simultaneous Contract Signing without an Arbitrator (Face-to-Face)

If Alice and Bob were sitting face-to-face, they could sign the contract this way [1244]:

(1)  Alice signs the first letter of her name and passes the contract to Bob.

(2)  Bob signs the first letter of his name and passes the contract to Alice.

(3)  Alice signs the second letter of her name and passes the contract to Bob.

(4)  Bob signs the second letter of his name and passes the contract to Alice.

(5)  This continues until both Alice and Bob have signed their entire names.

If you ignore the obvious problem with this protocol (Alice has a longer name than Bob), it works just fine. After signing only one letter, Alice knows that no judge will bind her to the terms of the contract. But the letter is an act of good faith, and Bob responds with a similar act of good faith.

After each party has signed several letters, a judge could probably be convinced that both parties had signed the contract. The details are murky, though. Surely they are not bound after only the first letter; just as surely they are bound after they sign their entire names. At what point in the protocol do they become bound? After signing one-half of their names? Two-thirds of their names? Three-quarters?

Since neither Alice nor Bob is certain of the exact point at which she or he is bound, each has at least some fear that she or he is bound throughout the protocol. At no point can Bob say: “You signed four letters and I only signed three. You are bound but I am not.” Bob has no reason not to continue with the protocol. Furthermore, the longer they continue, the greater the probability that a judge will rule that they are bound. Again, there is no reason not to continue with the protocol. After all, they both wanted to sign the contract; they just didn’t want to sign before the other one.

Simultaneous Contract Signing without an Arbitrator (Not Face-to-Face)

This protocol uses the same sort of uncertainty [138]. Alice and Bob alternate taking baby steps toward signing until both have signed.

In the protocol, Alice and Bob exchange a series of signed messages of the form: “I agree that with probability p, I am bound by this contract.”

The recipient of this message can take it to a judge and, with probability p, the judge will consider the contract to be signed.

(1)  Alice and Bob agree on a date by which the signing protocol should be completed.

(2)  Alice and Bob decide on a probability difference that they are willing to live with. For example, Alice might decide that she is not willing to be bound with a greater probability than 2 percent over Bob’s probability. Call Alice’s difference a; call Bob’s difference b.

(3)  Alice sends Bob a signed message with p = a.

(4)  Bob sends Alice a signed message with p = a + b.

(5)  Let p be the probability of the message Alice received in the previous step from Bob. Alice sends Bob a signed message with p´ = p + a or 1, whichever is smaller.

(6)  Let p be the probability of the message Bob received in the previous step from Alice. Bob sends Alice a signed message with p´ = p + b or 1, whichever is smaller.

(7)  Alice and Bob continue alternating steps (5) and (6) until both have received messages with p = 1 or until the date agreed to in step (1) has passed.