Paper 2012/112

On The Nonlinearity of Maximum-length NFSR Feedbacks

Meltem Sonmez Turan

Abstract

Linear Feedback Shift Registers (LFSRs) are the main building block of many classical stream ciphers; however due to their inherent linearity, most of the LFSR-based designs do not offer the desired security levels. In the last decade, using Nonlinear Feedback Shift Registers(NFSRs) in stream ciphers became very popular. However, the theory of NFSRs is not well-understood, and there is no efficient method that constructs a cryptographically strong feedback function with maximum period and also, given a feedback function it is hard to predict the period. In this paper, we study the maximum-length NFSRs, focusing on the nonlinearity of their feedback functions. First, we provide some upper bounds on the nonlinearity of the maximum-length feedback functions, and then we study the feedback functions having nonlinearity 2 in detail. We also show some techniques to improve the nonlinearity of a given feedback function using cross-joining.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
meltemsturan @ gmail com
History
2012-02-29: received
Short URL
https://ia.cr/2012/112
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/112,
      author = {Meltem Sonmez Turan},
      title = {On The Nonlinearity of Maximum-length NFSR Feedbacks},
      howpublished = {Cryptology ePrint Archive, Paper 2012/112},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/112}},
      url = {https://eprint.iacr.org/2012/112}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.