Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

With the knowledge of the trapdoor, we are able to compute the same digest for differents messages.

I've read that given two messages $m$, $m'$ and two numbers $r$, $r'$ such that $Ch(m,r)=Ch(m',r')$, computed by the owner of the trapdoor, we are able to find other collisions and sometimes we are able to find this trapdoor information (for log based chameleon hash, in a work from Tal Rabin and Hugo Krawczyk, ).

I don't really understand the purpose of chameleon hash functions, since computing colluding messages lead to attacks. What are the subtleties ?

Thank you.

share|improve this question
up vote 4 down vote accepted

I think you have some misunderstanding here. Finding collisions when knowing the trapdoor is a required feature, but leaking the trapoor when knowing collisions is an undesirable "feature" (which some constructions suffer from).

A chameleon hash function (aka trapdoor commitment) allows you given the trapdoor to find pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ such that $Ch(m,r)=Ch(m',r')$. This means that given the trapdoor you can produce such pairs and it should be computationally infeasible otherwise. There are many theoretical and practical applications of chameleon hash functions. One nice practical application are sanitizable signatures, where the knowledge of the trapdoor allows a sanitizer to sanitize an already signed message without invalidating the signature.

However, there are some constructions of chameleon hash functions (trapdoor commitments), that leak the trapdoor if one such pair has been computed and is publicly known. Note that the chameleon hash functon in the linked paper (Section 2.2.) is essentially a Pedersen commitment and the trapdoor is the discrete log between the two group elements. When knowing $Ch(m,r)=Ch(m',r')$ for two pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ this allows to extract the trapdoor (just take a look at the binding proof for Pedersen commitments to see how this works - or just look at the equation under figure 3 in your linked paper and solve for $x$).

Chameleon hash functions which suffer from this "undersirable feature" are known to suffer from key exposure (which clearly often is a very undesirable feature). You should take a look at this paper for constructions that do not suffer from this limitation and there are also some other constructions which do not suffer from key exposure as well.

share|improve this answer
Ok, I've understood. Thank you very much. – Dingo13 Oct 20 '14 at 13:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.