Tutte seminar - Dimitar Jetchev

Bit Security of Elliptic Curve Diffie-Hellman Secret Keys

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.