Why we still don't use digital cash

[lcs Mixmaster Remailer]

George writes:

> Chaum's proposals always seemed a little
> weird to me,  I'd be amazed if there wasn't a perfectly
> good way to implement dc without stepping on his patents.

Probably so, see the references in the recent critique of the Wired
article.

> If you look at the process of obtaining digital cash abstractly,
> I give you a bag of money,  you give me a bag of tokens I can
> use to spend in shops,  it seems to me that there are in principle
> two general sorts of ways that I can maintain my anonymity.
> ...
> 2) Just make it so you don't see my face when I get the bag of
> tokens.
>
> This seems a lot more straightforward and natural to me.

Well, the problem is that to exchange cash for tokens, you need a
way of sending cash to the bank.  But if this exchange is to be done
electronically, then that means you are sending e-cash.  But your "tokens"
*are* e-cash!  So your description shows how to get anonymous e-cash,
but only if you already start with anonymous e-cash.

What you can do is to do an initial withdrawal of e-cash,
non-anonymously, then do anonymous exchanges for fresh e-cash
tokens.  This is essentially the approach of Dan Simon of Microsoft,
which is unfortunately patented, US05768385.  It is described at
http://www.research.microsoft.com/crypto/papers/ecash2.ps.  Here is some
analysis from June, 1998 cypherpunks post:

: The basic idea is that to withdraw money, you select a random x and
: send f(x) to the bank, where f() is a one way function.  The bank debits
: your account and sends you sign(f(x)), a signature on f(x).  To deposit
: the money you need to supply both x and sign(f(x)).  By requiring you
: to exhibit x, sign(f(x)) is no longer sensitive, so you don't have to
: encrypt your communications with the bank.
: 
: To pay someone else, you send them x and sign(f(x)).  (This transaction
: does have to be encrypted, because it includes x.)  Now, if he just
: deposits this to his bank account, the transaction would not be anonymous
: since the bank would recognize sign(f(x)) as being associated with a
: specific withdrawal.
: 
: Instead, the recipient can do the standard anonymous-exchange trick,
: long discussed in the context of Chaumian cash.  He anonymously sends x,
: sign(f(x)) to the bank along with a new "withdrawal request" created by
: randomly choosing y and sending f(y) to the bank.  The bank exchanges
: the coin, sending sign(f(y)) back anonymously.  Now this second party
: can spend his coin y, sign(f(y)) with someone else, who does a similar
: exchange.  (The obscure "claim 27" quoted in the patent excerpt described
: this process in the case where change is being made, and multiple coins
: are received in exchange for one deposited.)
: 
: Simon's protocol has several problems.  First, the whole business
: about sending around the secret values x and y is largely pointless.
: Since you need secure communications for some steps, you might as well
: assume you have them for all of them.  In that case you could just send x
: to the bank and get it signed (forcing x to be of some restricted form),
: and then let sign(x) represent the coin.  Everything works the same way.
: 
: Second, it is not really anonymous.  Note that no blinding is used.
: Although the bank does not know who turned coin x into coin y, it does
: know which coin was exchanged for which.  Suppose it goes through, say,
: three steps before being deposited.  Coin x is withdrawn, anonymously
: exchanged for y, which is anonymously exchanged for z, which is
: later deposited.  The bank knows who withdrew x and who deposited z.
: It doesn't know who the intermediate parties were, which is the extent
: of the anonymity.  If the coins are circulating among a tightly knit
: group this could completely compromise anonymity as the bank gathers
: data on payment patterns.
: 
: Furthermore, it is not clear how long these transfer chains will be
: in practice.  It may be in many cases that a coin is withdrawn and
: then immediately deposited.  That's how cash businesses work these
: days.  For that case, Simon suggested (at Crypto) that the recipient
: could perform some "dummy exchanges", so it would look to the bank
: like it had gone through some third parties.  But if the bank suspects
: this is going on, it is ineffective.  The bank sees a withdrawal by
: Alice and a deposit by Bob, after some intermediate transfers, and
: it may speculate that Alice paid Bob directly.  Again, sufficient
: statistical data can be built up over time to correlate transfers and
: reveal these patterns.
: 
: This whole effort is an attempt to get anonymous payments without
: violating Chaum's patents.  But the anonymity is extremely weak, and
: the use of one way functions makes the protocol look more sophisticated
: than it is.  Ultimately, this is just a matter of banks issuing signed
: tokens to represent coins, with people being able to exchange them for
: new ones anonymously.  As such, the idea has been discussed since the
: early days of cypherpunks and would not be patentable.  Simon had to dress
: it up with the one way functions to get something that looks different,
: but ultimately it is nothing new or interesting.