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@wasabisystems.com