Describe a fast (polynomial time)algorithm who takes as input the elements $g^a,g^b$ and gives as output the element $g^{a \cdot b}$

Question

Let $q$ prime number, $G$ a cyclic group with order $q$ and $g \in G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$. Describe a fast (polynomial time) algorithm who takes as input the elements $g^a, g^b$ and gives as output the element $g^{a \cdot b}$ (namely an algorithm that solves the problem Diffie-Hellman). Any ideas how to solve it?

Answer 1

Note that because $g^q = 1$ (the neutral element), we have in general,

$$g^{ab} = g^{ab} 1 = g^{ab} g^{qab} = g^{ab (q+1)} = g^{2ab \frac {q+1} 2} = \big( g^{2ab} \big) ^{\frac {q+1} 2} = \big( g^{(a+b)^2 -a^2 -b^2} \big) ^{\frac {q+1} 2} =\big( A(g^{a+b}) A(g^a)^{-1} A(g^b)^{-1} \big) ^{\frac {q+1} 2} ,$$

the last expression being able to be implemented efficiently provided that multiplication in the group can be performed efficiently (and using binary exponentation for the outer exponentiation). In order to compute the inverse, note that $x^{-1} = x^{q-1}$, therefore inversion can be performed by exponentiation.

To clarify, we first compute $g^{2ab}$ as indicated in a comment below your question, then we remove the $2$ from the exponent by "extracting a square root", which means raising to $\frac {q+1} 2$.