University of Georgia
Mathematics Department Colloquium
Daniel Lieman
University of Missouri
January 27 2000
The security of the Diffie-Hellman Key exchange
protocol (or: an improved bound on the number of zeros of a sparse
polynomial)
Abstract:
One of the most important practical problems in cryptography is
that of
constructing a protocol whereby two parties can (with no prior exchange of
data) share a secret over an open communications channel without an
eavesdropper being able to infer the secret. Once this shared secret has
been established, the parties may then use it to encrypt communications.
These sorts of so-called "key exchange" protocols are widely implemented
in current internet and intranet products.
In this talk, we'll study the most popular key exchange protocol
(Diffie-Hellman), and show that it is secure against statistical attacks;
more precisely, we'll see that the values used in the D-H protocol are
uniformly distributed in some sense. Our method depends on a beautiful
problem in number theory and algebraic geometry which has proved
remarkably resistent to attack: that of bounding the number of roots of an
extremely sparse (high-degree) polynomial over a large prime field.
Our improved bounds also give rise to improved bounds on various types of
exponential sums, which have both mathematical and cryptographical
consequences.
This talk will be self-contained - no prior knowledge of cryptography or
Diffie-Hellman will be necessary. This talk presents joint work with
Canetti, Friedlander, Konyagin, Larsen and Shparlinski.