Advertisement
Published in:
2008 | OriginalPaper | Chapter
Bits Security of the Elliptic Curve Diffie–Hellman Secret Keys
Authors : Dimitar Jetchev, Ramarathnam Venkatesan
Published in: Advances in Cryptology – CRYPTO 2008
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We show that the least significant bits (LSB) of the elliptic curve Diffie–Hellman secret keys are hardcore. More precisely, we prove that if one can efficiently predict the LSB with non-negligible advantage on a polynomial fraction of all the curves defined over a given finite field
$\mathbb{F}_p$
, then with polynomial factor overhead, one can compute the entire Diffie–Hellman secret on a polynomial fraction of all the curves over the same finite field. Our approach is based on random self-reducibility (assuming GRH) of the Diffie–Hellman problem among elliptic curves of the same order. As a part of the argument, we prove a refinement of H. W. Lenstra’s lower bounds on the sizes of the isogeny classes of elliptic curves, which may be of independent interest.