Paper 2008/379

A Characterization of Chameleon Hash Functions and New, Efficient Designs

Mihir Bellare and Todor Ristov


This paper shows that chameleon hash functions and Sigma protocols are equivalent. We provide a transform of any suitable Sigma protocol to a chameleon hash function, and also show that any chameleon hash function is the result of applying our transform to some suitable Sigma protocol. This enables us to unify previous designs of chameleon hash functions, seeing them all as emanating from a common paradigm, and also obtain new designs that are more efficient than previous ones. In particular, via a modified version of the Fiat-Shamir protocol, we obtain the fastest known chameleon hash function with a proof of security based on the STANDARD factoring assumption. The increasing number of applications of chameleon hash functions, including on-line/off-line signing, chameleon signatures, designated-verifier signatures and conversion from weakly-secure to fully-secure signatures, make our work of contemporary interest.

Note: Fixed typos and re-wrote the equivalence.

Available format(s)
Publication info
Published elsewhere. Preliminary version appeared in ASIACRYPT 2008 entitled ``Hash functions from Sigma protocols and improvements to VSH." This is the full version.
hash functionschameleonVSHFiat-Shamiridentification
Contact author(s)
mihir @ cs ucsd edu
2011-06-01: last of 5 revisions
2008-09-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Todor Ristov},
      title = {A Characterization of Chameleon Hash Functions and New, Efficient Designs},
      howpublished = {Cryptology ePrint Archive, Paper 2008/379},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.