TR00-045 Authors: Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Publication: 2nd July 2000 13:42

Downloads: 2513

Keywords:

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

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.