1
$\begingroup$

Given a cyclic group $ G $ of prime order $ q $ with generator $ g $ in which computing the discrete logarithm is hard.

Is it (still) hard to find the discrete logarithm $ dlog_g(g^x) = x $ if the values $ g, g^x, g^{x + y} $, $ y $ are known?

$\endgroup$
  • 2
    $\begingroup$ Hint: suppose you had an oracle that could recover $x$ given $g, g^x, g^{x+y}, y$; could you use that oracle to compute discrete logs (i.e. recover $x$ given $g, g^x$)? $\endgroup$ – poncho Jul 18 '17 at 21:05
  • $\begingroup$ Indeed that would work, as I can always expand $ g, g^x $ to $ g, g^x, g^{x+y}, y $ because $ g^{x+y} = g^x \cdot g^y $. Therefore the problem should be equivalent to finding the discrete logarithm. So simple, thank you very much. $\endgroup$ – raisyn Jul 18 '17 at 21:12
10
$\begingroup$

Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here.

Yes, it is still hard to find the discrete log, given $g, g^x, g^{x+y}, y$. The reasoning is simple; if that were an easy problem, that is, if we had an oracle that, given $g, g^x, g^{x+y}, y$, recover $x$, we could then solve the discrete log problem. Here's how we would do that: given $g, g^x$, we would select a random $y$, and compute $g^y \cdot g^x = g^{x+y}$. Then, as we had $g, g^x, g^{x+y}, y$, we could hand those values to the oracle, which would give us $x$, solving the original DLog problem.

You also have an obvious reduction in the other direction; hence your problem is precisely equivalent to the standard DLog problem.

$\endgroup$

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.