Hidden Number Problem in Small Subgroups

Igor Shparlinski

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden" element alpha in F_p, where p is prime, from rather short strings of the most significant bits of the residue of (alpha t) (mod p) for several randomly chosen t in F_p. Gonzalez Vasco and Shparlinski have recently extended this result to subgroups of F_p^* of order at least p^{1/3+epsilon} for all p and to subgroups of order at least p^epsilon for almost all p.

Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' t and thus extend this result to subgroups of order at least $log( p)/log( log(p))^{1-epsilon} for all primes p.

We give applications of our result to the bit security of the Diffie--Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

Joint work with Arne Winterhof

Return to main page

Last Modified: 7-03-2003