I have a problem with this exercise:

Let $G$ be a group of order a prime $q$ and let $g, h$, be two randomly selected elements of $G$, with $g,h\ne 1$. Consider the following hash function on integers $x_1$ and $x_2$:

$H(x_1,x_2)=g^{x_1}h^{x_2} $

Show that the problem of finding a collision pair $(x_1',x_2')$ such that $H(x_1, x_2) =H(x_1',x_2')$ is equivalent to finding the discrete logarithm of $h$ with respect to the base $g$ (or viceversa, of $g$ w.r.t. the base $h$).

I thought I could do this to solve the problem:

$log_g(h)=x$ then $h=g^x$

If $H(x_1,x_2)=g^{x_1}h^{x_2} $ then I can write: $H(x_1,x_2)=g^{x_1}{(g^{x})}^{x_2}=g^{x_1}g^{xx_2}=g^{x_1+xx_2}$

With $x$ fixed, it is simple to find a pair of $(x_1',x'_2)$ such that $x_1'+xx_2'=x_1+xx_2$ and then a collision.

Can you tell me whether this logic works? Do you know if there are easier ways to solve it?


2 Answers 2


Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


Your reasoning is correct. Finding a collision will solve the discrete-logarithm problem. This is actually what Pollard's Rho does.

If you can find $g^{x_1}h^{x_2} = g^{y_1}h^{y_2}$ then you can compute the discrete logarithm of $h$

$g^{x_1}h^{x_2} = g^{x_1 + kx_2}$

$x_1 + kx_2 = y_1 + ky_2$

$x_1 - y_1 = k(y_2 - x_2)$

$(x_1 - y_1)(y_2 - x_2)^{-1} = k$

The same method can be used to solve $g$ with respect to $h$ since the subgroup is prime order, both $g$ and $h$ must be generators so there must exist $g^a = h$ and $h^b = g$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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