On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples
Let \(g\) be a primitive root modulo a prime \(p\). We prove that the triples \((g^xz,g^y,g^{xy})\), \(x,y=1,\dots, p-1\), are uniformly distributed modulo \(p\) in the sense of H. Weyl. This result is based on the following upper bound for double exponential sums. Let \(\varepsilon>0\) be fixed. Then \[ \sum_{x,y=1}^{p-1} \exp\Biggl(2\pi i\frac{ag^x+bg^y+cg^{xy}}{p} \Biggr)=O_\varepsilon (p^{31/16+\varepsilon}) \] uniformly for any integers \(a,b,c\) with \(\text{gcd}(a,b,c,p)=1\). Incomplete sums are estimated as well. The question is motivated by the assumption, of then made in cryptography, that the triples \((g^x,g^y,g^{xy})\) cannot be distinguished from totally random triples in feasible computation time. Our results imply that this is in any case true for a constant fraction of the most significant bits, and for a constant fraction of the least significant.
- Double character sums over elliptic curves and finite fields
- On the distribution of the Diffie-Hellman pairs
- Exponential function analogue of Kloosterman sums
- On the complexity of the discrete logarithm and Diffie-Hellman problems
- New bounds on exponential sums related to the Diffie-Hellman distributions
- On the uniformity of distribution of the RSA pairs
- On the distribution of Diffie-Hellman triples with sparse exponents
- Double exponential sums over thin sets
- Distribution of modular sums and the security of the server aided exponentiation
- On the distribution of the power generator
- Incomplete exponential sums and Diffie–Hellman triples
- On an exponential sum related to the Diffie-Hellman cryptosystem
- An Explicit Bound On Double Exponential Sums Related to Diffie–Hellman Distributions
- Character sums with exponential functions
- Some doubly exponential sums over Zm
- UNIFORM DISTRIBUTION, EXPONENTIAL SUMS, AND CRYPTOGRAPHY
- scientific article; zbMATH DE number 2188811 (Why is no real title available?)
- On the statistical properties of Diffie-Hellman distributions
- On the number of factorizations of \(t\bmod N\) and the probability distribution of Diffie-Hellman secret keys for many users
- Two-sources randomness extractors in finite fields and in elliptic curves
- Studying the performance of artificial neural networks on problems related to cryptography
This page was built for publication: On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354276)
