Re: "patent free(?) anonymous credential system pre-print" - asimpleattack and other problems
Hello Jason: >"Page 193 and 210 do talk about having an identifying >value encoded in the credentials which the holder can >prove is or isn't the same as in other credentials. However, >the discussion on page 193 is with respect to building >digital pseudonyms" No, not at all. The paragraph on page 193 that I referred to is the one starting with "In some PKIs it is desirable that certificate holders can anonymously prove to be the originator of several showing protocol executions." It _preceeds_ the paragraph on digital pseudonyms, which starts with "A special application of the latter technique are credential systems in which certificate holders [...] establish digital pseudonyms with organizations". >I can think of ways in which this feature might be leveraged to >create otherwise-unlinkable sets of credentials from different >(distrusting) CAs, but it's never addressed directly that I can >see, and would need some specifics filled in." There are no specifics to be filled in, the paragraph on 193 states everything there is to it. If the credential holder engages in several showing protocols (whether in sequence or in parallel, and regardless of whether at the same time or at different times -- the paragraph applies to any situation), all that is needed to prove that no pooling is going on is the abovementioned proof that the credentials all contain the same hidden identifier. Note that the prover can _hide_ this identifier, thereby allowing him to prevent linkability with other showing protocol executions for which no link needs to be established. Of course, the technique also works if there are many Cas. The user can even prevent the CAs from learning the built-in identifier that is central to all (or a subset of) his/her credentials. (A special CA could issue restrictively blindeded versions of the user's "identity", which the user then submits to different Cas who encode it into the certificates they issue.) >Page 211 of your book talks about discouraging lending, which doesn't >help in the case when Bob answers in Alice's behalf when she shows his >credentials. Discouraging lending is not the same as preventing pooling. The lending prevention technique was not intended to address pooling, the technique on page 193 does a much more effective job at that. However, in your approach, what prevents me from giving my credentials to someone else who then uses them to gain access to a service without needing to pool in any other credentials than the one I lent to him? Note also that when all credential attributes are specified within the same certificate, and the verifier requires authorization information to be contained within a single attribute certificate, pooling is inherently prevented. >What do you mean by "forced to leave behind digital signatures"? There is no zero-knowledge variant of your protocol; the verifier ends up with undisputable evidence (towards third parties) of the transaction, and in particular of which attribute values have been shown by the credential holder. Any digital signatures that are made by certificate holders can be added to their dossiers; they form self-signed statements that cannot be repudiated, proving to the whole world who is the originator of a message and possibly what information they were willing to give up in return for a service. Doing a zeroknowledge variant of your proposal requires one to prove knowledge in zk of various elements rather than showing them in the clear; this requires extrmely inefficient zk techniques, such as for proving knowledge of a pre-image under a specific hash function. >I'll expand my related work section to point out that your system and >others have lots of features which my system doesn't attempt to provide. >My apologies if my terse treatment mischaracterized your work. I realize that many of the features of my work are described in a very dense manner in the book, and therefore it is easy to overlook them. For example, on the same page 193 there is a sentence "Using our techniques it is also straightforward for several certificate holders to jointly demonstrate that their showing protocol executions did not all originate from the same certificate holder, or for one certificate holder to show that he or she was not involved in a fraudulent transaction." The same applies to my describtion of the simple hash selective disclosure technique on page 27, which only gets two sentences, and many others techniques/functionalities. The only excuse I have for this is that the book is a minor revision of my PhD thesis, and so the technical parts had to be targetted towards an expert audience; while skilled cryptographers will indeed find the dense statements more than sufficient, and may even consider some of them as trivial applications of the general techniques, I can see that this may not always be the case for readers in general. Good luck with your research! Stefan Brands
Re: "patent free(?) anonymous credential system pre-print" - a simpleattack and other problems
(Re: my paper at http://eprint.iacr.org/2002/151/ ) Stefan Brands wrote: > - The system is subject to a simple attack. The problem lies with the > multiplication of the hashes. Let's take the Chaum blinding as an [...] (For our readers at home, that was the vulnerability I mentioned in my response to Adam). [...] > - My work certainly does provide for "revocable anonymity" and "pooling" > prevention. For pooling protection, see paragraph 2 on page 193, > section 5.11 page 210 paragraph 2, and section 5.5.2 on page 211. For [...] When I speak of pooling credentials, I'm talking about Alice presenting her student ID along with the senior-citizen ID Bob loaned her (or for which Bob is answering clandestine-ly), as if they both belonged to her, in order to get both discounts on her movie tickets. In my system, you get your credentials issued in a set associated with a single identity, and it's hard for Alice to get Bob's credentials included in one of her own sets. It works even if the CAs don't trust each other. Page 211 of your book talks about discouraging lending, which doesn't help in the case when Bob answers in Alice's behalf when she shows his credentials. In any case, section 5.5.2 only adds liability to pooling - it doesn't prevent it mathematically. (As to lending in general, I think you're right that discouragement may be the best we can do). Page 193 and 210 do talk about having an identifying value encoded in the credentials which the holder can prove is or isn't the same as in other credentials. However, the discussion on page 193 is with respect to building digital pseudonyms, and the discussion on page 210 seems to be about showing that values are *not* the same, following a scenario in which a pseudonym holder has been identified as a misbehaver. I can think of ways in which this feature might be leveraged to create otherwise-unlinkable sets of credentials from different (distrusting) CAs, but it's never addressed directly that I can see, and would need some specifics filled in. Nonetheless, I'll point out in my paper that it's a possibility in your system. > - The proposed hashing technique for selective disclosure was introduced > by myself in 1999. Quoting from page 27 of my MIT Press book titled [...] Pages 27 and 184 of your book are now both referenced in my section on selective disclosure. > - More seriously, the simple hash technique has numerous drawbacks, as I > explain on page page 27 of my MIT Press book, in the very same > paragraph: "Although certificate holders now have some control over > which attributes they reveal to verifiers, they are forced to leave > behind digital signatures. ... [...] What do you mean by "forced to leave behind digital signatures"? > ... Worse, nothing prevents the CA and others from tracing and linking all > the communications and transactions of each certificate holder." ... [...] This is of course overcome in my system with blinding and cut-and-choose. > [ > Snipped discussion of features which Brands' system has and my system > doesn't: boolean formulae, lending prevention, limited show, > wallet-with-observer, discarding protection, anonymous recertification / > updating, multi-application certificates, etc. > ] From my response to Adam Back: I'm glad that was clear in my text. This isn't a do-everything system like Brands' - rather, it has 2 aims. 1: show how to do simple selective disclosure in a Chaum/Fiat/Naor-like system using X.509v3 credentials as a base, and 2: show how to link credentials from multiple issuers to the same identity without compromising anonymity. And actually, I forgot to mention the original goal of my paper, which was to create a system not encumbered by your patents or Chaum's. I'll expand my related work section to point out that your system and others have lots of features which my system doesn't attempt to provide. My apologies if my terse treatment mischaracterized your work. -J
Re: patent free(?) anonymous credential system pre-print
Stefan Brands writes regarding http://eprint.iacr.org/2002/151/: > The paper shows some promise but, apart from being insecure, has other > drawbacks that should be addressed: > > ... My work... introduced by myself... my MIT press book... > > In addition to various other drawbacks pointed out by of Dr. Adam Back > (see [EMAIL PROTECTED]/msg02752.html), > the proposal does not offer a wallet-with-observer mode, discarding > protection, anonymous recertification / updating, multi-application > certificates, etcetera. And balanced against all these numerous shortcomings, there is one inescapable, overwhelming fact: THE AUTHORS ARE MAKING THE FRUITS OF THEIR LABOR AVAILABLE FREELY FOR THE WORLD TO USE. With all of your patents, and your writings, and your self-promotion, how many people are using your certificates in the real world? Think how much you could have accomplished, how much of a difference you could have made, if you had been willing to sacrifice the hope of great riches. Instead you have followed in the footsteps of your mentor Chaum, and both of you have withheld your talent from the world. What is it about cash and credential systems that everyone who works in the area thinks they should patent their results? All you have accomplished is to make sure that no implementations exist! What good are your great ideas if no one can use them? Look at Chaum! Is that where you want to be in 20 years? Bitter and barren? Cut off from the cryptographic community? Reduced to publishing via the government patent office? That's no life for a great mind. Creativity demands interaction with an active and vital intellectual community. You have to give in order to take. Building walls around your intellectual property shuts others out even as you shut yourself in. If you really want to accomplish something meaningful, rather than continuing to hype and shill for a system which no one can use without entering into delicate financial negotiations, why not make it available on some basis for people to experiment with? Maybe a non-commercial, open-source GPL implementation could be a starting point. There is considerable interest in reputation systems among the P2P community and credentials could be a part of that. You can still protect your commercial interests while letting people get familiar with the technology by making a non-commercial library available. That's just one possibility. The point is, your ideas are going nowhere using your present strategy. Either this technology won't be used at all, or inferior but unrestricted implementations will be explored, as in the recent work. If you want things to happen differently, you must change your strategy.
Re: patent free(?) anonymous credential system pre-print
Some comments on this paper comparing efficiency, and functionality with Camenisch, Chaum, Brands. On Tue, Oct 29, 2002 at 11:49:21PM +, 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."
patent free(?) anonymous credential system pre-print
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. 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! -J
