Score:2

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

cn flag

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

István András Seres avatar
cf flag
Hint: try to reduce the computational Diffie-Hellman assumption to this problem.
et flag
`if you know only xH, G_1, and G_1?` - is this a typo, you have mentioned $G_1$ twice?
Daniel S avatar
ru flag
@IstvánAndrásSeres I don't think that we know that discrete logarithm being hard implies computational Diffie-Hellman being hard.
RobinLinus avatar
cn flag
@user93353 you're right! edited it.
István András Seres avatar
cf flag
You're right @DanielS! Can we assume the CDH assumption in your applied group, @RobinLinus?
RobinLinus avatar
cn flag
@IstvánAndrásSeres yes. I'll add it to the question
István András Seres avatar
cf flag
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. https://en.wikipedia.org/wiki/Computational_Diffie%E2%80%93Hellman_assumption
Score:3
cn flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.