On a Type of Linear Structures of NFSR Sequences
Xiao-Xin Zhao, Zhong-Xiao Wang, Qun-Xiong Zheng, Deng Tang, Wen‐Feng Qi · IEEE Transactions on Information Theory · 2024
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.