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

Omid Mir; Balthazar Bauer; Scott Griffy; Anna Lysyanskaya; Daniel Slamanig

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

Abstract

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Aggregate signatures randomization anonymous credentials multi-authority issuer-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
History: 2023-07-03: approved; 2023-06-30: received; See all versions
Short URL: https://ia.cr/2023/1016
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1016,
      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},
      url = {https://eprint.iacr.org/2023/1016}
}