I'm trying to learn about anonymous credential systems. I started with Lysyanskaya's thesis, which gives an outline of how to build an AC system given some particular primitives (signature scheme, commitment, etc.), and then looked at some papers building those particular primitives. I have also come across some papers (one using RSA assumptions and one using bilinear pairings) which don't follow Lysyanskaya's "formula" but still manage to form a valid AC system.

I can follow along in each of the papers from one line to the next, but I still don't exactly understand what makes it "tick". Can someone suggest a way to better understand this? Of course, the various assumptions (pairings, discrete log, RSA, etc.) offer some way of "hiding" information to achieve anonymity. But I don't really see what property exactly is necessary to make the system work.

Apologies if this question is vague. Can someone suggest what to do to better understand what makes these systems work? I fail to see the commonalities between the schemes.


1 Answer 1


I'll try to give some high-level intuition of the used construction paradigms in my answer below. First, note that we distinguish between one-show and multi-show anonymous credential schemes.

For one-show credential schemes, you essentially have that multiple showings of the same credential can be linked to each other, while showings are unlinkable to the issuing. Those schemes are typically instantiated using Blind signatures (e.g. Brands' credential scheme, or Baldimtsi and Lysanskaya's anonymous credentials light). Essentially, a Blind signature scheme is an interactive protocol where the signer does not learn the signed message. The issuer usually signs a blinded version of a commitment to the attributes of the user and the user then uses the unblinded, signed commitment together with a proof of knowledge upon showing. From a very high-level point of view, the property that the signer does not learn the signed message helps to achieve unlinkability between issuing and showing.

For multi-show credential schemes you essentially have that even multiple showings of the same credential are unlinkable. Those schemes are typically instantiated using a signature scheme where the signatures can be publicly randomised and which is compatible with zero-knowledge proofs. The issuer signs commitments to the attributes and upon showing one randomizes the signature and proves knowledge of the signature and the attributes (only the attributes which should be shown get revealed). The most prominent instantiations of this paradigm are Camenisch and Lysyanskaya's anonymous credential schemes (both the RSA variant and the pairing variant). Recently, another paradigm to construct multi-show anonymous credentials was introduced by Hanser and Slamanig. The use signature schemes where signatures and signed messages can be publicly randomised, together with a compatible commitment (i.e., one which still binds the committed message even when re-randomised). Here, the issuer issues a signature on commitments and showing amounts to re-randomizing the signature and the signed message and opening the commitment with respect to the attributes to be shown (they also require a simple zero-knowledge proof to guarantee freshness).

  • $\begingroup$ Thank you. So it seems like both require the signing of a commitment, but the main difference is whether the signature can be rerandomized (multi-show) or not (one-show). $\endgroup$
    – NNN
    Feb 21, 2018 at 14:07
  • $\begingroup$ From a high-level perspective, I would say yes. $\endgroup$
    – dade
    Feb 21, 2018 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.