# Diffie-Hellman: difficulty of computing $g^{x^2}$ given $g^x$?

Hoepfuly a simple question.

Given a group where the CDH problem is hard, if the adversary sees a public key $$g^x$$, is it easy or hard for the adversary to compute $$g^{x^2}$$?

My intuition says it should be hard, but I don't know for sure.

• – SEJPM Jul 23 '20 at 7:59

## 1 Answer

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^x)$$, then on $$(g,g^y)$$ and finally on $$(g,g^{x+y}=g^xg^y)$$ -- to obtain $$X=g^{x^2}$$, $$Y=g^{y^2}$$ and $$Z=g^{(x+y)^2}$$, respectively. Now $$\mathsf{A}'$$ can extract the solution to CDH, i.e., $$g^{xy}$$, by computing $$(Z/XY)^{1/2}$$. The correctness of the solution can be argued using the identity $$(x+y)^2=x^2+y^2+2xy$$.

Note that the ability to compute a square root is crucial for the reduction to go through. Therefore the reduction above holds only for prime-order groups or any group of known order. (I am not aware of a reduction from CDH to SDH for groups of unknown order.)

As @poncho points out in the comment, this means that SDH is equivalent to CDH since the reduction in the other direction is straightforward as described next. Given an adversary $$\mathsf{A}$$ that breaks CDH, we construct an adversary $$\mathsf{A}'$$ that breaks SDH works. On input the SDH challenge $$(g,g^x)$$, $$\mathsf{A}'$$ computes $$(g,g^x,(g^x)^r)$$ for a random $$r$$ and sends it to CDH adversary $$\mathsf{A}$$. The CDH solver returns $$g^{x^2r}$$ from which it can retrieve $$g^{x^2}$$ by computing the $$r$$-th root.

$$^*$$ This is an example where we know a Turing reduction but not a Karp reduction.

• It is also easy to solve the SDH problem with a CDH oracle, even if that oracle is restricted from given the answers to "non-random" triplets, such as $g, g^x, g^x$ – poncho Jul 23 '20 at 2:55
• Thanks, @poncho. Answer amended. – Occams_Trimmer Jul 23 '20 at 13:30
• Right. But practically we also lose one bit of security I think? Since the set of squares in a group modulo p-1 for prime p are all the even numbers? – Joe Jul 23 '20 at 17:57
• Interesting, had never thought of that. Concretely, it seems the cost is higher, thrice that of CDH. The reason is that given a CDH adversary that succeeds with probability $\varepsilon$, the probability with which the SDH adversary wins is $\varepsilon^3$. – Occams_Trimmer Jul 23 '20 at 21:43