Paper 2021/1062
On the Nonsingularity and Equivalence of NFSRs
Yingyin Pan, 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.
Note: We added some results.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Nonlinear feedback shift registerBoolean functionStream cipherEquivalenceNonsingularity
- Contact author(s)
- panyingyin @ iie ac cn
- History
- 2021-09-27: last of 2 revisions
- 2021-08-16: received
- See all versions
- Short URL
- https://ia.cr/2021/1062
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1062,
author = {Yingyin Pan and Jianghua Zhong and Dongdai Lin},
title = {On the Nonsingularity and Equivalence of {NFSRs}},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1062},
year = {2021},
url = {https://eprint.iacr.org/2021/1062}
}
