Paper 2014/705

Structure-Preserving Signatures on Equivalence Classes and their Application to Anonymous Credentials

Christian Hanser and Daniel Slamanig


Structure-preserving signatures are a quite recent but important building block for many cryptographic protocols. In this paper, we introduce a new type of structure-preserving signatures, which allows to sign group element vectors and to consistently randomize signatures and messages without knowledge of any secret. More precisely, we consider messages to be (representatives of) equivalence classes on vectors of group elements (coming from a single prime order group), which are determined by the mutual ratios of the discrete logarithms of the representative's vector components. By multiplying each component with the same scalar, a different representative of the same equivalence class is obtained. We propose a definition of such a signature scheme, a security model and give an efficient construction, which we prove secure in the SXDH setting, where EUF-CMA security is proven against generic forgers in the generic group model and the so called class hiding property is proven under the DDH assumption. As a second contribution, we use the proposed signature scheme to build an efficient multi-show attribute-based anonymous credential (ABC) system that allows to encode an arbitrary number of attributes. This is -- to the best of our knowledge -- the first ABC system that provides constant-size credentials and constant-size showings. To allow an efficient construction in combination with the proposed signature scheme, we also introduce a new, efficient, randomizable polynomial commitment scheme. Aside from these two building blocks, the credential system requires a very short and constant-size proof of knowledge to provide freshness in the showing protocol. We present our ABC system along with a suitable security model and rigorously prove its security.

Note: This paper was withdrawn because it was flawed. A corrected and extended version is available as eprint report 2014/944.

Available format(s)
-- withdrawn --
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2014
Structure-preserving signaturesattribute-based anonymous credentialspolynomial commitments
Contact author(s)
christian hanser @ iaik tugraz at
2016-03-20: withdrawn
2014-09-09: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.