Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds.

Take the problem given $g,g',h$ where $g^z\equiv h\bmod p$ holds at some $z$ find $h'$ such that $g'^{z}\equiv h'\bmod p$ holds.

If we know $y$ such that $g^y\equiv g'\bmod p$ then $g'^{z}\equiv h'\bmod p$ is known or if we know $z$ then $g'^{z}\equiv h'\bmod p$ is known.

  1. If we know $g'^{z}\equiv h'\bmod p$ and $g^z\equiv h\bmod p$ then is it easier to find $z$?

  2. What is the best way to find $g'^{z}\equiv h'\bmod p$ if we only know $g,g',h$ with $g^z\equiv h\bmod p$?

  3. What is the best way to find $f$ such that $f^{z}\equiv 1\bmod p$ if we only know $g,h$ with $g^z\equiv h\bmod p$?


1 Answer 1


This is exactly the Computational Diffie-Hellman (CDH) problem. Rename $h=g^z$ and $g'=g^y$ in what you wrote, then the problem becomes:

Given $g$, $g^z$, and $g^y$, compute $g^{yz}$.

See this discussion to address your question about the relationship between CDH and discrete log.


Q1: If we know $(g′)^z$ and $g^z$ then is it easier to find $z$?

No, it is just as hard as discrete log. If you are given just $g$ and $g^z$ then you can generate other pairs with the same discrete log relationship yourself, via $g' = g^r$ and $(g')^z = (g^z)^r$. So having extra such pairs doesn't add any new information.

  • $\begingroup$ That addresses 2. only? $\endgroup$
    – Turbo
    Aug 19, 2018 at 2:27
  • $\begingroup$ I updated with an answer to #1, and don't have an answer for #3. $\endgroup$
    – Mikero
    Aug 19, 2018 at 5:35
  • $\begingroup$ An answer for #3 would be to take $f = 1$... $\endgroup$
    – fkraiem
    Aug 19, 2018 at 11:54

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.