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; Wen-Feng Qi

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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 ciphers nonlinear feedback shift registers cascade connection of NFSRs decomposition
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: 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}
}