Happily, there is a complicated protocol that allows for authenticated but untraceable messages. Lobbyist Alice can transfer digital cash to Congresscritter Bob so that newspaper reporter Eve does not know Alice’s identity. Bob can then deposit that electronic money into his bank account, even though the bank has no idea who Alice is. But if Alice tries to buy cocaine with the same piece of digital cash she used to bribe Bob, she will be detected by the bank. And if Bob tries to deposit the same piece of digital cash into two different accounts, he will be detected—but Alice will remain anonymous. Sometimes this is called anonymous digital cash to differentiate it from digital money with an audit trail, such as credit cards.

A great social need exists for this kind of thing. With the growing use of the Internet for commercial transactions, there is more call for network-based privacy and anonymity in business. (There are good reasons people are reluctant to send their credit card numbers over the Internet.) On the other hand, banks and governments seem unwilling to give up the control that the current banking system’s audit trail provides. They’ll have to, though. All it will take for digital cash to catch on is for some trustworthy institution to be willing to convert the digits to real money.

Digital cash protocols are very complex. We’ll build up to one, a step at a time. For more formal details, read [318, 339, 325, 335, 340]. Realize that this is just one digital cash protocol; there are others.

Protocol #1

The first few protocols are physical analogies of cryptographic protocols. This first protocol is a simplified physical protocol for anonymous money orders:

(1)  Alice prepares 100 anonymous money orders for $1000 each.

(2)  Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She gives them all to the bank.

(3)  The bank opens 99 envelopes and confirms that each is a money order for $1000.

(4)  The bank signs the one remaining unopened envelope. The signature goes through the carbon paper to the money order. The bank hands the unopened envelope back to Alice, and deducts $1000 from her account.

(5)  Alice opens the envelope and spends the money order with a merchant.

(6)  The merchant checks for the bank’s signature to make sure the money order is legitimate.

(7)  The merchant takes the money order to the bank.

(8)  The bank verifies its signature and credits $1000 to the merchant’s account.

This protocol works. The bank never sees the money order it signed, so when the merchant brings it to the bank, the bank has no idea that it was Alice’s. The bank is convinced that it is valid, though, because of the signature. The bank is confident that the unopened money order is for $1000 (and not for $100, 000 or $100, 000, 000) because of the cut-and-choose protocol (see Section 5.1). It verifies the other 99 envelopes, so Alice has only a 1 percent chance of cheating the bank. Of course, the bank will make the penalty for cheating great enough so that it isn’t worth that chance. If the bank refuses to sign the last check (if Alice is caught cheating) without penalizing Alice, she will continue to try until she gets lucky. Prison terms are a better deterrent.

Protocol #2

The previous protocol prevents Alice from writing a money order for more than she claims to, but it doesn’t prevent Alice from photocopying the money order and spending it twice. This is called the double spending problem; to solve it, we need a complication:

(1)  Alice prepares 100 anonymous money orders for $1000 each. On each money order she includes a different random uniqueness string, one long enough to make the chance of another person also using it negligible.

(2)  Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She gives them all to the bank.

(3)  The bank opens 99 envelopes and confirms that each is a money order for $1000.

(4)  The bank signs the one remaining unopened envelope. The signature goes through the carbon paper to the money order. The bank hands the unopened envelope back to Alice and deducts $1000 from her account.

(5)  Alice opens the envelope and spends the money order with a merchant.

(6)  The merchant checks for the bank’s signature to make sure the money order is legitimate.

(7)  The merchant takes the money order to the bank.

(8)  The bank verifies its signature and checks its database to make sure a money order with the same uniqueness string has not been previously deposited. If it hasn’t, the bank credits $1000 to the merchant’s account. The bank records the uniqueness string in a database.

(9)  If it has been previously deposited, the bank doesn’t accept the money order.

Now, if Alice tries to spend a photocopy of the money order, or if the merchant tries to deposit a photocopy of the money order, the bank will know about it.

Protocol #3

The previous protocol protects the bank from cheaters, but it doesn’t identify them. The bank doesn’t know if the person who bought the money order (the bank has no idea it’s Alice) tried to cheat the merchant or if the merchant tried to cheat the bank. This protocol corrects that:

(1)  Alice prepares 100 anonymous money orders for $1000 each. On each of the money orders she includes a different random uniqueness string, one long enough to make the chance of another person also using it negligible.

(2)  Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She gives them all to the bank.

(3)  The bank opens 99 envelopes and confirms that each is a money order for $1000 and that all the random strings are different.

(4)  The bank signs the one remaining unopened envelope. The signature goes through the carbon paper to the money order. The bank hands the unopened envelope back to Alice and deducts $1000 from her account.

(5)  Alice opens the envelope and spends the money order with a merchant.

(6)  The merchant checks for the bank’s signature to make sure the money order is legitimate.

(7)  The merchant asks Alice to write a random identity string on the money order.

(8)  Alice complies.

(9)  The merchant takes the money order to the bank.

(10)  The bank verifies the signature and checks its database to make sure a money order with the same uniqueness string has not been previously deposited. If it hasn’t, the bank credits $1000 to the merchant’s account. The bank records the uniqueness string and the identity string in a database.

(11)  If the uniqueness string is in the database, the bank refuses to accept the money order. Then, it compares the identity string on the money order with the one stored in the database. If it is the same, the bank knows that the merchant photocopied the money order. If it is different, the bank knows that the person who bought the money order photocopied it.