Cryptology ePrint Archive: Report 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.

Category / Keywords: hash functions, chameleon, VSH, Fiat-Shamir, identification

Publication Info: Preliminary version appeared in ASIACRYPT 2008 entitled ``Hash functions from Sigma protocols and improvements to VSH." This is the full version.

Date: received 5 Sep 2008, last revised 1 Jun 2011

Contact author: mihir at cs ucsd edu

Available formats: PDF | BibTeX Citation

Note: Fixed typos and re-wrote the equivalence.

Version: 20110601:175200 (All versions of this report)

Discussion forum: Show discussion | Start new discussion