Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Cryptography and Communications
Published in: Cryptography and Communications 3-4/2012

01-12-2012

On the nonlinearity of maximum-length NFSR feedbacks

Author: Meltem Sönmez Turan

Published in: Cryptography and Communications | Issue 3-4/2012

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 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.
previous article Applying cube attacks to stream ciphers in realistic scenarios
next article State cycles, initialization and the Trivium stream cipher

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Golomb, S.W.: Shift Register Sequences. Holden-Day, Inc., Laguna Hills (1967)MATH
2.
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)CrossRef
3.
Braeken, A., Lano, J.: On the (im)possibility of practical and secure nonlinear filters and combiners. In: Selected Areas in Cryptography, pp. 159–174 (2005)
4.
Hell, M., Johansson, T., Meier, W.: Grain-A Stream Cipher for Constrained Environments. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/010 (2005)
5.
Babbage, S., Dodd, M.: The Stream Cipher MICKEY (version 1). eSTREAM, ECRYPT Stream Cipher Project, Report 2005/015 (2005)
6.
De Cannière, C., Preneel, B.: Trivium Specifications. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/030 (2005)
7.
8.
Tsuneda, A., Kudo, K., Yoshioka, D., Inoue, T.: Maximal-period sequences generated by feedback-limited nonlinear shift registers. IEICE Trans. 90(10), 2079–2084 (2007)CrossRef
9.
Çalık, Ç., Sönmez Turan, M., Özbudak, F.: On feedback functions of maximum length nonlinear feedback shift registers. IEICE Trans. 93(6), 1226–1231 (2010)CrossRef
10.
de Bruijn, N.G.: A combinatorial problem. Proc. K. Ned. Acad. Wet. Ser. A 49(7), 758–764 (1946)MATH
11.
Gonzalo, R., Ferrero, D., Soriano, M.: Some properties of nonlinear feedback shift registers with maximum period. In: Proc. 6th Int. Conf. Telecommunications Systems (1998)
12.
Etzion, T., Lempel, A.: On the distribution of de Bruijn sequences of given complexity. IEEE Trans. Inf. Theory 30(4), 611–614 (1984)MathSciNetMATHCrossRef
13.
Wu, C.K.: Distribution of Boolean functions with nonlinearity 2(n − 2). In: Proceedings of ChinaCrypt’94, pp. 10–14. Springer, China (1994)
14.
Helleseth, T., Kløve, T.: The number of cross-join pairs in maximum length linear sequences. IEEE Trans. Inf. Theory 37(6), 1731–1733 (1991)MATHCrossRef
Metadata
Title
On the nonlinearity of maximum-length NFSR feedbacks
Author
Meltem Sönmez Turan
Publication date
01-12-2012
Publisher
Springer US
Published in
Cryptography and Communications / Issue 3-4/2012
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-012-0067-5

Other articles of this Issue 3-4/2012

Cryptography and Communications 3-4/2012 Go to the issue

OriginalPaper

A survey on fast correlation attacks

OriginalPaper

High order differential attacks on stream ciphers

OriginalPaper

Synthetic linear analysis with applications to CubeHash and Rabbit

OriginalPaper

Applying cube attacks to stream ciphers in realistic scenarios

OriginalPaper

Correlation attacks on combination generators

OriginalPaper

State cycles, initialization and the Trivium stream cipher

Premium Partner

    Image Credits