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

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},
      url = {https://eprint.iacr.org/2014/536}
}