ECCC-Report TR00-045https://eccc.weizmann.ac.il/report/2000/045Comments and Revisions published for TR00-045en-usSun, 02 Jul 2000 13:42:40 +0300
Paper TR00-045
| On the Security of Diffie--Hellman Bits |
Maria Isabel Gonzalez Vasco,
Igor E. Shparlinski
https://eccc.weizmann.ac.il/report/2000/045Boneh 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
mo\-du\-lo $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.
Sun, 02 Jul 2000 13:42:40 +0300https://eccc.weizmann.ac.il/report/2000/045