A nonlinear-feedback shift register (NLFSR) is a

shift register A shift register is a type of digital circuit using a cascade of flip-flop (electronics), flip-flops where the output of one flip-flop is connected to the input of the next. They share a single clock signal, which causes the data stored in the syst ...

whose input bit is a non-linear function of its previous state. For an n-bit shift register ''r'' its next state is defined as:

r_(b_0, b_1, b_2, \ldots, b_)=r_(b_1, b_2, \ldots, f(b_0, b_1, b_2, \ldots, b_))

, where ''f'' is the non-linear feedback function.

Applications

Nonlinear-feedback shift registers are components in modern

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystrea ...

s, especially in

RFID Radio-frequency identification (RFID) uses electromagnetic fields to automatically identify and track tags attached to objects. An RFID system consists of a tiny radio transponder called a tag, a radio receiver, and a transmitter. When tri ...

and

smartcard A smart card (SC), chip card, or integrated circuit card (ICC or IC card), is a card used to control access to a resource. It is typically a plastic credit card-sized card with an embedded integrated circuit (IC) chip. Many smart cards include a ...

applications. NLFSRs are known to be more resistant to cryptanalytic attacks than Linear Feedback Shift Registers (

LFSR In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a sh ...

s).

Generating

It is known how to generate an ''n''-bit NLFSR of maximal length ''2ⁿ'', generating a

De Bruijn sequence In combinatorics, combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet (computer science), alphabet ''A'' is a cyclic sequence in which every possible length-''n'' String (computer science)#Formal theory, stri ...

, by extending a maximal-length LFSR with ''n'' stages; but the construction of other large NLFSRs with guaranteed long periods remains an open problem. Using bruteforce methods, a list of maximum-period ''n''-bit NLFSRs for n ≤ 25 has been made as well as for n=27. New methods suggest usage of

evolutionary algorithms Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least Approximation, approximately, for which no exact or satisfactory solution methods are k ...

in order to introduce non-linearity. In these works, an evolutionary algorithm learns how to apply different operations on strings from

to enhance their quality to meet the criteria of a fitness function, here the

NIST The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...

protocol,NIS
" A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications"
NIST, Special Publication April 2010 effectively.

NLFSR-based ciphers

* Achterbahn *

Grain A grain is a small, hard, dry fruit (caryopsis) – with or without an attached husk, hull layer – harvested for human or animal consumption. A grain crop is a grain-producing plant. The two main types of commercial grain crops are cereals and ...

KeeLoq KeeLoq is a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register (NLFSR). The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was ...

algorithm *

LIZARD Lizard is the common name used for all Squamata, squamate reptiles other than snakes (and to a lesser extent amphisbaenians), encompassing over 7,000 species, ranging across all continents except Antarctica, as well as most Island#Oceanic isla ...

Trivium The trivium is the lower division of the seven liberal arts and comprises grammar, logic, and rhetoric. The trivium is implicit in ("On the Marriage of Philology and Mercury") by Martianus Capella, but the term was not used until the Carolin ...

VEST A waistcoat ( UK and Commonwealth, or ; colloquially called a weskit) or vest ( US and Canada) is a sleeveless upper-body garment. It is usually worn over a dress shirt and necktie and below a coat as a part of most men's formal wear. It ...

References

Stream ciphers Radio-frequency identification {{crypto-stub