A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials
This work addresses a key bottleneck in cryptanalysis for security researchers, offering a more memory-efficient solution, though it is incremental as it builds on existing approaches.
The paper tackles the problem of computing low-weight multiples of binary polynomials, which is crucial for correlation attacks on LFSR-based stream ciphers, by introducing a discrete logarithm-based method that achieves much lower memory complexity with comparable time complexity to the best existing algorithm.
Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and has much lower memory complexity requirements with a comparable time complexity.