A nonuniform algorithm for the hidden number problem in subgroups

Boneh and Venkatesan have proposed a polynomial time algorithm in a non-uniform model for recovering a "hidden" element α ∈ F_p, where p is prime, from very short strings of the most significant bits of the residue of αt modulo p for several randomly chosen t ∈ F_p. Here we modify the scheme and amplify the uniformity of distribution of the 'multipliers' t and thus extend this result to subgroups of F_p*, which are more relevant to practical usage. As in the work of Boneh and Venkatesan, our result can be applied to the bit security of Diffie-Hellman related encryption schemes starting with subgroups of very small size, including all cryptographically interesting subgroups.