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