caa a22 4500 475827104 CHVBK 20180406123831.0 cr unu---uuuuu 170329e20000601xx s 000 0 eng 10.1007/s001450010002 doi (NATIONALLICENCE)springer-10.1007/s001450010002 On Polynomial Approximation of the Discrete Logarithm and the Diffie—Hellman Mapping [Elektronische Daten] [Don Coppersmith, Igor Shparlinski] Abstract. : We obtain several lower bounds, exponential in terms of lg 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 + ɛ . 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. International Association for Criptologic Rese, 2000 Key words. Discrete logarithms, Diffie—Hellman cryptosystem, Polynomial approximations, Boolean functions, Character sums nationallicence Coppersmith Don IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, U.S.A. copper@watson.ibm.com, US aut Shparlinski Igor Department of Computing, Macquarie University, Sydney, NSW 2109, Australia igor@comp.mq.edu.au, AU aut Journal of Cryptology Springer Berlin Heidelberg 13/3(2000-06-01), 339-360 0933-2790 13:3<339 2000 13 145 https://doi.org/10.1007/s001450010002 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s001450010002 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Coppersmith Don IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, U.S.A. copper@watson.ibm.com, US aut NATIONALLICENCE 700 1- Shparlinski Igor Department of Computing, Macquarie University, Sydney, NSW 2109, Australia igor@comp.mq.edu.au, AU aut NATIONALLICENCE 773 0- Journal of Cryptology Springer Berlin Heidelberg 13/3(2000-06-01), 339-360 0933-2790 13:3<339 2000 13 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer