On Polynomial Approximation and the Parallel Complexity of the Discrete Logarithm and Breaking the Diffie-Hellman Cryptosystem

Several exponential (in terms of log p) lower bounds are obtained on the degrees and orders of: polynomials, algebraic functions, Boolean functions, and linear recurring sequences, coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as little as p1/2+e). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue. These results are used to obtain lower bounds on the parallel complexity of computing the discrete logarithm. The method is based on bounds of character sums and numbers of solutions of some polynomial equations. Similar results are obtained for breaking the Diffie-Hellman cryptosystem. Several other applications of the method are indicated as well.