A nonlinear-feedback shift register (NLFSR) is a

shift register A shift register is a type of digital circuit using a cascade of 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 system to shift from one loc ...

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 keystream ...

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, a radio receiver and transmitter. When triggered by an electromag ...

and

smartcard A smart card, chip card, or integrated circuit card (ICC or IC card) is a physical electronic authentication device, used to control access to a resource. It is typically a plastic credit card-sized card with an embedded integrated circuit (IC) c ...

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 combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...

, 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 In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduc ...

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 sci ...

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 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 legum ...

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 wa ...

algorithm * LIZARD *

Trivium The trivium is the lower division of the seven liberal arts and comprises grammar, logic, and rhetoric. The trivium is implicit in ''De nuptiis Philologiae et Mercurii'' ("On the Marriage of Philology and Mercury") by Martianus Capella, but the ...

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. ...

References

Stream ciphers Radio-frequency identification {{crypto-stub