Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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