On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. (Q1573770)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. |
scientific article |
Statements
On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. (English)
0 references
8 August 2000
0 references
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.
0 references
discrete logarithm
0 references
Diffie-Hellman cryptosystem
0 references
polynomial approximations
0 references
boolean functions
0 references
character sums
0 references