On the statistical properties of Diffie-Hellman distributions (Q5932009)

Let \(p\) be a prime and \(\vartheta \in \mathbb{Z}^*_p\) be an element of order \(t\) such that \(t\) is not divisible by any small prime. The authors consider the Diffie-Hellman triples \((\vartheta^x, \vartheta^y, \vartheta^{xy})\) with random \(x,y \in \mathbb{Z}^*_p\) and prove that the distribution of the most significant bits of \((\vartheta^x, \vartheta^y, \vartheta^{xy})\) is close to a uniform distribution. They also present a similar result to the least significant bits and a somewhat weaker bound for arbitrary bit positions of the Diffie-Hellman triples. These results support the Diffie-Hellman indistinguishability assumption that the triples \((\vartheta^x, \vartheta^y, \vartheta^{xy})\) cannot be efficiently distinguished from random triples. The proofs are based on new bounds for double exponential sums. In particular, the bound of the first, second, and last author [J. Lond. Math. Soc. (2) 59, 799-812 (1999; Zbl 0935.11028)] on the sums \[ S_{a,b,c}(t)= \sum\limits_{x,y=1}^{t} \exp(2\pi i(a \vartheta^x + b \vartheta^y + c \vartheta ^{xy})), \quad \gcd(a,c,p)=1, \] is essentially improved: \[ S_{a,b,c}(t)=\begin{cases} O(t^{1+ \varepsilon}p^{1/2}), & \text{if } p\mid a,\\ O(t^{5/3}p^{1/4}), & \text{otherwise}. \end{cases} \]