From: Hal <hfinney@shell.portal.com>
Date: Sun, 10 Sep 95 12:13:27 PDT
To: cypherpunks@toad.com
Subject: Re:  Brand e-cash implementation?
Message-ID: <199509101912.MAA07700@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


Brands has a web page at <URL:http://www.cwi.nl/~brands>.  I don't know
of any implementations of his technology.  The last time I heard from him
was early this year and at that time he apparently was still looking for
backers.

BTW he has a new paper out as of July 95, available above, which
discusses some problems and attacks on some earlier papers.  He had
proposed a notion called "secret key certificates" in which some
problems have been found.  Basically a secret key certificate is just
like a public key certificate (a signature by someone on a public key
as in PGP) except that realistic-looking but ultimately worthless
secret key certificates can be faked up (simulated) by anyone.  No one
can distinguish a fake secret key certificate from a real one.
However, they are worthless because the faking process requires you to
choose a random public key, and you can't figure out what the secret
key is.

Brands has (re)expressed his digital cash technology in terms of these
secret key certificates.  But Berry Schoenmakers of CWI has shown a way
in which a faked-up secret key certificate can be used to spend a coin
which was never withdrawn.  However, to do so, you have to go through
the withdrawal protocol in a particular incorrect way.  You force the
bank to act as an "oracle" for a certain discrete log problem when you
do the withdrawal.  The data you get from the incorrect withdrawal
protocol allows you to spend the fake coin.

So this is not actually a dangerous attack, because you in effect have to
withdraw a coin in order to spend the fake one.  You can't make any money
from it.  Still it was not anticipated and that is a bit worrisome.  I'm
not sure why Brands' various proofs of correctness (which are one of the
big selling points of his technology) did not anticipate this attack.

(In effect this is a different form of a blind signature than what
Brands planned for, since you withdraw one thing and get another.  I was
thinking Brands should write this up under the title "Unanticipated
Blinding for Signatures", a pun on Chaum's "Blinding for Unanticipated
Signatures", one of his credential papers.)

Brands has a workaround to prevent this attack, but it hurts the
provability of his scheme.  "A rigorous prove [sic] of the effectiveness
of the measure may be hard to provide, though, since one must hereto
prove that the CA cannot be used as an oracle to perform the
cryptographic action in the showing protocol with respect to simulated
public keys."  So this may be a setback in Brands' attempts to get his
thesis finished and accepted.

As for the question of whether any digital cash scheme offers "true"
anonymity, I think you have to be more specific.  Virtually all cash
advocates will claim that they can offer this.  In the debate I had
earlier with Lucky Green I argued that Chaum's ecash does offer a certain
kind of anonymity.  The extent to which it does not is largely not
technical but a product of not allowing anonymous bank accounts.  With
anonymous accounts Chaum's technology offers as much anonymity as any
system that I have studied.

There is one technical problem with Chaum's ecash which Lucky mentioned,
but I believe it applies to all systems.  That is that the spender of the
cash can "mark" it or at least recognize it when it is later deposited.
If the spender wanted to attack the receiver of the money and it is
deposited non-anonymously then this will be a problem.

However, as we discussed here several months ago, Chaum's paper
"Transferred Cash Grows in Size" from a recent Crypto proceedings shows
that by colluding with the bank a payor of cash can recognize it at any
later stage of the payment chain.  So this kind of anonymity is very hard
to achieve.  Chaum's paper applied to off-line cash, though, so perhaps
an online system could do it.  But you'd have to blind the coins twice,
once when they pass from bank to payor and once when they go from payor
to payee, and I don't see how to do this.

Hal Finney