Paper 2023/1016

Aggregate Signatures with Versatile Randomization and Issuer-Hiding Multi-Authority Anonymous Credentials

Omid Mir, Johannes Kepler University Linz, LIT Secure and Correct Systems Lab, Linz, Austria
Balthazar Bauer, IRIF, CNRS, Paris, France
Scott Griffy, Brown University, Providence, USA
Anna Lysyanskaya, Brown University, Providence, USA
Daniel Slamanig, AIT Austrian Institute of Technology, Vienna, Austria

Anonymous credentials (AC) have emerged as a promising privacy-preserving solu- tion for user-centric identity management. They allow users to authenticate in an anonymous and unlinkable way such that only required information (i.e., attributes) from their credentials are re- vealed. With the increasing push towards decentralized systems and identity, e.g., self-sovereign identity (SSI) and the concept of verifiable credentials, this also necessitates the need for suit- able AC systems. For instance, when relying on existing AC systems, obtaining credentials from different issuers requires the presentation of independent credentials, which can become cum- bersome. Consequently, it is desirable for AC systems to support the so-called multi-authority (MA) feature. It allows a compact and efficient showing of multiple credentials from different is- suers. Another important property is called issuer hiding (IH). This means that showing a set of credentials is not revealed which issuer has issued which credentials but only whether a verifier- defined policy on the acceptable set of issuers is satisfied. This issue becomes particularly acute in the context of MA, where a user could be uniquely identified by the combination of issuers in their showing. Unfortunately, there are no AC schemes that satisfy both these properties simul- taneously. To close this gap, we introduce the concept of Issuer-Hiding Multi-Authority Anonymous Cre- dentials (IhMA). Our proposed solution involves the development of two new signature primi- tives with versatile randomization features which are independent of interest: 1) Aggregate Sig- natures with Randomizable Tags and Public Keys (AtoSa) and 2) Aggregate Mercurial Signatures (ATMS), which extend the functionality of AtoSa to additionally support the randomization of messages and yield the first instance of an aggregate (equivalence-class) structure-preserving sig- nature. These primitives can be elegantly used to obtain IhMA with different trade-offs but have applications beyond. We formalize all notations and provide rigorous security definitions for our proposed primi- tives. We present provably secure and efficient instantiations of the two primitives as well as corresponding IhMA systems. Finally, we provide benchmarks based on an implementation to demonstrate the practical efficiency of our constructions

Available format(s)
Cryptographic protocols
Publication info
Aggregate signaturesrandomizationanonymous credentialsmulti-authorityissuer-hiding
Contact author(s)
mir @ ins jku at
Balthazar Bauer @ ens fr
scott_griffy @ brown edu
anna_lysyanskaya @ brown edu
daniel slamanig @ ait ac at
2023-07-03: approved
2023-06-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Omid Mir and Balthazar Bauer and Scott Griffy and Anna Lysyanskaya and Daniel Slamanig},
      title = {Aggregate Signatures with Versatile Randomization and Issuer-Hiding Multi-Authority Anonymous Credentials},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1016},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.