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 |
Abstract:
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.