On certain exponential sums and the distribution of Diffie-Hellman triples

Ran Canetti*, John Friedlander, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)

Abstract

Let g be a primitive root modulo a prime p. It is proved that the triples (gx, gy, gxy), x, y = 1, ..., 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 ε > 0 be fixed. Then Σp-1 x,y-1 exp (2πiagx+bgy+cgxy/p) = O(p31/16+ε) uniformly for any integers a, b, c with gcd(a, b, c, p) = 1. Incomplete sums are estimated as well. The question is motivated by the assumption, often made in cryptography, that the triples (gx, gy, gxy) cannot be distinguished from totally random triples in feasible computation time. The 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 bits.

Original languageEnglish
Pages (from-to)799-812
Number of pages14
JournalJournal of the London Mathematical Society
Volume59
Issue number3
Publication statusPublished - Jun 1999

Fingerprint

Dive into the research topics of 'On certain exponential sums and the distribution of Diffie-Hellman triples'. Together they form a unique fingerprint.

Cite this