Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem
Open Access
- 7 March 2001
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 71 (237), 379-392
- https://doi.org/10.1090/s0025-5718-01-01310-2
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 2m, given that the unknown logarithm has a specified number of l'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 (m (t/2m/2)), and a Las Vegas algorithm, with complexity O (√t (m/2 t/2)).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(t3/2 (log m) (t/2m/2)))). We also present some explicit constructions for splitting systems that make use of perfect hash families.This publication has 3 references indexed in Scilit:
- Perfect hashingTheoretical Computer Science, 1997
- Explicit construction of exponential sized families of k-independent setsDiscrete Mathematics, 1986
- On the minimum distance of some quadratic residue codes (Corresp.)IEEE Transactions on Information Theory, 1984