Score:0

Diffie-Hellman: how to solve an alternative of Diffie-Hellman given an algorithm that solves Square Diffie-Hellman?

ru flag

A simple question. How can I proof the next polynomial reduction? : $DH’ ≤_{p} SQ$

where DH': given $g^{a}$ and $g^{b}$, compute {$g^{ab}$,$yg^{ab}$} where $y= g^{d/2}$, d is the order of cyclic group G.

and SQ: Square Diffie-Hellman (SDH) given $g^{a}$ , compute $(g^{a})^{2}$

Morrolan avatar
ng flag
Your notation of SDH is improper - it's about, given $g^a$, finding $g^{a^2} = g^{(a^2)}$. Finding $(g^a)^2$ would be rather straight-forward. With that said, there exist previous questions on this site about the equivalence of SDH and CDH, such as [this](https://crypto.stackexchange.com/questions/27152/show-how-to-efficiently-solve-the-computational-diffie-hellman-assumption-given) or [this](https://crypto.stackexchange.com/questions/82041/diffie-hellman-difficulty-of-computing-gx2-given-gx/82042#82042).
Facundo Fleitas avatar
ru flag
$(g^{a})^{2} = g^{a}g^{a} = g^{2a} = g^{(a^2)}$
Facundo Fleitas avatar
ru flag
I dont want for the equivalence of SDH and CDH, DH' its a different variant.
Morrolan avatar
ng flag
The last equality of yours does not hold. $a^2 \neq 2a$ for most values of $a$. In which context have you encountered this DH' problem? It seems equivalent to CDH, but if it's part of an assignment then I'd rather not provide a full solution.
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.