Suppose we have a signature scheme for signing elements of message space M 1 , but we need to sign messages from M 2 . The traditional approach of applying a collision resistant hash function from M 1 to M 2 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 M 1 , a pairwise independent hash function with key space M 1 and message space M 2 , and a non-interactive zero knowledge proof system to obtain a signature scheme for message space M 2 . This transform also removes any dependence on state in the signature for M 1 .

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.

}, author = {Melissa Chase and Markulf Kohlweiss}, booktitle = {Security and Cryptography for Networks (SCN)}, title = {A New Hash and Sign Approach and Structure-Preserving Signatures from DLIN}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=178987}, year = {2012}, }