Discrete logarithm hash function Exercises

Question

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?

Answer 1

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).

Answer 2

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$.