4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – poncho Jul 23 at 2:55
  • $\begingroup$ Thanks, @poncho. Answer amended. $\endgroup$ – Occams_Trimmer Jul 23 at 13:30
  • $\begingroup$ 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? $\endgroup$ – Joe Jul 23 at 17:57
  • $\begingroup$ 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$. $\endgroup$ – Occams_Trimmer Jul 23 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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