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

Authors: D. Boneh and I. Shparlinski

Let E/Fp be an elliptic curve, and G in E/Fp. Define the Diffie--Hellman function on E/Fp as DHE,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 Fp. Boneh and Venkatesan showed that in Fp 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.

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 Fp:    Boneh-Venkatesan