Paper 2014/1021

Tightly-Secure Signatures from Chameleon Hash Functions

Olivier Blazy, Saqib A. Kakvi, Eike Kiltz, and Jiaxin Pan


We give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, we show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model. Some of our signature schemes can (using known techniques) be combined with Groth-Sahai proof methodology to yield tightly secure and efficient simulation-sound NIZK proofs of knowledge and CCA-secure encryption in the multi-user/-challenge setting under classical assumptions.

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2015
digital signaturesstandard modeltight reductionchameleon hashes
Contact author(s)
saqib kakvi @ rub de
2016-06-28: last of 2 revisions
2014-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Olivier Blazy and Saqib A.  Kakvi and Eike Kiltz and Jiaxin Pan},
      title = {Tightly-Secure Signatures from Chameleon Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1021},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.