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 .