# Extracting $x$ given $g^x, g^{x + y}, y$

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?

• 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$)? – poncho Jul 18 '17 at 21:05
• 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. – raisyn Jul 18 '17 at 21:12

## 1 Answer

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.