# Tag Info

Let's call the problem Square Diffie-Hellman (SDH). SDH is at least as hard as CDH in groups of known order and the reduction goes as follows.$^*$ Given an adversary $\mathsf{A}$ that breaks SDH, our goal is to construct an adversary $\mathsf{A}'$ that breaks CDH. Given the CDH challenge $(g,g^x,g^y)$, $\mathsf{A}'$ runs $\mathsf{A}$ thrice -- first on $(g,g^... 6 This problem is equivalent to the CDH problem: Here is how to solve CDH given an Oracle that solves this problem: Given$g, g^x$, we can compute$g^{x^{-1}}$(which is equivalent to the CDH problem) by doing the following: Call the Oracle with$g, g^x$; the Oracle gives us a pair$g^{y}, xy$We compute$(g^{y})^{(xy)^{-1}} = g^{x^{-1}}\$, hence showing one ...