Applying ``Crowds'' idea to anonymous e-cash.

["John Kelsey" <kelsey@plnet.net>]

-----BEGIN PGP SIGNED MESSAGE-----

[ To: cypherpunks, coderpunks, Perry's Crypto List ##
  Date: 10/09/97 ##
  Subject: Applying ``Crowds'' idea to anonymous e-cash. ]

I was thinking about applying the ``Crowds'' idea to
anonymous e-cash, and came up with what I think is a pretty
good idea.  I am interested in seeing if anyone sees either
holes in it, or ways to improve it.  I am also interested in
hearing about whether or not it has been invented before.

Crowds, for those who haven't seen it, is a way of
giving web users partial anonymity by making it impossible
to determine which member of some ``crowd'' of users did
some action (such as requesting a document).  (This is a
very rough summary--read the paper for the real analysis.)

I can see a way to do something very similar with
withdrawing electronic coins.  (This works best with
online-cleared coins), without any blinding being used.
I think this gets around the Chaum patents.  I also think it
can probably be implemented more-or-less on top of the
web-anonymizing Crowds stuff, though I may be wrong.

Here's the basic idea:

1.      A Crowd of users forms up, each wanting to withdraw
some reasonably large amount of money, such as $100, in $1
e-coins.

2.      Each user provides a public key and pays some money
(perhaps $101) into the bank.  The bank registers each
public key as belonging to a member of the crowd.

3.      Each member of the crowd is given all other members'
public keys.

4.      Each member prepares 100 one-use symmetric
encryption keys, each with a 64-bit key ID.

5.      The members organize themselves into a sort of
one-time anonymous routing network, using those public keys.
Each message to be sent is encrypted in layers (a la onion
routing), so that each member appears at least once in the
message's path.  Each message ends up at the bank,
eventually.  I'll talk about likely network architectures
later, if anyone's interested.

6.      The bank publishes something noting that it has
received N*100 keys, where N = the number of members in the
crowd.  It also publishes the hashes of all N*100 symmetric
keys.

7.      Each member digitally signs something saying that he
agrees with the keys published, he hasn't been railroaded,
etc.  Nothing proceeds until this has been published from
each member.

8.      The bank encrypts one $1 online-cleared e-coin under
each symmetric key.  It publishes a list of (key ID, encrypted
coin) pairs for all the members to receive.

9.      Each member walks away with $100 in $1 e-coins.
Nobody can prove which member got which coin.  No linking of
coins is possible.

Now, the protocol isn't all *that* important here, but the
idea is:  We interface with the traceable money world, but
grant a sort of weak anonymity for all users in the crowd.

Because the coins are online-cleared, they must be deposited
immediately.  To protect recipient-confidentiality, these
can be deposited under a pseudonym account--basically just a
one-use public key.  The recipient accumulates a bunch of
credit under that public key, and then goes through the
withdrawal procedure again to get new, weakly anonymous
coins, which he can openly deposit without direct
traceability.  (That is, the bank can still learn that
certain coins were spent at the same place, but can't
identify the final recipient of the money.  I can think of
ways to adapt this idea to unlinkability, though they
involve some implementation hassles.)

Note that multiple iterations of the withdrawal protocol
make things much stronger.  That is, there is no reason why
the participants in the withdrawal protocol have to spend
their e-coins directly--they can also use them, along with a
one-use public key, to go back into the withdrawal protocol
again.  An attacker who manages to link a given coin to a
given crowd (possible only with the help of the bank) with
some anonymous participants (who paid in with coins from
this scheme) must face the possibility that this coin could
have come from the anonymous participants--which can then be
traced to another pool, with other anonymous participants,
etc.  The attacker can't even make statistical statements
in many cases, since, if I were doing something really hot,
I'd want to go through the withdrawal process lots of times.
The bank can tell only what crowd your coins came from, not
how many times you have swapped your coins out.  If you're
willing to pay the transaction costs and time, you can
withdraw and deposit as many times as you like.

Comments?  Is this idea practical at all?  Has someone else
already done it?

   --John Kelsey, jmkelsey@plnet.net / kelsey@counterpane.com

- -----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2

mQCNAi5JqlEAAAEEAPCEHMBdDCAJ83/ibNM7ngCaaibv7YkTxcpKPjTO+WcjswFV
SEzMeTqW4MX2wSKdfcMq1HembbgfYs7v2UCnUFkLPZF19s3yUSISGcS7JxlBc3q1
7uj8W5XfBoGpgCYQqYFL2+AB/+3tLu7lU5iiEYCnevY5GQkq0kHx57Ag8goBAAUR
tCdKb2huIE0uIEtlbHNleSBKciA8am1rZWxzZXlAZGVscGhpLmNvbT6JAJUDBRAv
5uh7QfHnsCDyCgEBAQZ2A/9/OMeWK4YC+PnEzBTmgpF4WAOsVXfzRD3zAbzfNWY9
MEGo4gRF8Mr1lPHdK+0JOHp327mj9ZvYqQb1bV5fwc5dJa8/Z34VLPYlVg2rV7vJ
Hd0YnrgkoaIerbRmtP8dmZGeygeFtrk8aDCdcnMm27+tTJACl5hv2yjFO9rxBq+R
MLQpRXhwaXJlcyBmb3IgbmV3IHNpZ3MvbXNncyBvbiBEZWMgMzEsIDE5OTc=
=pOyw
- -----END PGP PUBLIC KEY BLOCK-----


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNDzFQkHx57Ag8goBAQHYkQQA0Oud9OvEX7qJdxJgGyirqzrAN4jI005p
aOVl9UnSf4XGEPj1DFMONW61HaLoh46tEDmnfMrXjI706IfwNF3HfY14FIrGe5Nb
U386CP5iztc6rpS6YsiX+prN9Q9RIXzari9uSHrmYSlGAcqa571vy7kkn7uejGBC
jv+0hnYNE1M=
=aHpr
-----END PGP SIGNATURE-----


   --John Kelsey, Counterpane Systems, kelsey@counterpane.com
 PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36