5.8 Digital Certified Mail

The same simultaneous oblivious transfer protocol used for contract signing works, with some modifications, for computer certified mail [529]. Suppose Alice wants to send a message to Bob, but she does not want him to read it without signing a receipt. Surly postal workers handle this process in real life, but the same thing can be done with cryptography. Whitfield Diffie first discussed this problem in [490].

At first glance, the simultaneous contract-signing protocol can do this. Alice simply encrypts her message with a DES key. Her half of the protocol can be something like: “This is the left half of the DES key: 32f5,” and Bob’s half can be something like: “This is the left half of my receipt.” Everything else stays the same.

To see why this won’t work, remember that the protocol hinges on the fact that the oblivious transfer in step (5) keeps both parties honest. Both of them know that they sent the other party a valid half, but neither knows which. They don’t cheat in step (8) because the odds of getting away with it are miniscule. If Alice is sending Bob not a message but half of a DES key, Bob can’t check the validity of the DES key in step (6). Alice can still check the validity of Bob’s receipt, so Bob is still forced to be honest. Alice can freely send Bob some garbage DES key, and he won’t know the difference until she has a valid receipt. Tough luck, Bob.

Getting around this problem requires some adjustment of the protocol:

(1)  Alice encrypts her message using a random DES key, and sends the message to Bob.

(2)  Alice generates n pairs of DES keys. The first key of each pair is generated at random; the second key of each pair is the XOR of the first key and the message encryption key.

(3)  Alice encrypts a dummy message with each of her 2n keys.

(4)  Alice sends the whole pile of encrypted messages to Bob, making sure he knows which messages are which halves of which pairs.

(5)  Bob generates n pairs of random DES keys.

(6)  Bob generates a pair of messages that indicates a valid receipt. “This is the left half of my receipt” and “this is the right half of my receipt” are good candidates, with the addition of some kind of random-bit string. He makes n receipt pairs, each numbered. As with the previous protocol, the receipt is considered valid if Alice can produce both halves of a receipt (with the same number) and all of her encryption keys.

(7)  Bob encrypts each of his message pairs with DES key pairs, the ith message pair with the ith key pair, the left message with the left key in the pair, and the right message with the right key in the pair.

(8)  Bob sends his pile of message pairs to Alice, making sure that Alice knows which messages are which halves of which pairs.

(9)  Alice and Bob send each other every key pair using the oblivious transfer protocol. That is, Alice sends Bob either the key used to encrypt the left message or the key used to encrypt the right message, for each of the n pairs. Bob does the same. They can either alternate sending halves or one can send n and then the other—it doesn’t matter. Now both Alice and Bob have one key in each key pair, but neither knows which halves the other has.

(10)  Both Alice and Bob decrypt the halves they can and make sure that the decrypted messages are valid.

(11)  Alice and Bob send each other the first bits of all 2n DES keys. (If they are worried about Eve being able to read these mail messages, then they should encrypt their transmissions to each other.)

(12)  Alice and Bob repeat step (11) for the second bits of all 2n DES keys, the third bits, and so on, until all the bits of all the DES keys have been transferred.

(13)  Alice and Bob decrypt the remaining halves of the message pairs. Alice has a valid receipt from Bob, and Bob can XOR any key pair to get the original message encryption key.

(14)  Alice and Bob exchange the private keys used during the oblivious transfer protocol and each verifies that the other did not cheat.

Steps (5) through (8) for Bob, and steps (9) through (12) for both Alice and Bob, are the same as the contract-signing protocol. The twist is all of Alice’s dummy messages. They give Bob some way of checking the validity of her oblivious transfer in step (10), which forces her to stay honest during steps (11) through (13). And, as with the simultaneous contract-signing protocol, both a left and a right half of one of Alice’s message pairs are required to complete the protocol.

5.9 Simultaneous Exchange of Secrets

Alice knows secret A; Bob knows secret B. Alice is willing to tell Bob A, if Bob tells her B. Bob is willing to tell Alice B, if Alice tells him A. This protocol, observed in a schoolyard, does not work:

(1)  Alice: “I’ll tell if you tell me first.”

(2)  Bob: “I’ll tell if you tell me first.”

(3)  Alice: “No, you first.”

(4)  Bob: “Oh, all right.” Bob whispers.

(5)  Alice: “Ha! I won’t tell you.”

(6)  Bob: “That’s not fair.”

Cryptography can make it fair. The previous two protocols are implementations of this more general protocol, one that lets Alice and Bob exchange secrets simultaneously [529]. Rather than repeat the whole protocol, I’ll sketch the modifications to the certified mail protocol.

Alice performs steps (1) through (4) using A as the message. Bob goes through similar steps using B as his message. Alice and Bob perform the oblivious transfer in step (9), decrypt the halves they can in step (10), and go through the iterations in steps (11) and (12). If they are concerned about Eve, they should encrypt their messages. Finally, both Alice and Bob decrypt the remaining halves of the message pairs and XOR any key pair to get the original message encryption key.

This protocol allows Alice and Bob to exchange secrets simultaneously, but says nothing about the quality of the secrets exchanged. Alice could promise Bob the solution to the Minotaur’s labyrinth, but actually send him a map of Boston’s subway system. Bob will get whatever secret Alice sends him. Other protocols are [1286,195,991,1524,705,753,259,358,415].