On the security of Diffie-Hellman bits

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element a: of a finite field IFp of p elements from rather short strings of the most significant bits of the remainder module p of at for several values of t selected uniformly at random from IFp*. 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 IFp*. Namely, our results apply to subgroups of size at least p(1/3+E) for all primes p and to subgroups of size at least p(epsilon) for almost all primes p, for any fixed epsilon > 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.