How digital cash works.

Most people don't realize what amazing kinds of systems cryptographers have come up with over the years. Here's a good example of a way to create a mathematically-based digital cash system with a lot of desirable properties: you can't counterfeit coins without getting caught, we don't have to rely on a central database being up all the time, and best of all, as long as you don't try to cheat, your privacy is mathematically assured!

Secure, anonymous digital cash is real and has been implemented in the real world. In fact it's one of the things that got me into cryptography years ago. It's mathe-magical!

As others have pointed out, online, trusted third party (TTP) systems are an easy way to solve lots of security problems. Tamper-resistant devices are another "easy out". But in this case, there's a purely mathematical solution.

We have two goals: anonymous cash, and cash that prevents double-spending without an on-line authority.

Anonymity: an anonymous coin is one which you can withdraw from the bank, but which the bank can't link to you when you spend it. Sounds impossible, doesn't it? Blind signatures to the rescue. They allow the bank to sign the banknote using its private key without seeing the contents of what it's signing.

If you're scared of math, skip this part and trust me that it's possible to sign a message without seeing what it is. Otherwise, here's the math for how blind signatures work in RSA:

In ordinary RSA, e is the public exponent, d is the private exponent, and m^(ed) = m (modulo n, the signer's modulus) for all suitable messages m. A signature on m can be computed as m^d (mod n).

If I want you to sign m without knowing what it is, I pick a random r and compute r^e. I send you m*r^e and you sign it, returning (m*r^e)^d = m^d*r^(ed) = m^d*r. I divide out r and am left with m^d, the signature for m. You don't know r, so you have no idea what m is.

Okay, done with math for now.

Now, if the bank only uses d to sign, say, $1 coins, then it doesn't care what I chose for m, so it doesn't mind signing it blindly. m just becomes the serial number for the bill, and I pick it randomly each time. Now, I'm perfectly free to repeat a value of m, but the only person that hurts is me, since I'm just left with two copies of the signed bill.

When I want to spend the bill, I present m and m^d (the bill and the bank's signature for the bill) to the merchant, who verifies that it was indeed signed by the bank. He sends it to the bank while Alice waits, and they record the serial number to prevent double spending, but they have no way to link m with the blinded value m*r^e they signed earlier.

So there's anonymity. Now, to show off, we'll remove the need for the online double-spending check.

m now gets fancier. It's now a structured message having an encrypted message saying "Alice, account number: #123456789" and some other special fields. The 256-bit key k for encrypting the message is split into 2 128-bit keys k1 and k2. The special fields h1 and h2 are computed as hash(k1) and hash(k2). That is, they don't reveal what k1 and k2 are (because you can't work backward from a cryptographic hash calculation), but they let you know when you've got k1 or k2, since you can compute hash(k1) yourself and compare.

Alice creates, say, 1024 different versions of m that we'll call m0..m1023. Each has a unique k. She blinds each m with its own blinding factor b and sends them all to the bank. Each is called a "share".

Now we do what's called "cut and choose". The bank picks half of the shares at random and tells Alice to provide the blinding factors and keys for each of those. She does, and the bank verifies that each one matches the blinded values she sent earlier and that each of the keys decrypts properly, revealing Alice's name and account number.

Satisfied that she's not cheating (by putting a bogus name/account in the shares), the bank smooshes the blinded, unrevealed shares together and signs them. Alice gets back the smooshed value and the bank's signature on it, and is able to unblind each of the individual smooshed parts, leaving a completely unblinded smooshed up message and a valid signature for it.

Here's the math: assuming the bank didn't ask to see m0, m3, m4, ..., it'd give back:

((m0*b0^e) * (m3*b3^e) * (m4*b4^e)...)^d (mod n)

= m0^d * b0^ed * m3^d * b3^ed ...

As before, each b^ed = b, and she divides out the b values, leaving:

(m0*m3*m4...)^d

That is, the signature on the product of all the m values.

Still with me? Alice now has a signature on a bunch of smooshed-together shares, and the decryption keys for each share which reveal her identity. The bank's signature is valid, but the bank has never seen the unblinded value and thus won't recognize it as coming from Alice when it sees it later.

Alice goes to spend her $1 coin. She gives the signature to Bob the merchant, along with the shares m0,m3,m4... that make up the signed coin. Bob checks the signature on the smooshed up message and unsmooshes it into the separate shares. So far so good. Now, for each m, Bob picks at random and demands to see either k1 or k2 -- that is, half the key decrypting the message which would identify her. She complies, knowing that he has only half the key for any given message, so her identity is still safe. He computes the hash(k1) or hash(k2) and makes sure it matches what's in each m to make sure she isn't lying about the k values. Satisfied, he accepts the coin, and later, at his leisure, sends the day's spent coins to the bank. Alice securely deletes all the k values and goes on her way.

Now, what happens if she tries to spend the same coin twice? She gives the same signature
and m values to the other merchant, and he now demands to see one half-key or the other for each of the m values. With overwhelming probability, he asks to see the *other* half key for one of the m values the first merchant requested. Call that share m'. One merchant has one half of the key, and the other merchant has the other half. Later, when they each send their version of the spent coin to the bank, the bank will see that they're the same coin, and use the two key halves of m' to decrypt the message incriminating Alice.

Neat, huh? I simplified a lot, so if you want to get all the details, look up "Untraceable Electronic Cash" by Chaum, Fiat and Naor. Chaum actually put a fancier version of his system into practice, and I remember around 1995 downloading a Digicash "wallet" and $100 in play money to spend online in a trial run. He also had real vending machines and bus passes (iirc) in the
Netherlands, but ultimately Digicash went broke for the same reason I moved away from security: very few people actually care enough about security and privacy to pay even a little for it (and big companies like Visa have everything to lose if we have to shift to new ways of doing things).