# Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?

Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $$G_1, G_2$$, and a third generator defined by $$H = G_1 + G_2$$. Can you compute $$xG_1$$ if you know only $$G_1$$, $$G_2$$, and $$xH$$?

My guess: I would assume it's hard, because otherwise it would be easy to compute $$xG$$ knowing only $$xH$$ for any two unrelated generators $$G$$ and $$H$$.

• Hint: try to reduce the computational Diffie-Hellman assumption to this problem. Commented May 3, 2023 at 15:50
• if you know only xH, G_1, and G_1? - is this a typo, you have mentioned $G_1$ twice? Commented May 3, 2023 at 15:57
• @IstvánAndrásSeres I don't think that we know that discrete logarithm being hard implies computational Diffie-Hellman being hard. Commented May 3, 2023 at 16:08
• @user93353 you're right! edited it. Commented May 3, 2023 at 16:13
• Superb! I think now you can prove that your problem is as hard as CDH. Imagine that you have an oracle that solves your problem, and now try to build a machine that solves arbitrary CDH instances with the same success probability as the oracle solving your problem. Hope this helps. If not, let me know and I can write down the proof for you as an answer but I'll leave the joy of thinking for you as of now. en.wikipedia.org/wiki/… Commented May 3, 2023 at 17:29

Computing $$xG_1$$ knowing only $$G_1$$, $$G_2$$, and $$xH$$ is as hard as the computational Diffie-Hellman problem (CDH).
For some given $$xH$$ we can choose, for example, $$G_1 = yH$$ and $$G_2 = H - G_1$$. This choice satisfies $$H = G_1 + G_2$$.
Computing $$xG_1$$ from $$xH$$ is equivalent to computing $$xyH$$, which breaks the CDH assumption.