On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping

Don Coppersmith, Igor Shparlinski

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)

Abstract

We obtain several lower bounds, exponential in terms of Ig p, on the degrees of polynomials and algebraic functions coinciding with values of the discrete logarithm module a prime p at sufficiently many points; the number of points can be as little as p(1/2+epsilon). 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.

Original languageEnglish
Pages (from-to)339-360
Number of pages22
JournalJournal of Cryptology
Volume13
Issue number3
DOIs
Publication statusPublished - 2000

Keywords

  • discrete logarithms
  • Diffie-Hellman cryptosystem
  • polynomial approximations
  • Boolean functions
  • character sums
  • RANDOM-ACCESS MACHINES
  • LOWER TIME-BOUNDS
  • BOOLEAN FUNCTIONS

Cite this