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

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.