Tutte seminar - Dimitar Jetchev

Friday, August 22, 2008 3:30 pm - 4:30 pm EDT (GMT -04:00)

Bit Security of Elliptic Curve Diffie-Hellman Secret Keys

Speaker: Dimitar Jetchev
Affiliation: Institut des Hautes Études Scientifiques
Room: Mathematics & Computer Building (MC) 5158


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.