Standard Model Signatures from Dual Identification Schemes

In this paper we introduce dual tag-based identification ( d t I D ) schemes. Inspired by a recent signature scheme by Chevallier-Mames, we present a general transformation that converts d t I D schemes into signature schemes via parallel-OR proofs and the Fiat-Shamir transformation. The security of this approach does not rely on the random oracle model; it only requires the hash function to be correlation intractable relative to some simple function f . We present two instantiations of d t I D schemes: one that explains the Chevallier-Mames signature scheme, which is based on the q -Strong Diffie-Hellman assumption, and another that relies on a slightly weaker assumption, the q -Diffie-Hellman assumption.