Welcome to the resource topic for 2003/049
Title:
Hidden Number Problem in Small Subgroups
Authors: Igor Shparlinski, Arne Winterhof
Abstract: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ä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.
ePrint: https://eprint.iacr.org/2003/049
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .