Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4582703 | Finite Fields and Their Applications | 2016 | 15 Pages |
Abstract
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 can take advantage of the structure of the polynomial. In some cases it has much lower memory complexity requirements with a comparable time complexity.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Pietro Peterlongo, Massimiliano Sala, Claudia Tinnirello,