## Abstract

Let F_{p} be a prime field of p elements and let g be an element of F_{p} of multiplicative order t modulo p. We show that for any ε > 0 and t ≥ p^{1/3+ε} the distribution of the Diffie-Hellman pairs (x,g^{x}) is close to uniform in the Cartesian product ℤ_{t} × F_{p}, where x runs through • the residue ring ℤ_{t} modulo t (that is, as in the classical Diffie-Hellman scheme); • The all k-sums x = a_{i1} + ⋯ + a_{ik}, 1 ≤ i_{1} < ⋯ <i_{k} ≤ n, where a_{1}, ⋯, a_{n} ∈ ℤ_{t} are selected at random (that is, an in the recently introduced Diffie-Hellman scheme with precomputation). These results are new and nontrivial even if t = p - 1, that is, if g is a primitive root. The method is based on some bounds of exponential sums.

Original language | English |
---|---|

Pages (from-to) | 131-141 |

Number of pages | 11 |

Journal | Finite Fields and their Applications |

Volume | 8 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2002 |