Paper 2000/020

On the Security of Diffie--Hellman Bits

Maria Isabel Gonzalez Vasco and Igor E. Shparlinski

Abstract

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element $\alpha$ of a finite field $\F_p$ of $p$ elements from rather short strings of the most significant bits of the remainder modulo $p$ of $\alpha t$ for several values of $t$ selected uniformly at random from $\F_p^*$. 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 $\F_p^*$. Namely, our results apply to subgroups of size at least $p^{1/3+ \varepsilon}$ for all primes $p$ and to subgroups of size at least $p^{\varepsilon}$ for almost all primes $p$, for any fixed $\varepsilon >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.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Diffie-HellmanExponential Sums
Contact author(s)
igor @ comp mq edu au
History
2000-05-25: received
Short URL
https://ia.cr/2000/020
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/020,
      author = {Maria Isabel Gonzalez Vasco and Igor E.  Shparlinski},
      title = {On the Security of Diffie--Hellman Bits},
      howpublished = {Cryptology ePrint Archive, Paper 2000/020},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/020}},
      url = {https://eprint.iacr.org/2000/020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.