On the security of Diffie-Hellman bits

María Isabel González Vasco, IE Shparlinski

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


Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element a: of a finite field IFp of p elements from rather short strings of the most significant bits of the remainder module p of at for several values of t selected uniformly at random from IFp*. We use some recent bounds of exponential sums to generalize this algorithm to the case when t is selected from a quite small subgroup of IFp*. Namely, our results apply to subgroups of size at least p(1/3+E) for all primes p and to subgroups of size at least p(epsilon) for almost all primes p, for any fixed epsilon > 0. We also use this generalization to improve (and correct) one of the statements of the aforementioned work about the computational security of the most significant bits of the Diffie-Hellman key.

Original languageEnglish
Title of host publicationCryptography and computational number theory
EditorsK. Y. Lam, Igor Shparlinski, H. Wang, C. P. Xing
Place of PublicationBasel
PublisherBirkhauser Verlag Basel
Number of pages12
ISBN (Print)3764365102
Publication statusPublished - 2001
EventWorkshop on Cryptography and Computational Number Theory (CCNT 99) - Singapore, Singapore
Duration: 22 Nov 199926 Nov 1999

Publication series

NameProgress in Computer Science and Applied Logic
PublisherBirkhauser Verlag


ConferenceWorkshop on Cryptography and Computational Number Theory (CCNT 99)




Dive into the research topics of 'On the security of Diffie-Hellman bits'. Together they form a unique fingerprint.

Cite this