A Characterization of Chameleon Hash Functions and New, Efficient Designs

Mihir Bellare; Todor Ristov

Paper 2008/379

A Characterization of Chameleon Hash Functions and New, Efficient Designs

Mihir Bellare and Todor Ristov

Abstract

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.

Metadata

Available format(s): PDF
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.
Keywords: hash functions chameleon VSH Fiat-Shamir identification
Contact author(s): mihir @ cs ucsd edu
History: 2011-06-01: last of 5 revisions; 2008-09-07: received; See all versions
Short URL: https://ia.cr/2008/379
License: CC BY

BibTeX

@misc{cryptoeprint:2008/379,
      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},
      url = {https://eprint.iacr.org/2008/379}
}