Paper 2019/1061

Breaking and Fixing Anonymous Credentials for the Cloud

Ulrich Haböck and Stephan Krenn


In an attribute-based credential (ABC) system, users obtain a digital certificate on their personal attributes, and can later prove possession of such a certificate in an unlinkable way, thereby selectively disclosing chosen attributes to the service provider. Recently, the concept of encrypted ABCs (EABCs) was introduced by Krenn et al. at CANS 2017, where virtually all computation is outsourced to a semi-trusted cloud-provider called wallet, thereby overcoming existing efficiency limitations on the user’s side, and for the first time enabling “privacy-preserving identity management as a service”. While their approach is highly relevant for bringing ABCs into the real world, we present a simple attack allowing the wallet to learn a user's attributes when colluding with another user -- a scenario which is not covered by their modeling but which needs to be considered in practice. We then revise the model and construction of Krenn et al. in various ways, such that the above attack is no longer possible. Furthermore, we also remove existing non-collusion assumptions between wallet and service provider or issuer from their construction. Our protocols are still highly efficient in the sense that the computational effort on the end user side consists of a single exponentiation only, and otherwise efficiency is comparable to the original work of Krenn et al.

Note: slightly reformatted, correction of a mistake in the formal definition of the unlinkability experiment.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.CANS 2019, LNCS 1182
Attribute-based credentialsPrivacy-preserving authenticationStrong authentication
Contact author(s)
ulrich haboeck @ fh-campuswien ac at
stephan krenn @ ait ac at
2019-11-18: last of 3 revisions
2019-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ulrich Haböck and Stephan Krenn},
      title = {Breaking and Fixing Anonymous Credentials for the Cloud},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1061},
      year = {2019},
      doi = {10.1007/978-3-030-31578-8_14},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.