A hidden number problem in small subgroups

Abstract:

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element $\alpha \in \mathbb {F}_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \mathbb {F}_p$. González Vasco and the first author have recently extended this result to subgroups of $\mathbb {F}_p^*$ of order at least $p^{1/3+\varepsilon }$ for all $p$ and to subgroups of order at least $p^\varepsilon$ 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-\varepsilon }$ for all primes $p$. 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.