Claw-free TDP ⇒ Chameleon hash (Krawczyk–Rabin)
Statement
A claw-free pair of trapdoor permutations on a domain gives a collision-resistant, uniform chameleon hash function with a prefix-free message space and randomness space and range — KR00. The hash key is and the trapdoor is ; for ,
and applies in turn to .
Sketch
Given a collision with , peel the outermost permutations off both sides while the leading bits agree; since neither message is a prefix of the other, a first position with is reached before either message ends, and the two arguments of and there form a claw. Every composition is a permutation of , so is uniform for uniform , whatever .
Notes
- The composition and the prefix-free encoding are those of the GMR signature scheme — GMR88.