Claw-free TDP ⇒ Chameleon hash (Krawczyk–Rabin)

Fully-black-box reduction · standard model · KR00 · security loss: none

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.