Polynomial Approximation and Arithmetic Complexity of the Diffie-Hellman Secret Key

Let g be a primitive root of a finite field $${\mathbb{F}_q}$$ of q elements. One of the most popular public key cryptosystems, the Diffie- Hellman key exchange protocol, is based on the still unproved assumption that recovering the value of the Diffie-Hellman secret key $$K(x,y) = {g^{xy}}$$ from the known values of gXand gyis essentially equivalent to the discrete logarithm problem and therefore is hard. Here we show that even computation of $${g^{{x^2}}}$$ from gxcannot be realized by a polynomial of low degree.