2
$\begingroup$

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.

$\endgroup$
1
5
$\begingroup$

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

$\endgroup$

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.