Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: igor@ics.mq.edu.au

Arne Winterhof
Affiliation: RICAM, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040 Linz, Austria
Email: arne.winterhof@oeaw.ac.at

DOI: http://dx.doi.org/10.1090/S0025-5718-05-01797-7
PII: S 0025-5718(05)01797-7
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