On a Type of Linear Structures of NFSR Sequences

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

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2025-01, Vol.71 (1), p.768-782
Main Authors: Zhao, Xiao-Xin, Wang, Zhong-Xiao, Zheng, Qun-Xiong, Tang, Deng, Qi, Wen-Feng
Format: Article
Language:English
Subjects:
Boolean functions
cascade connection
Ciphers
Complexity theory
Indexes
isomorphism
linear complexity
Linear feedback shift registers
Linear systems
Logic gates
nonlinear feedback shift register
Polynomials
Reviews
Stream cipher
Vectors
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2024.3482451