On the unpredictability of bits of the elliptic curve Diffie-Hellman scheme

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

34 Citations (Scopus)


Let E/Fp be an elliptic curve, and G ∈ E/Fp. Define the Diffie-Hellman function 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.

Original languageEnglish
Title of host publicationAdvances in cryptology - crypto 2001
Subtitle of host publication21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings
EditorsJoe Kilian
Place of PublicationBerlin Germany
PublisherSpringer, Springer Nature
Number of pages12
Volume2139 LNCS
ISBN (Print)3540424563, 9783540424567
Publication statusPublished - 2001
Event21st Annual International Cryptology Conference - Santa Barbara, USA
Duration: 19 Aug 200123 Aug 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2139 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference21st Annual International Cryptology Conference
CitySanta Barbara, USA


Dive into the research topics of 'On the unpredictability of bits of the elliptic curve Diffie-Hellman scheme'. Together they form a unique fingerprint.

Cite this