# On the Unpredictability of Bits of the Elliptic Curve Diffie--Hellman Scheme

**Authors:**

*D. Boneh and I. Shparlinski*

** Abstract: **

Let E/Fp be an elliptic curve, and G in E/F_{p}. Define the
Diffie--Hellman function on E/F_{p} as DH_{E,G}(aG,bG) = abG.
We show that if there is an efficient algorithm for predicting the LSB
of the x or y coordinate of abG given (E,G,aG,bG) for a
certain family of elliptic curves, then there is an algorithm for
computing the Diffie-Hellman function on all curves in this family.
This seems stronger than the best analogous results for the
Diffie--Hellman function in F_{p}. Boneh and Venkatesan showed
that in F_{p} computing approximately (log p)^{1/2} of the bits
of the Diffie-Hellman secret is as hard as computing the entire
secret. Our results show that just predicting one bit of the Elliptic
Curve Diffie-Hellman secret in a family of curves is as hard as
computing the entire secret.

** Reference:**

In proceedings of Crypto '2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp. 201-212, 2001

**Full paper:**
PostScript

**Related papers:**
A related result about Diffie-Hellman in F_{p}:
Boneh-Venkatesan