In the study of linear feedback shift registers (LFSRs) for the design of stream ciphers, an important metric used for determining the security of the cipher is its linear complexity. This is defined as the length of the shortest LFSR that can mimic the generator's output. This is very important for the design of a stream cipher because of the Berlekamp-Massey Algorithm, which allows you to reconstruct the LFSR based on a number of bits equal to twice the linear complexity of the generator.

Obtaining the linear complexity of a stream cipher is one way to perform cryptanalysis of it. High linear complexity is a necessary condition for a stream cipher to be secure but not a sufficient condition.

Log in or register to write something here or to contact authors.