[Resource Topic] 2021/1062: On the Nonsingularity and Equivalence of NFSRs

Welcome to the resource topic for 2021/1062

Title:
On the Nonsingularity and Equivalence of NFSRs

Authors: Yingyin Pan, Jianghua Zhong, 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.

ePrint: https://eprint.iacr.org/2021/1062

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .