Welcome to the resource topic for
**2000/020**

**Title:**

On the Security of Diffie–Hellman Bits

**Authors:**
Maria Isabel Gonzalez Vasco, 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.

**ePrint:**
https://eprint.iacr.org/2000/020

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .