E-Cash is supposed to be the digital equivalent of real cash. The idea is that Alice can withdraw money from the bank and spend it anonymously. Later, when the bank looks at its database of deposits and withdrawals, it shouldn’t be able to link any deposit with any withdrawal.
Of course there is a problem with this scenario. Suppose Alice withdraws a digital dollar and then spends it twenty-gadzillion times. Since Alice stores the digital dollar on her computer, nothing stops her from making those twenty-gadzillion copies.
The standard solution is to embed Alice’s identity into every e-dollar she withdraws. If she spends the same e-dollar more than once, the bank can look at the two deposits and determine Alice’s identity. For example, suppose we associate a straight line with each e-dollar. The y-intercept is Alice’s identity. The slope is chosen at random during withdrawal. If Alice spends the e-dollar once, she reveals one point on the line. That’s not enough to learn anything about Alice’s identity. (Try it at home: point your finger on any random spot on the monitor and count the number of straight lines between your finger and the left hand side of the screen). If Alice spends the e-dollar a second time, the bank can “connect the dots” and follow the line to the y-intercept.
The standard objection is that even if Alice is identified after the fact, Alice fly to the Bahamas long before the bank catches up. The potential damage is just not worth the on-line privacy goodness.
These practical obligations did not deter me from writing my Ph.D. thesis on e-cash. One of my favorite results was showing how to do secure fair exchange of e-cash. When Alice sends Bob her e-dollars (ok, now that we’re getting technical, I should call them by their official latin name, e-coin, which is easy to remember, because it is like e-coli, only it corrupts you soul and not your stomach), she wants to make sure she gets some sort of receipt back in return. Bob doesn’t want to send a receipt until he gets paid. The solution is to do alot of math in algebraic groups of prime order.
Things get even more interesting when Alice needs to pay more than one e-coin. Now we do a cool trick and hide all the e-coins in a polynomial of degree N. Then Alice gives Bob N points on the polynomial. Just as in the straight line example, Bob doesn’t learn anything about the e-coins because he only has N points. He needs N+1 points to interpolate (english: compute) the polynomial. Then Alice and Bob run the Asokan, Shoup and Waidner fair exchange algorithm for the magic N+1th point. Alice gets a receipt. Bob gets N+1 points. He interpolates, and voila! out comes the pot of e-cash.
You can read more about Endorsed E-Cash in my IEEE Security and Privacy 2007 publication.