# 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.

-

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.

-
Ok, I've understood. Thank you very much. –  Dingo13 Oct 20 '14 at 13:50