Jerusalem Mathematics Colloquium

Thursday, 11th November 2004, 4:00 pm
Mathematics Building, Lecture Hall 2

Professor Stephen Miller
(Rutgers University)

"Expander Graphs, GRH, and the Elliptic Curve Discrete Logarithm"

Abstract: Cryptographic applications using elliptic curves typically select curves based on their number of points over a finite field. It is therefore natural to ask whether or not the difficulty of the discrete logarithm problem (DLOG) is uniform among such curves. If so, this would justify the above common practice. I will discuss a recent such equivalence. Applications of this theorem range from justifying the security of curves proposed as international standards, to the security of a potentially widely used antipiracy algorithm.

The proof relies upon the Generalized Riemann Hypothesis (GRH) and utilizes expander graphs whose vertices represent elliptic curves, and whose edges represent maps between them. This construction of expanders turns out to be more general: for example assuming GRH and letting Q be a large prime, the graph on (Z/QZ)^* connecting x to px, p a prime < (log Q)^3, is an expander.

This is a joint work with David Jao and Ramarathnam Venkatesan, Microsoft Research Cryptography Group.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2004-05
List of talks, 2003-04
List of talks, 2002-03
List of talks, 2001-02
List of talks, 2000-01
List of talks, 1998-99
List of talks, 1997-98