Cascade connection architectures of nonlinear feedback shift registers (NFSRs) have been widely used as the main components in the design of cryptographic algorithms, such as the Grain family of stream ciphers. It is known that the cascade connection of ann-stage NFSR into anm-stage NFSR is equivalent to an (n+m)-stage NFSR. However, the converse problem on decomposing an NFSR into the cascade connection of two smaller NFSRs has not been well addressed, which can be transformed to decomposing the characteristic functionhof the NFSR into the formh=f*gfor some nonlinearf,g, where “*” is a special composition of Boolean functions. In this paper, we present a complete and efficient method for such decomposition problem based on previous works. The framework of the decomposition consists of two steps. The first is to construct a candidate set forgas precise as possible, and the second is to verify each candidategand recover the correspondingf. We propose the notion of *-multiples of Boolean functions, and present three ways to take derivatives ofhto extract the low-degree *-multiples ofg, which are useful to determinegefficiently. Compared to existing methods, the new approach can provide a very small candidate set forgin most cases, with the size beingO(deg(h)), thereby achieving lower and more stable time costs in determining whetherhis *-reducible and enumerating all pairs (f,g) such thath=f*g(if it is *-reducible). Moreover, we show that the decomposition method also applies to shift-invariant maps, by establishing a connection between the *-product of Boolean functions and the composition of shift-invariant maps.

Nonlinear feedback shift registers (NFSRs) are an important building blocks in the design of stream ciphers over the past years. An NFSR is vulnerable to cryptanalysis if there are output sequences with low linear complexities. In this paper, we present a method to find output sequences of an NFSR with low linear complexities from a new perspective. Let f be the characteristic function of an NFSR, and let$f_{L}$be the linear part of f. First, we present some theoretical results in order to find sequences$\underline {a}\in G(f_{L})$such that$\underline {a}\in G(f)$. In particular, it is shown that if$f_{L}$has divisors of the form$g(x^{d})$, then$G(f)$is more likely to have linear sequences. Then, we introduce two kinds of isomorphisms of NFSRs which could be used to find more potential linear sequences in$G(f)$. Such isomorphisms induce a close relationship among the linear structures of NFSRs, whose realization relies on a type of decomposition of Boolean functions. As a generalization, we propose a framework to analyze the linear structure of a Galois NFSR. The idea is to focus on the Galois LFSR derived from the Galois NFSR by removing the nonlinear part, which can be transformed into an equivalent Fibonacci LFSR. Finally, we apply the results to some lightweight algorithms designed based on the cascade connections of NFSRs, and find several families of sequences generated by the main register of Lizard with linear complexities no more than 30.