|
Friday, August 22, 2008 |
|
|
|
|
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. |