International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Arne Winterhof

Publications

Year
Venue
Title
2004
PKC
2003
EPRINT
Hidden Number Problem in Small Subgroups
Igor E. Shparlinski Arne Winterhof
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$ modulo $p$ for several randomly chosen $t\in \F_p$. Gonz{\'a}lez Vasco and the first author have recently extended this result to subgroups of $\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.

Coauthors

Igor E. Shparlinski (2)