Friday, August 22, 2008
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Spring 2008


Dimitar Jetchev
Institut des Hautes Études Scientifiques

Bit Security of Elliptic Curve Diffie-Hellman Secret Keys

We show that if one can predict the least significant bit of the Diffie-Hellman secret keys for elliptic curves with non-negligible advantage on a polynomial fraction of all curves over a given finite field $\mathbb{F}_p$, then one can compute the entire Diffie-Hellman secret on a polynomial fraction of all curves over the same finite field. Our method combines rapid mixing properties of certain isogeny graphs, results due to Boneh and Shparlinski and a new refinement of H. Lenstra's lower bounds on the size of the isogeny classes corresponding to certain traces of Frobenius.

This is joint work with Ramarathnam Venkatesan.