Cryptology ePrint Archive: Report 2015/252
Linearization of Multi-valued Nonlinear Feedback Shift Registers
Haiyan Wang, Jianghua Zhong, Dongdai Lin
Abstract: The Linearization of Nonlinear feedback shift registers (NFSRs) is to find their state transition matrices. In this paper,
we investigate the linearization multi-valued NFSRs by considering it as a logical network via a semi-tensor product approach.
A new state transition matrix is found for an multi-valued NFSR, which can be simply computed from the truth table of its
feedback function, and the new state transition matrix is easier to compute and is more explicit. First, a linear representation of a
multi-valued NFSR is given, based on which several necessary and sufficient conditions for the nonsingularity are given. Then,
some properties of the state transition matrice are provided, which are helpful to theoretically analyze NFSRs. Finally, we give
properties of a maximum length multi-valued NFSR and the linear representation of the general structure of an n-bit shift register
with updating functions.
Category / Keywords: secret-key cryptography / Shift register, Semi-tensor product, state transition matrix, Boolean network, Nonsingularity.
Date: received 17 Mar 2015
Contact author: wanghaiyan at iie ac cn
Available format(s): PDF | BibTeX Citation
Version: 20150319:073217 (All versions of this report)
Short URL: ia.cr/2015/252
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]