Further Results on the Decomposition of an NFSR Into the Cascade Connection of an NFSR Into an LFSR

Author

Jia-Min Zhang ; Wen-Feng Qi ; Tian Tian ; Zhong-Xiao Wang

Author_Institution

State Key Lab. of Math. Eng. & Adv. Comput., Zhengzhou Inf. Sci. & Technol. Inst., Zhengzhou, China

Volume

61

Issue

1

fYear

2015

fDate

Jan. 2015

Firstpage

645

Lastpage

654

Abstract

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. In this paper, we study the problem of decomposing an NFSR into the cascade connection of an NFSR into a linear feedback shift register (LFSR), which is a kind of concatenation of an NFSR and LFSR. A necessary and sufficient condition for such decomposition is provided and other algebraic properties about such decomposition are also studied. Based on these theoretical results, a binary decision diagram (BDD)-based algorithm for such decomposition is proposed. Compared with the previous algorithm proposed by Ma et al., our algorithm can find more accurate candidate LFSR and the algebraic properties presented in this paper guarantee that the memory requirement during our verification is linear in the size of the BDD of the NFSRs characteristic function.

Keywords

Boolean functions; binary decision diagrams; cryptography; shift registers; Boolean function; LFSR; LFSR stream cipher design; NFSR decomposition; binary decision diagram-based algorithm; cascade connection; linear feedback shift register; memory requirement; nonlinear feedback shift registers; Binary decision diagrams; Boolean functions; Ciphers; Polynomials; Shift registers; Binary Decision Diagram; Boolean function; Cascade connection; Nonlinear feedback shift registers; Stream cipher; binary decision diagram; cascade connection; nonlinear feedback shift registers;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2014.2371542

Filename

6963418