Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 2/2022

20-01-2022

A generic method for investigating nonsingular Galois NFSRs

Authors: Xiao-Juan Wang, Tian Tian, Wen-Feng Qi

Published in: Designs, Codes and Cryptography | Issue 2/2022

Login to get access
share
SHARE

Abstract

Let n be a positive integer. An n-stage Galois NFSR has n registers and each register is updated by a feedback function. Then a Galois NFSR is called nonsingular if every register generates (strictly) periodic sequences, i.e., no branch points. In this paper, a generic method for investigating nonsingular Galois NFSRs is provided. Two fundamental concepts that are standard Galois NFSRs and the simplified feedback function of a standard Galois NFSR are proposed. Based on the new concepts, a sufficient condition is given for nonsingular Galois NFSRs. In particular, for the class of Galois NFSRs with linear simplified feedback functions, a necessary and sufficient condition is presented.
Appendix
Available only for authorised users
Footnotes
1
A Galois NFSR is called an autonomous binary machine in [9]. Please refer to Fig. II-14 in [9].
 
Literature
1.
go back to reference Ågren M., Hell M., Johansson T., Meier W.: Grain-128a: a new version of grain-128 with optional authentication. IJWMC 5(1), 48–59 (2011). CrossRef Ågren M., Hell M., Johansson T., Meier W.: Grain-128a: a new version of grain-128 with optional authentication. IJWMC 5(1), 48–59 (2011). CrossRef
2.
go back to reference Canteaut A., Trabbia M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel, Bart (ed), Advances in Cryptology—EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14–18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, Springer, pp. 573–588 (2000). Canteaut A., Trabbia M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel, Bart (ed), Advances in Cryptology—EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14–18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, Springer, pp. 573–588 (2000).
3.
go back to reference Canteaut A., Carpov S., Fontaine C., Lepoint T., Naya-Plasencia M., Paillier P., Sirdey R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. J. Cryptol. 31(3), 885–916 (2018). MathSciNetCrossRef Canteaut A., Carpov S., Fontaine C., Lepoint T., Naya-Plasencia M., Paillier P., Sirdey R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. J. Cryptol. 31(3), 885–916 (2018). MathSciNetCrossRef
4.
go back to reference Chose P., Joux A., Mitton M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, Lars R. (ed), Advances in Cryptology—EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of Lecture Notes in Computer Science, Springer, pp. 209–221 (2002). Chose P., Joux A., Mitton M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, Lars R. (ed), Advances in Cryptology—EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of Lecture Notes in Computer Science, Springer, pp. 209–221 (2002).
5.
go back to reference Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, Eli (ed), Advances in Cryptology—EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, Springer, pp. 345–359 (2003). Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, Eli (ed), Advances in Cryptology—EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, Springer, pp. 345–359 (2003).
6.
go back to reference Courtois N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, Dan (ed), Advances in Cryptology—CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, Springer, pp. 176–194 (2003). Courtois N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, Dan (ed), Advances in Cryptology—CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, Springer, pp. 176–194 (2003).
7.
go back to reference De Cannière C., Preneel B.: Trivium. In: Robshaw and Billet [19], pp. 244–266. De Cannière C., Preneel B.: Trivium. In: Robshaw and Billet [19], pp. 244–266.
8.
go back to reference Dubrova E.: A transformation from the fibonacci to the galois nlfsrs. IEEE Trans. Inf. Theory 55(11), 5263–5271 (2009). MathSciNetCrossRef Dubrova E.: A transformation from the fibonacci to the galois nlfsrs. IEEE Trans. Inf. Theory 55(11), 5263–5271 (2009). MathSciNetCrossRef
9.
go back to reference Golomb S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1982). MATH Golomb S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1982). MATH
10.
go back to reference Hell M., Johansson T., Maximov A., Meier W.: The grain family of stream ciphers. In: Robshaw and Billet [19], pp. 179–190. Hell M., Johansson T., Maximov A., Meier W.: The grain family of stream ciphers. In: Robshaw and Billet [19], pp. 179–190.
11.
go back to reference Honggang H., Gong G.: Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions. Int. J. Found. Comput. Sci. 22(6), 1317–1329 (2011). MathSciNetCrossRef Honggang H., Gong G.: Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions. Int. J. Found. Comput. Sci. 22(6), 1317–1329 (2011). MathSciNetCrossRef
12.
go back to reference Johansson T., Jönsson F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare, Mihir (ed.), Advances in Cryptology—CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings, volume 1880 of Lecture Notes in Computer Science, Springer, pp. 300–315 (2000). Johansson T., Jönsson F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare, Mihir (ed.), Advances in Cryptology—CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings, volume 1880 of Lecture Notes in Computer Science, Springer, pp. 300–315 (2000).
13.
go back to reference Lu Y., Vaudenay S.: Faster correlation attack on bluetooth keystream generator E0. In: Franklin, Matthew K. (ed), Advances in Cryptology—CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, Springer, pp. 407–425 (2004). Lu Y., Vaudenay S.: Faster correlation attack on bluetooth keystream generator E0. In: Franklin, Matthew K. (ed), Advances in Cryptology—CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, Springer, pp. 407–425 (2004).
14.
go back to reference Robshaw M.J.B., Billet, O. (eds).: New Stream Cipher Designs—The eSTREAM Finalists, volume 4986 of Lecture Notes in Computer Science. Springer, Heidelberg (2008). Robshaw M.J.B., Billet, O. (eds).: New Stream Cipher Designs—The eSTREAM Finalists, volume 4986 of Lecture Notes in Computer Science. Springer, Heidelberg (2008).
15.
go back to reference Simpson L., Boztas S.: State cycles, initialization and the trivium stream cipher. Cryptogr. Commun. 4(3–4), 245–258 (2012). MathSciNetCrossRef Simpson L., Boztas S.: State cycles, initialization and the trivium stream cipher. Cryptogr. Commun. 4(3–4), 245–258 (2012). MathSciNetCrossRef
16.
go back to reference Tian T., Qi W.-F., Ye C.-D., Xie X.-F.: Spring: a family of small hardware-oriented block ciphers based on nfsrs. J. Cryptol. Res. 6(6), 815–834 (2019). Tian T., Qi W.-F., Ye C.-D., Xie X.-F.: Spring: a family of small hardware-oriented block ciphers based on nfsrs. J. Cryptol. Res. 6(6), 815–834 (2019).
17.
go back to reference Wu H.-J.: Acorn: a lightweight authenticated cipher (v3). Candidate for the CAESAR Competition (2016). Wu H.-J.: Acorn: a lightweight authenticated cipher (v3). Candidate for the CAESAR Competition (2016).
18.
19.
go back to reference Zhao X.-X., Qi W.-F., Zhang J.-M.: Further results on the equivalence between galois nfsrs and fibonacci nfsrs. Des. Codes Cryptogr. 88(1), 153–171 (2020). MathSciNetCrossRef Zhao X.-X., Qi W.-F., Zhang J.-M.: Further results on the equivalence between galois nfsrs and fibonacci nfsrs. Des. Codes Cryptogr. 88(1), 153–171 (2020). MathSciNetCrossRef
Metadata
Title
A generic method for investigating nonsingular Galois NFSRs
Authors
Xiao-Juan Wang
Tian Tian
Wen-Feng Qi
Publication date
20-01-2022
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00982-5

Other articles of this Issue 2/2022

Designs, Codes and Cryptography 2/2022 Go to the issue

Premium Partner