Paper 2003/049

Hidden Number Problem in Small Subgroups

Igor Shparlinski and Arne Winterhof

Abstract

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden" element $$, where $$ is prime, from rather short strings of the most significant bits of the residue of $$ modulo $$ for several randomly chosen $$. Gonzälez Vasco and the first author have recently extended this result to subgroups of $$ of order at least $$ for all $$ and to subgroups of order at least $$ for almost all $$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' $$ and thus extend this result to subgroups of order at least $$ for all primes $$. As in the above works, 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.