eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/944

Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials

Georg Fuchsbauer, Christian Hanser, and Daniel Slamanig


Structure-preserving signatures (SPS) are a powerful building block for cryptographic protocols. We introduce SPS on equivalence classes (SPS-EQ), which allow joint randomization of messages and signatures. Messages are projective equivalence classes defined on group element vectors, so multiplying a vector by a scalar yields a different representative of the same class. Our scheme lets one adapt a signature for one representative to a signature for another representative without knowledge of any secret. Moreover, given a signature, an adapted signature for a different representative is indistinguishable from a fresh signature on a random message. We propose a definitional framework for SPS-EQ and an efficient construction in Type-3 bilinear groups, which we prove secure against generic forgers. We also introduce set-commitment schemes that let one open subsets of the committed set. From this and SPS-EQ we then build an efficient multi-show attribute-based anonymous credential system for an arbitrary number of attributes. Our ABC system avoids costly zero-knowledge proofs and only requires a short interactive proof to thwart replay attacks. It is the first credential system whose bandwidth required for credential showing is independent of the number of its attributes, i.e., constant-size. We propose strengthened game-based security definitions for ABC and prove our scheme anonymous against malicious organizations in the standard model; finally, we discuss a concurrently secure variant in the CRS model.

Note: This paper corrects and extends eprint report 2014/705.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in JOC 2019
Structure-preserving signaturesattribute-based anonymous credentialsset commitments
Contact author(s)
fuchsbau @ di ens fr
daniel slamanig @ ait ac at
2021-01-21: last of 2 revisions
2014-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Georg Fuchsbauer and Christian Hanser and Daniel Slamanig},
      title = {Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials},
      howpublished = {Cryptology ePrint Archive, Paper 2014/944},
      year = {2014},
      doi = {10.1007/s00145-018-9281-4},
      note = {\url{https://eprint.iacr.org/2014/944}},
      url = {https://eprint.iacr.org/2014/944}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.