International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the Security of Diffie--Hellman Bits

Authors:
Maria Isabel Gonzalez Vasco
Igor E. Shparlinski
Download:
URL: http://eprint.iacr.org/2000/020
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11364,
  title={On the Security of Diffie--Hellman Bits},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Diffie-Hellman, Exponential Sums},
  url={http://eprint.iacr.org/2000/020},
  note={ igor@comp.mq.edu.au 11096 received 18 May 2000},
  author={Maria Isabel Gonzalez Vasco and Igor E. Shparlinski},
  year=2000
}