Let $p$ be a prime number, and $g$ a generator of $\mathbb Z/p\mathbb Z$. For a message $m$, define the hash function $$h(m) = g^m \pmod p.$$ Is $h$ collision-resistant?

  • $\begingroup$ Instructions for beginners: please @mariyana, click "accept" in the accepted answer. $\endgroup$ – Peter Krauss Apr 21 '18 at 12:50

Let $m$ be arbitrary. Then $m'=m+p-1$ yields a collision with $h(m)=h(m')$ as $m\equiv m'\pmod{p-1}$ and thus by $p-1$ being the relevant group's order $g^m\equiv g^{m'}\pmod p$.

Or formulated differently (using $g^{p-1}\bmod p=1$): $$h(m')=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p$$

| improve this answer | |
  • 1
    $\begingroup$ Strictly speaking, the domain wasn't specified. If the domain was $\{0, 1, 2, \dots, p - 2\}$, then $h$ is injective and so has no collisions at all! $\endgroup$ – Squeamish Ossifrage Apr 22 '18 at 4:10
  • $\begingroup$ @SqueamishOssifrage But then $h$ also wouldn't be a "hash function" because it would be non-compressing. $\endgroup$ – SEJPM Apr 22 '18 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.