# How does $g^{x^2} \bmod p$ help you find $x$?

I was thinking about the Diffie-Hellman key exchange. One fact that we seem to know is that given a group generator $$g$$, a prime $$p$$ and the expression $$g^x \bmod p$$ its believed to be hard to find $$x$$; or more accurately $$x \bmod(p-1)$$.

Now the question is, what if we gave away some extra information. Such as $$g^{x^2} \bmod p$$.

My guess is that surely this should help us find $$x$$ in some fashion, but it’s not clear how.

Finding an exponent that sends $$g^x$$ to $$g^{x^2}$$ is as hard as finding $$x$$ given just our usual initial data. So that’s probably not the right way to exploit this information.

It is not known that knowing $$g^{x^2}$$ would help in any meaningful way to solve the discrete logarithm problem.

What you are describing can be generalized to asking whether in a group $$\mathbb{G}$$ giving an attacker $$(g, g^x,g^{x^2},\dots,g^{x^q})$$ for some $$q$$ and a uniformly chosen $$x \in |\mathbb{G}|$$ makes it feasible to recover $$x$$.

It is generally assumed that this is not the case. In fact the assumption that recovering $$x$$ remains hard is called the $$q$$-strong discrete logarithm ($$q$$-SDL) assumption and has been used before. [GOR11] Similarly, the bilinear variant is also assumed to be hard. [FS20]

While the $$q$$-SDL assumption itself is not used very often, it is actually implied by a variety of much more commonly used variants of $$q$$-strong Diffie Hellman assumptions. [TS10]

[GOR11] Vipul Goyal, Adam O'Neill, and Vanishree Rao. "Correlated-Input Secure Hash Functions". TCC 2011

[FS20] Nils Fleischhacker and Mark Simkin. "Robust Property-Preserving Hash Functions for Hamming Distance and More". Cryptology ePrint Archive, Report 2020/1301, 2020

[TS10] Naoki Tanaka and Taiichi Saito, "On the $$q$$-Strong Diffie-Hellman Problem". Cryptology ePrint Archive, Report 2010/215, 2010