A New Hash-and-Sign Approach and Structure-Preserving Signatures from DLIN

Melissa Chase, Markulf Kohlweiss

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Suppose we have a signature scheme for signing elements of message space M1, but we need to sign messages from M2. The traditional approach of applying a collision resistant hash function from M1 to M2 can be inconvenient when the signature scheme is used within more complex protocols, for example if we want to prove knowledge of a signature. Here, we present an alternative approach in which we can combine a signature for M1, a pairwise independent hash function with key space M1 and message space M2, and a non-interactive zero knowledge proof system to obtain a signature scheme for message space M2. This transform also removes any dependence on state in the signature for M1.

As a result of our transformation we obtain a new signature scheme for signing a vector of group elements that is based only on the decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by evaluating a set of pairing-product equations, so the result is a structure-preserving signature. In combination with the Groth-Sahai proof system, such a signature scheme is an ideal building block for many privacy-enhancing protocols.
Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks - 8th International Conference, SCN 2012, Amalfi, Italy, September 5-7, 2012. Proceedings
Number of pages18
ISBN (Electronic)978-3-642-32928-9
ISBN (Print)978-3-642-32927-2
Publication statusPublished - 2012
Event8th Conference on Security and Cryptography for Networks - Amalfi, Italy
Duration: 5 Sep 20127 Sep 2012


Conference8th Conference on Security and Cryptography for Networks
Abbreviated titleSCN 2012

Fingerprint Dive into the research topics of 'A New Hash-and-Sign Approach and Structure-Preserving Signatures from DLIN'. Together they form a unique fingerprint.

Cite this