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 l ow hamming weight discrete logarithm problem. In this version of the discre te log problem, we are required to find a discrete logarithm in a finite gr oup of order approximately 2(m), given that the unknown logarithm has a spe cified number of 1's, say t, in its binary representation. Heiman and Odlyz ko presented the first algorithms for this problem. Unpublished improvement s by Coppersmith include a deterministic algorithm with complexity O (m (m/ 2 t/2 )), and a Las Vegas algorithm with complexity O (roott (m/2 t/2)). We perform an average-case analysis of Coppersmith's deterministic algorith m. The average-case complexity achieves only a constant factor speed-up ove r the worst-case. Therefore, we present a generalized version of Coppersmit h's algorithm, utilizing a combinatorial set system that we call a splittin g system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with compl exity O (t(3/2) (log m) (m/2 t/2)). We also present some explicit construct ions for splitting systems that make use of perfect hash families.