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

  • 3
    $\begingroup$ Hint: try to reduce the computational Diffie-Hellman assumption to this problem. $\endgroup$ Commented May 3, 2023 at 15:50
  • $\begingroup$ if you know only xH, G_1, and G_1? - is this a typo, you have mentioned $G_1$ twice? $\endgroup$
    – user93353
    Commented May 3, 2023 at 15:57
  • $\begingroup$ @IstvánAndrásSeres I don't think that we know that discrete logarithm being hard implies computational Diffie-Hellman being hard. $\endgroup$
    – Daniel S
    Commented May 3, 2023 at 16:08
  • $\begingroup$ @user93353 you're right! edited it. $\endgroup$
    – RobinLinus
    Commented May 3, 2023 at 16:13
  • 1
    $\begingroup$ 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/… $\endgroup$ Commented May 3, 2023 at 17:29

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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