On the statistical properties of Diffie-Hellman distributions

Let p be a large prime such that p - 1 has some large prime factors, and le t 6 is an element of Z(p)* be an r-th power residue for all small factors p - 1. The corresponding Diffie-Hellman (DH) distribution is (theta (x), the ta (y), theta (xy)) where x,y are randomly chosen from Z(p)*. A recently fo rmulated assumption is that given p, theta of the above form it is infeasib le to distinguish in reasonable time between DH distribution and triples of numbers chosen randomly from Z(p)*. This assumption, called the DH Indisti nguishability (DHI) assumption, turns out to be quite useful and central in cryptography. In an effort to investigate the validity of this assumption, we study some statistical properties of DH distributions. Let theta be an element in Z(p) *: with sufficiently high multiplicative order. We show that if one takes a positive (but sufficiently small) proportion of the most significant bits of each of theta (x), theta (y), theta (xy) then one obtains a distribution whose statistical distance from uniform is exponentially small. A similar result holds with respect to the least significant bits of (theta (x), thet a (y), theta (xy)). We also show somewhat weaker bounds with respect to arb itrary subsets of Lit-positions. This remarkable property may help gaining assurance in the DHI assumption. Our techniques are mainly number-theoretic. We obtain an upper bound for do uble exponential sums with the function a theta (x) + b theta (y) + c theta (xy) which sharpens and generalizes the previous estimates. In particular, our bound implies the following result (for p, theta of the above form). R anging over all x, y is an element of Z(p)*, the vectors (theta (x)/p, thet a (y)/p, theta (xy)/p) are very evenly distributed in the unit cube. In order to make this work accessible to two groups of researchers, cryptog raphers and number theorists, we have decided to make it as self-contained as possible. As a result, some parts of it, mainly targetted to one of thes e groups, may appear obvious to the other. In particular we present some ba sic notions of the modern cryptography and on the other hand we give a shor t explanation how exponential sums show up in various questions related to uniform distribution of sequences.