Finding low-weight polynomial multiples using discrete logarithm

Abstract

Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The best algorithms to solve this problem are based on a time memory tradeoff. Staying in this category, we will present a new approach using discrete logarithm rather than a direct representation of the involved polynomials. This provides an alternative to the previously known algorithms which improves in some case the computational complexity.