Advanced

Another look at weak feedback polynomials in the nonlinear combiner

Hell, Martin LU and Brynielsson, Lennart (2009) IEEE International Symposium on Information Theory (ISIT), 2009 p.1115-1119
Abstract
Feedback polynomials with low degree multiples of low weight should be avoided in linear feedback shift registers when used in nonlinear combiners. We consider another class of weak feedback polynomials, namely the class when taps are located in small groups. This class was introduced in 2004 demonstrating that the resulting distinguishing attack can sometimes be better than the one using low weight multiples. In this paper we take another look at these polynomials and give further insight to the theory behind the attack complexity. Using the Walsh transform we show an easy way to determine the attack complexity given a polynomial. Further, we show that the size of the vectors should sometimes be larger than previously known. We also give... (More)
Feedback polynomials with low degree multiples of low weight should be avoided in linear feedback shift registers when used in nonlinear combiners. We consider another class of weak feedback polynomials, namely the class when taps are located in small groups. This class was introduced in 2004 demonstrating that the resulting distinguishing attack can sometimes be better than the one using low weight multiples. In this paper we take another look at these polynomials and give further insight to the theory behind the attack complexity. Using the Walsh transform we show an easy way to determine the attack complexity given a polynomial. Further, we show that the size of the vectors should sometimes be larger than previously known. We also give a simple relation showing when the new attack will outperform the simple attack based on low weight multiples. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to conference
publication status
published
subject
keywords
weak feedback polynomials, stream ciphers, cryptography, LFSR
pages
5 pages
conference name
IEEE International Symposium on Information Theory (ISIT), 2009
external identifiers
  • WOS:000280141400227
  • Scopus:70449481609
language
English
LU publication?
yes
id
8ae1f495-3157-457d-bb79-6dc4b46df54c (old id 1471499)
date added to LUP
2009-09-08 08:50:58
date last changed
2016-10-13 05:00:56
@misc{8ae1f495-3157-457d-bb79-6dc4b46df54c,
  abstract     = {Feedback polynomials with low degree multiples of low weight should be avoided in linear feedback shift registers when used in nonlinear combiners. We consider another class of weak feedback polynomials, namely the class when taps are located in small groups. This class was introduced in 2004 demonstrating that the resulting distinguishing attack can sometimes be better than the one using low weight multiples. In this paper we take another look at these polynomials and give further insight to the theory behind the attack complexity. Using the Walsh transform we show an easy way to determine the attack complexity given a polynomial. Further, we show that the size of the vectors should sometimes be larger than previously known. We also give a simple relation showing when the new attack will outperform the simple attack based on low weight multiples.},
  author       = {Hell, Martin and Brynielsson, Lennart},
  keyword      = {weak feedback polynomials,stream ciphers,cryptography,LFSR},
  language     = {eng},
  pages        = {1115--1119},
  title        = {Another look at weak feedback polynomials in the nonlinear combiner},
  year         = {2009},
}