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

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

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

American Mathematical Society