[2906] in cryptography@c2.net mail archive
Anonymous cash without blinding
daemon@ATHENA.MIT.EDU (lcs Mixmaster Remailer)
Mon Jul 6 14:17:38 1998
Date: 6 Jul 1998 18:00:03 -0000
To: cryptography@c2.net
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Here is an electronic cash system similar in flavor to Dan Simon's, but
truly anonymous. It is not efficient enough to be used widely, however.
As with Simon's method, it does not use blinding.
To withdraw a coin, the client creates a random x, and sends f(x) (where
f is a one-way function) to the bank. The bank signs f(x) and debits the
client's account, sending sign(f(x)) back to the client.
To deposit a coin, the client supplies g(x), where g is a different one
way function than f. It also supplies a zero knowledge proof that it
knows an x such that (1) g(x) is the value being deposited, and (2)
it knows sign(f(x)). This is done of course without revealing x or
f(x).
The deposit is therefore unlinkable to the withdrawal, and anonymity is
achieved, without blinding. g(x) is stored by the bank and is used to
prevent double spending.
There are a couple of ways payment could be done. One possibility is
for the buyer to give the seller x and sign(f(x)), so that the seller
can just do the deposit as described. However this allows the seller
to collude with the bank and learn the identity of the buyer.
Another possibility is to have the buyer give the seller the proof of
knowledge of x, without revealing x. This could be a non-interactive
zero knowledge proof, which the seller can then show to the bank to
do the deposit. However this allows the buyer to collude with the bank
and learn the identity of the seller.
The collusion problem (which is also present in Chaum cash) can be solved
by allowing anonymous exchanges, as with Simon's scheme (and as often
discussed in the context of Chaum cash).
The problem is of course that general-purpose zero knowledge proofs
are slow. The state of the art for general purpose zero knowledge
proof systems is that the requisite proofs would require one to three
hours of computation on a workstation and roughly tens of megabytes
of communication. This is obviously too large for routine use with
payment systems using current technology.
However, some things can be proven quickly. There has been considerable
work on proving relations among discrete logs of values in an efficient
way. Camenisch and Stadler have some recent papers which show how to
construct efficient proofs of this type, although none seem quite suitable
for this application. http://www.brics.dk/~camenisch/publications.html
Perhaps variants on these ideas can be used to construct efficient
anonymous cash systems without blinding.
