# Discrete logarithm hash function Exercises

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

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