Cryptology ePrint Archive: Report 2014/536

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

Tian Tian and Jia-Min Zhang and 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.

Category / Keywords: Stream ciphers, nonlinear feedback shift registers, cascade connection of NFSRs, decomposition

Date: received 9 Jul 2014, last revised 9 Feb 2018

Contact author: tiantian_d at 126 com

Available format(s): PDF | BibTeX Citation

Version: 20180210:041234 (All versions of this report)

Short URL: ia.cr/2014/536


[ Cryptology ePrint archive ]