## 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 language | English |
---|---|

Pages (from-to) | 339-360 |

Number of pages | 22 |

Journal | Journal of Cryptology |

Volume | 13 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2000 |

## Keywords

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