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

Stinson, D.

doi:10.1090/S0025-5718-01-01310-2

Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem
HTML articles powered by AMS MathViewer

by D. R. Stinson PDF

Math. Comp. 71 (2002), 379-391 Request permission

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

N. Alon, Explicit construction of exponential sized families of $k$-independent sets, Discrete Math. 58 (1986), no. 2, 191–193. MR 829076, DOI 10.1016/0012-365X(86)90161-5
D. Coppersmith. Private communication to Scott Vanstone, December 1997.
Don Coppersmith and Gadiel Seroussi, On the minimum distance of some quadratic residue codes, IEEE Trans. Inform. Theory 30 (1984), no. 2, 407–411. MR 754880, DOI 10.1109/TIT.1984.1056861
Zbigniew J. Czech, George Havas, and Bohdan S. Majewski, Perfect hashing, Theoret. Comput. Sci. 182 (1997), no. 1-2, 1–143. MR 1463931, DOI 10.1016/S0304-3975(96)00146-6
R. Heiman. A note on discrete logarithms with special structure. Lecture Notes in Computer Science 658, 454–457 (Advances in Cryptology – EUROCRYPT ’92).
D. L. Kreher and D. R. Stinson. Combinatorial algorithms: generation, enumeration and search, CRC Press, 1999.
S. Bergmann and J. Marcinkiewicz, Sur les fonctions analytiques de deux variables complexes, Fund. Math. 33 (1939), 75–94 (French). MR 57, DOI 10.4064/fm-33-1-75-94
Kurt Mehlhorn, Data structures and algorithms. 1, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin, 1984. Sorting and searching. MR 756413, DOI 10.1007/978-3-642-69672-5
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
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.