# Security of chameleon hash functions

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, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3262 ).

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

Thank you.

-

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$).