On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. (Q1573770)

The paper considers polynomial approximations to the discrete logarithm and the Diffie-Hellman mappings modulo \(p\). It presents several lower bounds, exponential in terms of \(\log p\), on the degrees of polynomials and algebraic functions coinciding with values of the discrete logarithm modulo a prime \(p\) at sufficiently many points; the number of points can be as little as \(p^{1/2 + \varepsilon}\). The paper also presents 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 \rightarrow g^{x^2}\), 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.