Paper 2010/496

Efficient Attributes for Anonymous Credentials (Extended Version)

Jan Camenisch and Thomas Groß


We extend the Camenisch-Lysyanskaya anonymous credential system such that selective disclosure of attributes becomes highly efficient. The resulting system significantly improves upon existing approaches, which suffer from a linear complexity in the total number of attributes. This limitation makes them unfit for many practical applications, such as electronic identity cards. Our system can incorporate an large number of binary and finite-set attributes without significant performance impact. Our approach compresses all such attributes into a single attribute base and, thus, boosts the efficiency of \emph{all} proofs of possession. The core idea is to encode discrete binary and finite-set values as prime numbers. We use the divisibility property for efficient proofs of their presence or absence. We contribute efficient methods for conjunctions and disjunctions, in addition. The system builds on the Strong-RSA assumption. We demonstrate the aptness of our method in realistic application scenarios, such as electronic identity cards and complex/structured credentials. Our method has crucial advantages in devices with restricted computational capabilities, such as smartcards and cell phones.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Earlier version in ACM CCS 2008
Anonymous Credential Systems
Contact author(s)
tgr @ zurich ibm com
2010-09-27: revised
2010-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jan Camenisch and Thomas Groß},
      title = {Efficient Attributes for Anonymous Credentials (Extended Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2010/496},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.