"patent free(?) anonymous credential system pre-print" - a simpleattack and other problems

[Stefan Brands]

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


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