Paper 2014/536

A Survey and New Results on the Decomposition of an NFSR into a Cascade Connection of Two Smaller NFSRs

Tian Tian, Jia-Min Zhang, Chen-Dong Ye, and Wen-Feng Qi

Abstract

Nonlinear feedback shift registers (NFSRs) are an important building block for stream ciphers. Given a cascade connection of two NFSRs, say NFSR$(f,g)$, it has been known for decades how to solve the characteristic function of the NFSR which is equivalent to NFSR$(f,g)$. However, the converse problem of decomposing an NFSR into a cascade connection of two smaller NFSRs is not completely solved, and only a special case has been studied recently. In this paper, a complete and feasible solution to the problem is given.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Stream ciphersnonlinear feedback shift registerscascade connection of NFSRsdecomposition
Contact author(s)
tiantian_d @ 126 com
History
2018-02-10: revised
2014-07-09: received
See all versions
Short URL
https://ia.cr/2014/536
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/536,
      author = {Tian Tian and Jia-Min Zhang and Chen-Dong Ye and Wen-Feng Qi},
      title = {A Survey and New Results on the Decomposition of an NFSR into a Cascade Connection of Two Smaller NFSRs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/536},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/536}},
      url = {https://eprint.iacr.org/2014/536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.