[Resource Topic] 2000/020: On the Security of Diffie--Hellman Bits

Welcome to the resource topic for 2000/020

On the Security of Diffie–Hellman Bits

Authors: Maria Isabel Gonzalez Vasco, Igor E. Shparlinski


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 .