Paper 2015/252

Linearization of Multi-valued Nonlinear Feedback Shift Registers

Haiyan Wang, Jianghua Zhong, and 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Shift registerSemi-tensor productstate transition matrixBoolean networkNonsingularity.
Contact author(s)
wanghaiyan @ iie ac cn
History
2015-03-19: received
Short URL
https://ia.cr/2015/252
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/252,
      author = {Haiyan Wang and Jianghua Zhong and Dongdai Lin},
      title = {Linearization of Multi-valued Nonlinear Feedback Shift Registers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/252},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/252}},
      url = {https://eprint.iacr.org/2015/252}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.