Paper 2015/580

Composable & Modular Anonymous Credentials: Definitions and Practical Constructions

Jan Camenisch, Maria Dubovitskaya, Kristiyan Haralambiev, and Markulf Kohlweiss


It takes time for theoretical advances to get used in practical schemes. Anonymous credential schemes are no exception. For instance, existing schemes suited for real-world use lack formal, composable definitions, partly because they do not support straight-line extraction and rely on random oracles for their security arguments. To address this gap, we propose unlinkable redactable signatures (URS), a new building block for privacy-enhancing protocols, which we use to construct the first efficient UC-secure anonymous credential system that supports multiple issuers, selective disclosure of attributes, and pseudonyms. Our scheme is one of the first such systems for which both the size of a credential and its presentation proof are independent of the number of attributes issued in a credential. Moreover, our new credential scheme does not rely on random oracles. As an important intermediary step, we address the problem of building a functionality for a complex credential system that can cover many different features. Namely, we design a core building block for a single issuer that supports credential issuance and presentation with respect to pseudonyms and then show how to construct a full-fledged credential system with multiple issuers in a modular way. We expect this flexible definitional approach to be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
(Fully) structure preserving signaturesvector commitmentsanonymous credentialsuniversal composabilityGroth-Sahai proofs
Contact author(s)
markulf @ microsoft com
2015-06-21: received
Short URL
Creative Commons Attribution


      author = {Jan Camenisch and Maria Dubovitskaya and Kristiyan Haralambiev and Markulf Kohlweiss},
      title = {Composable & Modular Anonymous Credentials: Definitions and Practical Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/580},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.