Formal Treatment of Privacy-Enhancing Credential Systems


Jan Camenisch (IBM Research -- Zurich), Stephan Krenn (AIT), Anja Lehmann (IBM Research -- Zurich), Gert L. Mikkelsen (Alexandra Institute), Gregory Neven (IBM Research -- Zurich), and Michael Ø. Pedersen (Miracle A/S)


Privacy-enhancing attribute-based credentials (PABCs) are the core ingredients to privacy-friendly authentication systems. They allow users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion while revealing only a subset of the attributes. In practice, PABCs typically need additional features like revocation, pseudonyms as privacy-friendly user public keys, or advanced issuance where attributes can be ``blindly'' carried over into new credentials. For many such features, provably secure solutions exist in isolation, but it is unclear how to securely combined them into a full-fledged PABC system, or even which properties such a system should fulfill.
We provide a formal treatment of PABCs supporting a variety of  features by defining their syntax and security properties, resulting in the most comprehensive definitional framework for PABCs so far. Unlike previous efforts, our definitions are not targeted at one specific use-case; rather, we try to capture generic properties that can be useful in a variety of scenarios. We believe that our definitions can also be used as a starting point for diverse application-dependent extensions and variations of PABCs. We present and prove secure a generic and modular construction of a PABC system from simpler building blocks, allowing for a ``plug-and-play'' composition based on different instantiations of the building blocks. Finally, we give secure instantiations for each of the building blocks.


22nd International Conference on Selected Areas in Cryptography, SAC 2015 (

Place and Date

Mount Allison University, Sackville, New Brunswick, Canada, August 12th – 14th, 2015

Publication Reference

Jan Camenisch, Stephan Krenn, Anja Lehmann, Gert L. Mikkelsen, Gregory Neven, and Michael Ø. Pedersen, "Formal Treatment of Privacy-Enhancing Credential Systems", Selected Areas in Cryptography - SAC 2015, Sackville, New Brunswick, Canada, August 12–14, 2015.


   Author    = {Jan Camenisch and Stephan Krenn and Anja Lehmann and Gert L. Mikkelsen and Gregory Neven and Michael {\O}. Pedersen},
   Title     = {{Formal Treatment of Privacy-Enhancing Credential Systems}},
   Booktitle = {Selected Areas in Cryptography - {SAC} 2013, Sackville, New Brunswick, Canada},   
   Year      = {2015}, 
   Publisher = {Springer}