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

Abstract

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
Pages257-268
Number of pages12
ISBN (Print)3764365102
DOIs
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
Volume20

Conference

ConferenceWorkshop on Cryptography and Computational Number Theory (CCNT 99)
CountrySingapore
CitySingapore
Period22/11/9926/11/99

Keywords

  • REDUCTION
  • NUMBERS

Cite this