1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

edit:

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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