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?
$\begingroup$
$\endgroup$
2
-
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$– ponchoJul 18, 2017 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$– raisynJul 18, 2017 at 21:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
