DLOG ⇒ Chameleon hash (Krawczyk–Rabin)
Statement
If DLOG is hard in prime-order groups for , the following is a collision-resistant, uniform chameleon hash function with message and randomness space and range — KR00. samples and and outputs with and ; ; .
Sketch
A collision with gives , so and : on DLOG challenge the reduction outputs if , and otherwise sets , distributed as in , so a collision finder yields . Uniformity holds because is uniform in for uniform when .
Notes
- The function is the Pedersen commitment to with randomness , a commitment scheme — Ped91.
- Any published collision reveals by the same computation, so the trapdoor holder cannot exhibit a collision without exposing the trapdoor; chameleon hashes avoiding this are studied by AdM04.