# On a diffie hellman related oracle

Given an oracle that can compute $$g^{x^{-1}}\bmod p$$ from $$g^x\bmod p$$ is it possible to compute $$g^{x^2}\bmod p$$ in polynomial time ($$p$$ is a prime and $$g$$ generates the multiplicative group modulo $$p$$)?

• Most probably yes by intuition. I haven't done serious calc yet. May 14 at 9:47

Well, if the Oracle works with an arbitrary base 'g', then it is easy.

If we give the Oracle the base $$g^x$$, and ask it to 'invert' $$g$$ with respect to that base, that is:

The base is $$h = g^x$$

The value being inverted is $$g = h^{x^{-1}}$$

Hence, the Oracle will return the value $$h^{{x^{-1}}^{-1}} = h^x = g^{x^2}$$

And we're done...

• "The value being inverted is g=h^{x^{−1}}".. We are not given h^x. May 14 at 18:35
• @Turbo: no, we're not - that's the value that the Oracle gives us... May 14 at 19:06
• I don't follow. What is the input to the oracle to get $h^{x^{-1}}$? May 14 at 22:20
• @Turbo: the input is $g$; it happens that $g = h^{x^{-1}}$ May 15 at 1:19

If the oracle is restricted to working with $$g$$ as the base, then the reduction is possible by considering the following equality: $$\frac{1}{x-1} - \frac{1}{x} = \frac{1}{x^2 - x}.$$

Inversions in the exponents are implemented by the oracles, while the other operations are done by multiplications/divisions.

• This is a better answer than mine... May 20 at 22:02