From: David Wagner <daw@cs.berkeley.edu>
Date: Mon, 1 Apr 1996 03:05:03 +0800
To: cypherpunks@toad.com
Subject: Chaumian ecash without RSA
Message-ID: <199603311610.IAA10786@joseph.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


I've always seen Chaum's anonymous ecash system described in terms of RSA.
RSA has this ungainly patent which probably will be around for quite some
time, yet the Diffie-Hellman patent expires pretty soon.  With that motivation,
here's a Chaumian anonymous ecash protocol based on Diffie-Hellman.

Take a publicly known group G and generator g; breaking Diffie-Hellman and
taking discrete logs in this group should be hard.  For instance, G might
be (Z/pZ)^*, the integers modulo a prime p.

The bank picks a secret value k, and publishes g^k.

To withdraw a coin, Alice picks an x, sets
	y = x | hash(x),                [  | is concatenation  ]
chosen so that y is in G.  Alice chooses a random secret blinding factor b,
sends to the bank
	A->B: y g^b,
and the bank returns
	B->A: (y g^b)^k,
debiting Alice's account.

Note that this is a (blinded) Diffie-Hellman key exchange with public
exponentials g^k and y g^b; the bank returns the exchanged "secret".

Alice unblinds this value, computing
	z = (y g^b)^k (g^k)^{-b}
and now c = (x,z) is a coin in the digital cash system.  Note z = y^k.

We use the traditional online clearing protocol; to deposit the coin, a
shop S sends
	S->B: x, z.
The bank checks to make sure the coin hasn't already been spent, and then
computes
	y = x | MD5(x),
checking whether y^k = z.  If equality holds, and the coin hasn't already
been spent, then the bank credits S's account and adds the coin to the
list of spent coins.

This is just the same old Chaum anonymous ecash protocol, except that I've
replaced the RSA operations by Diffie-Hellman ones.  It's a lesser-known
fact that you can blind a Diffie-Hellman key exchange just as you can blind
a RSA signature.

The security of this protocol depends on the intractibility of breaking
Diffie-Hellman.  In particular, given public exponentials g^k and y = g^m,
for k,m unknown, it must be impossible to compute g^{km} = y^k.  Furthermore,
this protocol depends on the hash function being one-way and possessing no
interactions with Diffie-Hellman or modular exponentiation.

Comments?