DLOG ⇒ Chameleon hash (Krawczyk–Rabin)

Fully-black-box reduction · standard model · KR00 · security loss: tight: on DLOG challenge the reduction outputs , and otherwise it sets , distributed as in , and turns one collision into

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.