Abstract
Nonlinear feedback shift registers (NFSRs) have been widely used in hardware-oriented stream ciphers. Whether a family of NFSR sequences includes an affine sub-family of sequences is a fundamental problem for NFSRs. Let f be the characteristic function of an NFSR whose algebraic degree is d. The previous necessary condition on affine sub-families of NFSR sequences given by Zhang et al. [IEEE Trans. Inf. Theory, 65(2), 2019] provides a set of possible affine NFSRs defined by the variables appearing in the terms with the maximum degree d in f, which leads to the fastest algorithm so far for finding affine sub-families. In this paper, a new necessary condition for the existence of an affine sub-family in a family of NFSR sequences is proposed. The new necessary condition is further concerned with the algebraic relations between the terms with the maximum degree d in f, not only the variables involved in them, and so yields a smaller space of possible affine sub-families and less computation complexity for a large number of NFSRs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Golomb, S. Shift Register Sequences, Aegean Park Press, 1982
Jiang, Yupeng, Lin, Dongdai: On affine sub-families of Grain-like structures. Des. Codes. Cryptogr. 82(3), 531–542 (2017)
Ma, Zhen, Qi, Wen-Feng., Tian, Tian: On affine sub-families of the NFSR in Grain. Des. Codes. Cryptogr. 75(2), 199–212 (2015)
Mykkeltveit, Johannes, Siu, Man-Keung., Tong, Po.: On the Cycle Structure of Some Nonlinear Shift Register Sequences. Information and Control 43(2), 202–215 (1979)
Matthew J. B. Robshaw and Olivier Billet, New Stream Cipher Designs - The eSTREAM Finalists, Lecture Notes in Computer Science, 4986, Springer, (2008)
Tian, Tian, Qi, Wen-Feng.: On the largest affine sub-families of a family of NFSR sequences. Des. Codes Cryptogr. 71(1), 163–181 (2014)
Zhang, Jia-Min., Tian, Tian, Qi, Wen-Feng., Zheng, Qun-Xiong.: On the Affine Sub-Families of Quadratic NFSRs. IEEE Trans. Inf. Theory 64(4), 2932–2940 (2018)
Zhang, Jia-Min., Tian, Tian, Qi, Wen-Feng., Zheng, Qun-Xiong.: A New Method for Finding Affine Sub-Families of NFSR Sequences. IEEE Trans. Inf. Theory 65(2), 1249–125 (2019)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the National Natural Science Foundation of China under Grants 61672533.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Che, C., Tian, T. Further Results on Affine Sub-Families of NFSR Sequences. Cryptogr. Commun. 16, 309–321 (2024). https://doi.org/10.1007/s12095-023-00663-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-023-00663-1
Keywords
- Stream Ciphers
- Nonlinear feedback Shift Registers
- a Family of NFSR Sequences
- an Affine Sub-Family of Sequences