Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A hidden number problem in small subgroups
HTML articles powered by AMS MathViewer

by Igor Shparlinski and Arne Winterhof PDF
Math. Comp. 74 (2005), 2073-2080 Request permission

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
Similar Articles
Additional Information
  • Igor Shparlinski
  • Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
  • MR Author ID: 192194
  • 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
  • Received by editor(s): March 3, 2003
  • Published electronically: April 5, 2005
  • © Copyright 2005 American Mathematical Society
  • Journal: Math. Comp. 74 (2005), 2073-2080
  • MSC (2000): Primary 11T23, 11T71, 11Y16, 94A60
  • DOI: https://doi.org/10.1090/S0025-5718-05-01797-7
  • MathSciNet review: 2164114