Summary: Let \(\mathbb E/\mathbb F_p\) be an elliptic curve and \(G \in \mathbb E/\mathbb F_p\). Define the Diffie-Hellman function as \({\text{DH}}_{{\mathbb E},G}(aG,bG) = abG\). We show that if there is an efficient algorithm for predicting the least significant bit of the \(x\) or \(y\) coordinate of \(abG\) given \(\langle {\mathbb E},G,aG,bG\rangle\) 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 \(\mathbb F_p^*\). D. Boneh and R. Venkatesan [Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Proc. Crypto ‘96, Lect. Notes Comput. Sci. 1109, 129-142 (1996)] showed that in \(\mathbb 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.
For the entire collection see [Zbl 0969.00102].