Remote Access Mathematics of Computation
Green Open Access

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

Abstract | References | Similar Articles | Additional Information


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?)

  • 1. N. Alon. Explicit construction of exponential sized families of $k$-independent sets, Discrete Math. 58 (1986), 191-193. MR 87e:05002
  • 2. D. Coppersmith. Private communication to Scott Vanstone, December 1997.
  • 3. D. Coppersmith and G. Seroussi. On the minimum distance of some quadratic residue codes, IEEE Trans. Inform. Theory 30 (1984), 407-411. MR 86c:94025
  • 4. Z. J. Czech, G. Havas and B. S. Majewski. Perfect hashing, Theoretical Computer Science 182 (1997), 1-143. MR 98h:68048
  • 5. R. Heiman. A note on discrete logarithms with special structure. Lecture Notes in Computer Science 658, 454-457 (Advances in Cryptology - EUROCRYPT '92).
  • 6. D. L. Kreher and D. R. Stinson. Combinatorial algorithms: generation, enumeration and search, CRC Press, 1999.
  • 7. F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes, North-Holland, 1977. MR 57:5408a; MR 57:5408b
  • 8. K. Mehlhorn. Data structures and algorithms 1: sorting and searching, Springer-Verlag, Berlin, 1984. MR 86e:68001
  • 9. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone. Handbook of applied cryptography, CRC Press, 1997. MR 99g:94015
  • 10. P. C. van Oorschot and M. J. Wiener. On Diffie-Hellman key agreement with short exponents. Lecture Notes in Computer Science 1070, 332-343 (Advances in Cryptology - EUROCRYPT '96), Springer, Berlin, 1996. CMP 97:04

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

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

American Mathematical Society