On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping

We obtain several lower bounds, exponential in terms of Ig p, on the degrees of polynomials and algebraic functions coinciding with values of the discrete logarithm module a prime p at sufficiently many points; the number of points can be as little as p(1/2+epsilon). We also obtain improved lower bounds on the degree and sensitivity of Boolean functions on bits of x deciding whether x is a quadratic residue. Similar bounds are also proved for the Diffie-Hellman mapping g(x) --> g(x2), where g is a primitive root of a finite field of q elements F-q. These results can be used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm and breaking the Diffie-Hellman cryptosystem. The method is based on bounds of character sums and numbers of solutions of some polynomial equations.