A new linearization method for nonlinear feedback shift registers

• Linearization of nonlinear feedback shift registers (NFSRs) is to find their state transition matrices.
• A Boolean network approach is used for the linearization of NFSRs.
• A new state transition matrix of an NFSR is found.
• Some properties of the new state transition matrix are provided as well.
• The properties are helpful to theoretically analyze NFSRs.

Nonlinear feedback shift registers (NFSRs) have been used as the main building blocks in many stream ciphers and convolutional decoders. The linearization of NFSRs is to find their state transition matrices. This paper uses a Boolean network approach to facilitate the linearization of NFSRs. A new state transition matrix is found for an NFSR, which can be simply computed from the truth table of its feedback function. Compared to the existing results, the new state transition matrix is easier to compute and is more explicit. Some properties of the matrix are provided, which are helpful to theoretically analyze NFSRs.