Cryptology ePrint Archive: Report 2021/1062

On the Nonsingularity and Equivalence of NFSRs

Yingyin Pan and Jianghua Zhong and Dongdai Lin

Abstract: Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. In particular, Galois NFSRs with terminal bits are used in the typical stream ciphers Grain and Trivium. One security criterion for the design of stream ciphers is to assure their used NFSRs are nonsingular. The nonsingularity is well solved for Fibonacci NFSRs, whereas it is not for Galois NFSRs. In addition, some types of Galois NFSRs equivalent to Fibonacci ones have been found. However, whether there exist new types of such Galois NFSRs remains unknown. The paper first considers the nonsingularity of Galois NFSRs. Some necessary/sufficient conditions are presented. The paper then concentrates on the equivalence between Galois NFSRs and Fibonacci ones. Some necessary conditions for Galois NFSRs equivalent to Fibonacci ones are provided. The Galois NFSRs with terminal bits equivalent to a given Fibonacci one are enumerated. Moreover, two classes of nonsingular Galois NFSRs with terminal bits are found to be the new types of Galois NFSRs equivalent to Fibonacci ones.

Category / Keywords: secret-key cryptography / Nonlinear feedback shift register, Boolean function, Stream cipher, Equivalence, Nonsingularity

Date: received 15 Aug 2021, last revised 27 Sep 2021

Contact author: panyingyin at iie ac cn

Available format(s): PDF | BibTeX Citation

Note: We added some results.

Version: 20210927:121623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]