## Abstract

Let p be a large prime such that p - 1 has some large prime factors, and let θ ∈ ℤ*_{p} be an r-th power residue for all small factors of p - 1. The corresponding Diffie-Hellman (DH) distribution is (θ^{x},θ^{y},θ^{xy}) where x, y are randomly chosen from ℤ*_{p}. A recently formulated assumption is that given p, θ of the above form it is infeasible to distinguish in reasonable time between DH distribution and triples of numbers chosen randomly from ℤ*_{p}. This assumption, called the DH Indistinguishability (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 θ be an element in ℤ*_{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 θ^{x},θ^{y},θ^{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 (θ^{x},θ^{y},θ^{xy}). We also show somewhat weaker bounds with respect to arbitrary subsets of bit-positions. This remarkable property may help gaining assurance in the DHI assumption. Our techniques are mainly number-theoretic. We obtain an upper bound for double exponential sums with the function aθ^{x} + bθ^{y} + cθ^{xy}which sharpens and generalizes the previous estimates. In particular, our bound implies the following result (for p, θ of the above form). Ranging over all x, y ∈ ℤ*_{p}, the vectors (θ^{x}/p, θ^{y}/p, θ^{xy}/p) are very evenly distributed in the unit cube. In order to make this work accessible to two groups of researchers, cryptographers and number theorists, we have decided to make it as selfcontained as possible. As a result, some parts of it, mainly targetted to one of these groups, may appear obvious to the other. In particular we present some basic notions of the modern cryptography and on the other hand we give a short explanation how exponential sums show up in various questions related to uniform distribution of sequences.

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

Pages (from-to) | 23-46 |

Number of pages | 24 |

Journal | Israel Journal of Mathematics |

Volume | 120 |

DOIs | |

Publication status | Published - 2000 |

Event | Conference on Exponential Sums - Jerusalem, Israel Duration: 11 Jan 1998 → 15 Jan 1998 |