This protocol assumes that the merchant cannot change the identity string once Alice writes it on the money order. The money order might have a series of little squares, which the merchant would require Alice to fill in with either Xs or Os. The money order might be made out of paper that tears if erased.

Since the interaction between the merchant and the bank takes place after Alice spends the money, the merchant could be stuck with a bad money order. Practical implementations of this protocol might require Alice to wait near the cash register during the merchant-bank interaction, much the same way as credit-card purchases are handled today.

Alice could also frame the merchant. She could spend a copy of the money order a second time, giving the same identity string in step (7). Unless the merchant keeps a database of money orders it already received, he would be fooled. The next protocol eliminates that problem.

Protocol #4

If it turns out that the person who bought the money order tried to cheat the merchant, the bank would want to know who that person was. To do that requires moving away from a physical analogy and into the world of cryptography.

The technique of secret splitting can be used to hide Alice’s name in the digital money order.

(1)  Alice prepares n anonymous money orders for a given amount.
Each of the money orders contains a different random uniqueness string, X, one long enough to make the chance of two being identical negligible.
On each money order, there are also n pairs of identity bit strings, I₁, I₂,..., I_n. (Yes, that’s n different pairs on each check.) Each of these pairs is generated as follows: Alice creates a string that gives her name, address, and any other piece of identifying information that the bank wants to see. Then, she splits it into two pieces using the secret splitting protocol (see Section 3.6). Then, she commits to each piece using a bit-commitment protocol.
For example, I₃₇ consists of two parts: I_37L and I_37R. Each part is a bit-committed packet that Alice can be asked to open and whose proper opening can be instantly verified. Any pair (e.g., I_37L and I_37R, but not I_37L and I_38R), reveals Alice’s identity.
Each of the money orders looks like this:

	Amount
	Uniqueness String: X
     Identity Strings:  I1 = (I1L,I1R)
                        I2 =       (I2L,I2R)
                         ....
                        In = (InL, InR)

(2)  Alice blinds all n money orders, using a blind signature protocol. She gives them all to the bank.

(3)  The bank asks Alice to unblind n - 1 of the money orders at random and confirms that they are all well formed. The bank checks the amount, the uniqueness string, and asks Alice to reveal all of the identity strings.

(4)  If the bank is satisfied that Alice did not make any attempts to cheat, it signs the one remaining blinded money order. The bank hands the blinded money order back to Alice and deducts the amount from her account.

(5)  Alice unblinds the money order and spends it with a merchant.

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

(7)  The merchant asks Alice to randomly reveal either the left half or the right half of each identity string on the money order. In effect, the merchant gives Alice a random n- bit selector string, b₁, b₂,..., b_n. Alice opens either the left or right half of I_i, depending on whether b_i is a 0 or a 1.

(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 the amount to the merchant’s account. The bank records the uniqueness string and all of the identity information 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 copied the money order. If it is different, the bank knows that the person who bought the money order photocopied it. Since the second merchant who accepted the money order handed Alice a different selector string than did the first merchant, the bank finds a bit position where one merchant had Alice open the left half and the other merchant had Alice open the right half. The bank XORs the two halves together to reveal Alice’s identity.

This is quite an amazing protocol, so let’s look at it from various angles.

Can Alice cheat? Her digital money order is nothing more than a string of bits, so she can copy it. Spending it the first time won’t be a problem; she’ll just complete the protocol and everything will go smoothly. The merchant will give her a random n-bit selector string in step (7) and Alice will open either the left half or right half of each I_i in step (8). In step (10), the bank will record all of this data, as well as the money order’s uniqueness string.

When she tries to use the same digital money order a second time, the merchant (either the same merchant or a different merchant) will give her a different random selector string in step (7). Alice must comply in step (8); not doing so will immediately alert the merchant that something is suspicious. Now, when the merchant brings the money order to the bank in step (10), the bank would immediately notice that a money order with the same uniqueness string was already deposited. The bank then compares the opened halves of the identity strings. The odds that the two random selector strings are the same is 1 in 2ⁿ; it isn’t likely to happen before the next ice age. Now, the bank finds a pair with one half opened the first time and the other half opened the second time. It XORs the two halves together, and out pops Alice’s name. The bank knows who tried to spend the money order twice.

Note that this protocol doesn’t keep Alice from trying to cheat; it detects her cheating with almost certainty. Alice can’t prevent her identity from being revealed if she cheats. She can’t change either the uniqueness string or any of the identity strings, because then the bank’s signature will no longer be valid. The merchant will immediately notice that in step (6).

Alice could try to sneak a bad money order past the bank, one on which the identity strings don’t reveal her name; or better yet, one whose identity strings reveal someone else’s name. The odds of her getting this ruse past the bank in step (3) are 1 in n . These aren’t impossible odds, but if you make the penalty severe enough, Alice won’t try it. Or, you could increase the number of redundant money orders that Alice makes in step (1).

Can the merchant cheat? His chances are even worse. He can’t deposit the money order twice; the bank will notice the repeated use of the selector string. He can’t fake blaming Alice; only she can open any of the identity strings.