On the distribution of the Diffie-Hellman pairs

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₁ < ⋯ <i_k ≤ n, where a₁, ⋯, 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.