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.