On polynomial approximation of the discrete logarithm and the diffie-hellman mapping don coppersmith

Abstract

We obtain several lower t ounds, exponential in terms of Ig p, on the degrees of polynomials and algebraic 1 motions coinciding with values of the discrete logarithm modulo a prime p at sufficiency many points; the number of points can be as little as p1/2+ε_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 gx → gx2 , where g is a primitive root of a finite field of q elements Fq. These results can be used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm and breaking the DiffieHellman cryptosystem. The method is based on bounds of character sums and numbers of solutions of some polynomial equations. © 2000 International Association (or Cryptologic Research.