Cryptology ePrint Archive: Report 2014/705

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

Christian Hanser and Daniel Slamanig

Abstract: 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.

Category / Keywords: public-key cryptography / Structure-preserving signatures, attribute-based anonymous credentials, polynomial commitments

Original Publication (with major differences): IACR-ASIACRYPT-2014

Date: received 8 Sep 2014, last revised 3 Dec 2014, withdrawn 20 Mar 2016

Contact author: christian hanser at iaik tugraz at

Available format(s): (-- withdrawn --)

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

Version: 20160320:192442 (All versions of this report)

Short URL: ia.cr/2014/705