CDR: ecash, cut & choose and private credentials (Re: Jim Bell)

[Adam Back]

[Hey Hal, what happened to your Chaum's ecash description?  Can't find
it to link to].

Anonymous wrote:
> Ray wrote:
> > Even if she provides enough 
> > tokens to completely populate the cut-and-choose protocol, 
> > those tokens still have to have splits of valid identification 
> > information for somebody in them - and giving them all to 
> > Bob so that Bob could complete the protocol with the bank - 
> > would imply that Bob is privy to that information.
> 
> There are far more efficient offline systems than cut and choose.
> You need to get past the A's and into the B's and C's in your
> protocol list.  Check more recent work from Brands and Chaum.

Here's a short description of Chaum's [2] ecash and credentials vs
Brands' [1] more general and flexibile private credentials and ecash.

So as both anonymous and Ray know cut and choose refers to the method
of encoding identity into coin.  The basic problem is that Chaum's
blind signature doesn't the signer see what he is signing.

So cut and choose is just the user encodes identity in a number of
candidate coins, and the bank chooses one at random and the user must
reveal the rest.  This allows tunable probability of cheating (not
encoding identity in the chosen coin).  This is done in such a way
that a coin showing protocol will reveal the identity if the coin is
spent twice (due to random values chosen by the merchant resulting in
two simultaneous equations with two unknowns -- one of them the
identity).

Cut and choose is computation and communication inefficient.

Brands' private credentials stuff uses a technique he calls secret key
certificates to allow the issuer and the user to both see the
attributes being signed.  The user ends up with a certificate on the
attributes and the ability to prove the validity of the certificate
during a certificate showing protocol.

The user can also choose to selectively disclose attributes during
disclosure, for example if there are two attributes he can reveal one
(the coin denomination) and not the other (his identity).

With Chaum's ecash you have to use the cut and choose protocol which
is inefficient, with Brands' protocol the user and the issuer engage
in a protocol with 3 moves (Discrete Log based variant) or 2 moves
(RSA based variant) which is both computation and communication
efficient.

With Chaum's ecash you have to encode the coin denomination by having
a separate public certification key for each denomination.  You don't
have to do this with Brands' private credentials, as you can put this
in an attribute.

Also the number of attributes is arbitrary, so if it makes sense to
have more attributes in the general private credential case, you can.

(For example sex, age, nationality, passport credential, etc. you can
reveal any combination you choose after certification.)

You can also show fairly arbitrary boolean expressions involving the
attributes and not reveal anything other than the truth of the
expression.  (Eg. Female US citizen over 60 or Male Canadian citizen
under 18, and not reveal sex, citizenship or age).

The certificates are linkable (ie the verifier or merchant can tell
that you are the same pseudonymous person who last showed the
certificate), because there is a public key chosen by the user and the
public key is revealed during the show protocol.

There is also a refresh protocol where the user can give a used
certificate and get a fresh certificate without having to show the
attribute vales of the certificate -- the certifier just knows he is
certifying the same as last time.  The refreshed cert would be
unlinkable at show time from the original cert.

For ecash purposes you can use private credentials to make both
offline and online cash.

So private credentials are nice and flexible for building generalised
private credentials, and also more flexible and so allow you to do
some things more efficiently, and do some things not directly possible
with Chaum's credentials.

Unfortunately both Brands' and Chaum's ecash and credential schemes
are patented.  David Wagner et al also had some ideas about an ecash
coin [3] composed roughly of a public key based MAC (ie the user can't
verify the validity of the coin directly -- only the bank can do
that), plus a zero-knowledge proof that the bank hasn't marked the
coin.  This may be unpatened in that it's not directly a certificate,
it's a MAC, plus a zero-knowledge proof so it seems like a fairly
different process.  I don't think you can do efficient offline ecash
with Wagner et al's mechanism -- I'd guess it's more comparable with
the functionality offered by Chaum's blind signature.

There is a high level white paper describing the applications of
Brands' private credentials and comparing to Chaum's credentials:

at the bottom Brands Private Credentials White Paper.

[1] http://www.zeroknowledge.com/media/default.asp

[2] Hal Finney used to have a description of Chaum's protocol on rain.org
but he's at www.finney.org/~hal/ now and I can't find the link.  (Cc'd
to see if he still has it.)  Actually I did once see a description of
Brands stuff by Hal also... still have that too?

[3] Ben Laurie has a paper describing Wagner et al's MAC + ZKP ecash /
credential protocol as theory2.pdf.

http://anoncvs.aldigital.co.uk/lucre/

Adam

Disclaimer: As always my comments are my own.