patent free(?) anonymous credential system pre-print

[Adam Back]

Some comments on this paper comparing efficiency, and functionality
with Camenisch, Chaum, Brands.

On Tue, Oct 29, 2002 at 11:49:21PM +0000, Jason Holt wrote:
> http://eprint.iacr.org/2002/151/
> 
> It mentions how to use the blinding technique Ben Laurie describes
> in his Lucre paper, which I don't think has been mentioned in the
> formal literature, and also describes what I call a non-interactive
> cut and choose protocol which is new AFAICT.  Thanks again!

- efficiency

The non-interactive cut and choose protocol results in quite big
messages in the issuing and showing protcols to attain good security.
The user who wishes to cheat must create n/2 false attributes, and n/2
true attributes.  (True attributes being the ones he will try to
convince the CA are encoded in all the attributes).  The user can in
an offline fashion keep trying different combinations of false and
true attributes until he finds one where the attributes selected for
disclosure during issuing are the n/2 true attributes.  Then in the
showing protocol he can show the n/2 false attributes.

But C(n,n/2) grows sub-exponentially and so the user has to for
example encode 132 blinded hashed attributes to provide assurance of
work factor of 2^128 to the CA.  (C(132,66) ~ 2^128).  Without looking
in detail at what must be sent I presume each the issuing message for
a single credential would be order of 10KB.  Similar for the showing
protocol.

Computational efficiency is probably still better than Camenisch
credentials despite the number of attribute copies which must be
blinded and unblinded, but of course less efficient than Brands.

- functionality

The credentials have a relatively inefficient cut-and-choose based
issuing and showing protocol.  Brands has efficient issuing protocols
which support offline showing.  Chaum's basic offline credentials are
based on interactive cut-and-choose, but there is an efficient
variant [1].

As with Brands and Chaum's certificates if they are shown multiple
times they are linkable.  (Camenisch offers unlinkable multi-show but
they are quite inefficient).

The credentials can be replayed (as there is no credential private
key, a trace of a credential show offers no defense against replay).
Brands credentials have a private key so they can defend against this.
(Chaum's credentials have the same problem).

The credentials unavoidably leave the verifier with a transferable
signed trace of the transaction.  Brands credentials offer a
zero-knowledge option where the verifier can not transfer any
information about what he was shown.

The credentials support selective disclosure of attributes, but only
in a restricted sense.  Attributes can be disclosed with AND
connectives.  However other connectives (OR, +, -, negation, and
formulae) are not directly possible.  Brands supports all of these.

The credentials do not support lending deterence (there is no option
to have a secret associated with a credential that must necessarily be
revealed to lend the credential as with Brands).

The credentials are not suitable for offline use because they offer no
possibility for a secret (such as user identity, account number etc)
to be revealed if the user spends more times than allowed.

Most of these short-falls stem from the analogous short-falls in the
Wagner blinding method they are based on.  Of course (and the point of
the paper) the credentials do offer over the base Wagner credentials
(a restrictive) form of selective disclosure which the base
credentials do not.

On citations:

> I've submitted a pre-print of my anonymous credential system to the
> IACR ePrint server.  Thanks to all of you who responded to the
> questions I posted here while working on it.  I'd love to hear
> feedback from any and all before I sumbit it for publication;
> particularly, I want to make sure I haven't forgotten to give proper
> attribution for any previous work.

Brands discusses the salted hash form of selective disclosure in his
book [2], you might want to cite that.  He includes some related
earlier reference also.  I reinvented the same technique before being
aware of the Brands reference also -- it seems like an obvious
construction for a limited hashing based form of selective disclosure.

Adam
--
[1] Niels Ferguson, "Single Term Off-Line Coins", eurocrypt 93.

[2] Stefan Brands, "Rethinking Public Key Infrastructures and Digital
Certificates; Building in Privacy", MIT Press, Aug 2000

viz p27: "Another attempt to protect privacy is for the CA to
digitally sign (salted) oneway hashes of attributes, instead of (the
concatenation of) the attributes themselves. When transacting or
communicating with a verifier, the certificate holder can selectively
disclose only those attributes needed.  Lamport [244] proposed this
hashing construct in the context of one-time signatures."

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com