This is how it works in general terms: Alice opens an account with a bank non-anonymously. She shows ID so that the bank knows who she is; both she and the bank know her account number. When she withdraws cash, she goes to the bank or contacts them electronically and presents some proof of who she is and what her account number is, and the bank gives her some digital cash. The digital cash is an information pattern, perhaps stored in a computer file on a smart card or magnetic disk. Later, she spends the digital cash by sending or giving it to Bob, a merchant. Bob can check and verify that the cash must have come from the bank. He accepts the cash if it is valid, giving Alice the merchandise. Later, he sends the cash to the bank to be added to his own account.

Note that this much could basically be done with a simple RSA signature. The bank could give Alice a statement saying, "this is worth $1", signed by the bank's public key. Bob could verify that the statement was in fact signed by the bank, and know therefore that no one else than the bank could have created that statement. He accepts it and sends it to the bank, which honors it since it recognizes its own signature.

One problem with this trivial money is that double-spending can not be detected or prevented since all the cash looks alike. This can be remedied by having the cash include a unique serial number. Now when Bob goes to accept the cash from Alice, he can call the bank and say, has anyone else deposited serial number 123456? If not, he accepts the cash and deposits it. This is called on-line electronic money; the merchant must check with the bank for each transaction.

This improved simple system does not deserve to be called cash, though, because it lacks the distinguishing characteristic of digital cash: it is not anonymous. When the bank sees money with serial number 123456 being deposited, the bank recognizes that this was the same bill that Alice withdrew. The bank can therefore deduce that Alice spent the money at Bob's, and from this kind of information a dossier could be built up with all kinds of privacy-destroying information about her.

To allow anonymity, we have to get into the mathematics. What we want is for Alice and the bank collectively to create an RSA signature from the bank that could not be forged, but one which the bank will not recognize as coming from Alice. This is the first thing Chaum's paper discusses.

The money in this system is of the form (x, f(x)^(1/3)) mod n, where n is the bank's public modulus. f() (and, below, g()) is a one-way function, one which can be calculated easily but for which it is infeasible to calculate the inverse. It should also be infeasible to come up with two different y,z such that f(y) = f(z). Today there are several suitable choices for one-way functions, the most common being the MD4 and MD5 algorithms from RSA.

The reason the expression above would be accepted as cash is two-fold. First, only the bank can calculate anything ^ (1/3) mod n. This is basically the RSA signing operation for the exponent of 3. Nobody else can find cube roots. The reason f(x) is used is this. Suppose we proposed that (x, x^(1/3)) should be the cash, for some random x, reasoning that only the bank could find the cube root of x. Can you see how to forge cash like this? (Take a few moments and try to see how you could construct a pair like this even if you can't take cube roots.)

The answer is that it is easy to forge this by first choosing a random y, and exhibiting the pair (y^3, y). Now we have a number and then its cube root. Yet we didn't have to take any cube roots to find it. That's why this kind of money would be no good.

Chaum's system avoids this by taking the cube root of a one-way function of x. To forge it without taking a cube root you'd have to produce (finv(y^3), y), which would match the above pattern, but you can't invert the one-way function like that. So only the bank can create money of the proper form. This can be thought of as the formal, mathematical form of my informal "money" above which was a digitally signed note with a serial number. Here, x is the serial number, and it's digitally signed in this special way. Nothing more is needed.

The nice thing about this money is that it allows for blinding, a method of having the bank sign the value without knowing what value it is signing. It works like this. Alice chooses x, which will be the x in the cash. She calculates f(x), but instead of sending it to the bank to be signed (raised to the 1/3 power) she first chooses a random number r, and sends f(x)*r^3 to the bank. The bank takes this number to the 1/3 power, getting r * f(x)^(1/3). Remember, though, that the bank doesn't see r or f(x) separately, but just their product. It doesn't know what r or f(x) is. They could each be anything, actually.

The bank sends this r * f(x)^(1/3) back to Alice, and she divides it by r, which she knows. This gives her f(x)^(1/3), and she puts that together with x to get her digital cash: (x, f(x)^(1/3)). She has a piece of money which could only have been signed by the bank, yet the bank won't recognize it when it is deposited.

Other, non-mathematical, things take place as this withdrawal goes on. Alice must prove her identity to the bank, as mentioned above. And the bank will debit her account by the value of the cash. In this system, we are assuming for simplicity that all cash has the same value. In a real system, different values might be encoded by different exponents than 3.

When Alice deposits the money, Bob must call the bank to make sure that it hasn't been deposited before, this being an "on-line" system. Although the bank won't recognize x (it's never heard of it) it will remember all the x's which have been deposited and so can alert Bob if the money has been spent before. Both Bob and the bank can verify the digital signature on the money and so will honor it.

All the material above takes up less than one page of Chaum's nine-page paper. For Chaum, this much is trivial. Now we get to the interesting part. Now we will see the scheme that allows double-spenders to lose their anonymity. This will allow for "off-line" electronic cash; Bob will no longer have to check with the bank to see if the money has already been spent. He accepts it from Alice knowing that if she does cheat, the bank will honor the cash and sue Alice to make up the loss.

Let's start with the form of the cash itself. It is the product of k/2 numbers, where k is a "security parameter" that affects the chance of a cheater getting away with it. Each number is of the form f(xi,yi)^(1/3), where f is a two-argument one-way function like the f above. (The "xi", "yi", "ai", etc. here are separate values for each i from 0 to k/2.)

xi and yi are like this: xi = g(ai, ci), where ai and ci are random, and g is another one-way function. yi is kind of complicated. It is basically g(ai xor <info>, di). di is another random number, and <info>, the key to this whole operation, is identifying information about Alice's account! It is her account number concatenated with a serial number for the cash.

Now, why go through all this? Here's why. If you could find out both ai and (ai xor <info>), for some i, you would know Alice's identity. (Xor'ing them would produce <info>.) When Alice double-spends, both ai and ai xor <info> will be revealed.

What happens when Alice spends the coin is this. For each i from 0 to k/2 Bob chooses 0 or 1 at random. If he chooses 1 he gets told ai (and some other stuff). If he chooses 0 he gets told ai xor <info> (and other stuff). The other things he gets told are sufficient to let him confirm that the money is of the proper form.

Now, if Bob does this, he'll know a bunch of ai's, and he'll know a bunch of (ai xor <info>)'s, but they are for different i's. He doesn't know both ai and (ai xor <info>) for any one i. So he can't break Alice's anonymity.

When Bob deposits the money at the bank, he passes along the information he got from Alice regarding the ai's and such.

Now, suppose Alice cheats. She spends the money again somewhere else, at Charlie's. Charlie goes through the same procedure as Bob, choosing 0 or 1 at random for each value of i. Here is the catch. Since he is choosing at random, it would be very unlikely that he will choose exactly the same 0's and 1's that Bob chose. (Here is where the size of k matters - making it bigger makes it less likely that Charlie and Bob will choose the same pattern of 0's and 1's. But it makes the calculations take longer.) That means for one or more values of i, Charlie will probably choose a 0 where Bob chose a 1, or vice versa.

Because of this, if Bob got ai for that i, Charlie will get ai xor <info>. Or if Bob got ai xor <info>, Charlie will get ai. Either way, when Charlie sends his record of this information to the bank, the bank will put Bob's and Charlie's information together and get both ai and ai xor <info>. Xor'ing these together reveals <info>, and Alice is caught! This is the main idea.

All the other things, the ci's and di's and such, are there so that Bob can confirm that the money is of the proper form. For each value of i Alice has to give him enough information to calculate xi and yi. If Bob chooses a 1, she gives him ai, ci, and yi. Given ai and ci Bob can calculate xi (=g(ai,ci)), and with this and yi he can calculate f(xi,yi). If Bob chooses a 0, she gives him (ai xor <info>), as described before, and also di and xi. Given (ai xor <info>) and di, Bob calculates yi (=g(ai xor <info>, di)), and with this and xi he can calculate f(xi,yi).

So for each i, whether Bob gives a 0 or a 1 he gets enough information to calculate f(xi,yi). He multiplies these all together and confirms that they are equal to Alice's original "money" value when it is taken to the 3rd power (recall the money was product of f(xi,yi)^(1/3) for all i). Only the bank could have produced a signature on this one-way function f whose arguments take this special form.

One more complication exists. (Well, actually, an almost infinite number of complications exist if you look hard enough. But we'll just focus on one more.) Alice needs to get this special form of money from the bank in such a way that the bank won't recognize it. That means she has to blind it. But in this case the bank wants to be sure that the money is of the proper form when it signs it; in particular, it wants to make darned sure that Alice's <info> which is buried deep in all of those f's of g's is actually the right one for her. But since the bank can't see what it is signing, this is hard to do.

Chaum uses cut-and-choose for this. He has Alice prepare all these f's and g's according to the form above, carefully embedding her own incriminating <info> in each one. Then she multiplies each f(xi,yi) by a blinding factor ri^3 just like in the first cash. These are what she sends to the bank to be signed.

The trick, though, is that she sends twice as many as will be used. She sends k of them, but only k/2 will be used. (That's why the loop above used k/2 as the limit.) The bank chooses k/2 at random out of the k she sent as the ones which will actually be used. Alice then has to send the blinding ri values for the ones which the bank didn't pick.

The idea is that if Alice tries to cheat, embedding "Bozo" instead of "Alice" in that <info> field, she's taking a chance. First, to be useful, she's going to have to embed it in a lot of <info> fields for different values of i. When Bob and Charlie compare notes after she double-spends, every value of i for which they chose different 0's and 1's, which will be on the average half of them, will reveal an <info> field. If she only fakes a few, chances are her real identity will still be revealed.

But if she falsifies a great many of them, then when the bank chooses half, chances are at least some of the fake ones will be in the set the bank didn't choose. Then when Alice has to reveal her blinding r's, the jig will be up. The bank will un-blind all those f(xi,yi)'s which aren't being used, and see the fake <info> fields.

This cut-and-choose methodology has the disadvantage that Alice has to do twice as much work in preparing the money, half of which will just be thrown away. But it is a simple, "brute force" way to make sure that blinding signatures are actually being done on properly-formed data.

So, there you have it. Anonymity as long as you don't cheat, and double-spenders get caught. It's a little complicated but that's what computers are for; Bob and Alice wouldn't do all this stuff by hand. Alice would push the "generate a money candidate" button and get something to be sent to the bank (lots of the new PDA's have infrared wireless communications that would be perfect for face-to-face transactions). Bob would push the "check money" button when Alice spent it and it would flash red or green. As long as the calculations don't actually take too much time, which they really wouldn't in this case despite this long-winded explanation, the people involved can ignore the details.

Hal Finney hfinney@shell.portal.com 

Recall that the double-spending cash is the product, for i from 0 to k/2, of f(xi,yi)^(1/3), mod the bank's public modulus. f() is a one-way function, one which can't be inverted. xi and yi were a little complicated, and here is where my simplification comes in.

Let xi be g(ai), where ai is a random number and g is a one-way function. Let yi be g(ai xor <info>), where <info> is Alice's identifying information, her account number. Normally the ai "blinds" that since it is random and it is xor'd onto it. But if ever both ai and ai xor <info> are known, <info> is revealed and Alice's goose is cooked.

Everything else works as Chaum suggested; I have just eliminated his ci and di random numbers. In his proposal, g took two arguments, and ci and di were appended for the xi and yi cases. But I'm convinced now that these are unnecessary for our purposes.

The purpose for ci and di are to provide "unconditional" anonymity to Alice if she doesn't cheat. Look what happens with my simpler system. She tells Bob ai and yi for certain i's. Now, g is a one-way function, but suppose Bob had a big enough computer to try all possible arguments to g. Sooner or later he'd find a value Z for which g(Z) was yi. So then he could figure that Z equals ai xor <info>, and he knows ai, so he could find <info>. This means that in my simplified system Alice is depending on Bob (and everyone else) being unable to crack g() in order to stay anonymous.

Chaum's system is better. By having a g with two arguments he creates a huge number of solutions to g(Z1,Z2) = yi. There is no way for Bob to tell which one is right, so even with infinite computing resources he can't crack Alice's anonymity.

My thought is, unconditional anonymity is really no better than computational anonymity in the real world. Eric Hughes often says "all cryptograpy is economics". In practice, beyond a certain point, anonymity would not be broken by a direct computational attack, but rather by other means - bribery, theft, etc. In the real world there is no such thing as "unconditional" anonymity. In practice, computational anonymity is enough.

So my feeling is that for implementation purposes the ci and di in Chaum's system can be removed, simplifying the protocols somewhat, at the cost of reducing Alice's anonymity from unconditional to computational.

So, this method relies on trusting the bank? After all, Alice must include her identity in the messages, so that double spending can be detected later. When the bank verifies that it says 'Alice' and not 'Bozo', then it could keep track of her coins.

This method does not depend on trusting the bank not to reveal Alice's identity. That's why this is called "cash". As long as she does not double-spend, her identity is kept secret.

I'm not sure whether you are asking about the part of the protocol where Alice withdraws her cash from the bank, or the later part where she spends the money and the merchant sends it to the bank. When she withdraws the money, she blinds the f(xi,yi) candidates by multiplying them by ri. For half of those, she has to reveal the ri, but that half IS NOT USED in the rest of the protocol. The ones which are used are blinded and so the bank never sees her <info> in those.

When she spends the money and reveals the values to the merchant, Alice only includes her <info> in the form (ai xor <info>), where ai is a random value that nobody knows unless she double-spends. The ai "blinds" the <info> so that (ai xor <info>) does not reveal <info>. Only if she double-spends is both ai and (ai xor <info>) revealed for some i, and only then is her <info> exposed.

To take cube roots, the bank must find a d such that d*3 = 1 mod (p-1)(q-1), where p and q are the secret primes in its RSA system. Finding such a d is a simple application of Euclid's algorithm. It has the property that (m^d)^3 = (m^3)^d = m. In other words, taking a number to the power of d produces its cube root. This is the basic mathematics behind the RSA public-key cryptosystem.

Marc Horowitz asks about collusion between Bob and Charlier to pick the same 1's and 0's. It is true that this would defeat the scheme. However, the chances of this happening randomly are so low that the bank would know that at least one of them was cheating, although it would not know which.

Chaum discusses this threat in his paper. He suggests that each merchant in the system would have a unique ID number. The 1's and 0's that the merchant uses in the payment protocol would be partially random choices as I described and partially based on the unique ID. Since all ID's are different this would guarantee that any two merchants would use different patterns of 1's and 0's even if they were cheating.