Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A hidden number problem in small subgroups

Authors: Igor Shparlinski and Arne Winterhof
Journal: Math. Comp. 74 (2005), 2073-2080
MSC (2000): Primary 11T23, 11T71, 11Y16, 94A60
Published electronically: April 5, 2005
MathSciNet review: 2164114
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T23, 11T71, 11Y16, 94A60

Retrieve articles in all journals with MSC (2000): 11T23, 11T71, 11Y16, 94A60

Additional Information

Igor Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
MR Author ID: 192194

Arne Winterhof
Affiliation: RICAM, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040 Linz, Austria

Keywords: Hidden number problem, Diffie–Hellman key exchange, lattice reduction, exponential sums, Waring problem in finite fields
Received by editor(s): March 3, 2003
Published electronically: April 5, 2005
Article copyright: © Copyright 2005 American Mathematical Society