TransWikia.com

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

Cryptography Asked on December 2, 2021

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.

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

Answered by ckamath on December 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP