[2855] in cryptography@c2.net mail archive
Re: Microsoft patent
daemon@ATHENA.MIT.EDU (Anonymous)
Thu Jun 25 14:37:19 1998
Date: Thu, 25 Jun 1998 18:12:01 +0200
From: Anonymous <nobody@replay.com>
To: cryptography@c2.net
Bob Hettinga forwarded:
> And now for something completely different: Microsoft recently received
> a U.S. patent for an untraceable electronic cash protocol. Check out
> http://www.patents.ibm.com/details?patent_number=5768385.
This is basically Daniel Simon's "anonymous" electronic cash protocol
from Crypto 96. The protocol in less legalistic terms is described in
http://www.research.microsoft.com/crypto/papers/ecash2.ps.
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.
