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)

 

Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem


Author: D. R. Stinson
Journal: Math. Comp. 71 (2002), 379-391
MSC (2000): Primary 68Q25, 11Y16, 05B30
Published electronically: March 7, 2001
MathSciNet review: 1863008
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately $2^m$, given that the unknown logarithm has a specified number of 1's, say $t$, in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity $O \left( m \left(\begin{smallmatrix}m / 2\ t / 2\end{smallmatrix}\right) \right) $, and a Las Vegas algorithm with complexity

$O \left( \sqrt{t} \left(\begin{smallmatrix}m / 2\ t / 2\end{smallmatrix}\right)\right) $.

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with complexity $O \left( t^{3/2} \, (\log m) \, \left(\begin{smallmatrix}{m / 2} \ {t / 2}\end{smallmatrix}\right)\right) $. We also present some explicit constructions for splitting systems that make use of perfect hash families.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68Q25, 11Y16, 05B30

Retrieve articles in all journals with MSC (2000): 68Q25, 11Y16, 05B30


Additional Information

D. R. Stinson
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo Ontario, N2L 3G1, Canada
Email: dstinson@uwaterloo.ca

DOI: http://dx.doi.org/10.1090/S0025-5718-01-01310-2
PII: S 0025-5718(01)01310-2
Keywords: Discrete logarithm problem, baby-step giant-step algorithm, splitting system
Received by editor(s): June 22, 1999
Received by editor(s) in revised form: May 8, 2000
Published electronically: March 7, 2001
Article copyright: © Copyright 2001 American Mathematical Society