A New Type of NLFSR Functions with Maximum Periods

  • Ibraheem Mohammed Al-Hejri King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia
  • Talal Mousa Al-Kharobi King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia
Keywords: NLFSR, Stream Ciphers, Pseudorandom, Feedback Functions, Optimal Period.


Nonlinear feedback shift registers (NLFSRs) have received much attention in designing various cryptographic algorithms such as stream ciphers and light weight block ciphers in the provision of high-level security in communication systems. The main purpose of NLFSRs is to generate pseudorandom sequences of bits. NLFSRs are known to be more secure than their linear counterparts. However, there is no mathematical foundation on how to construct an NLFSR with optimal period. In this paper, we propose a new type of NLFSR function of degree 2 with optimal periods. Using our construction method, we propose 639 new functions of this type with optimal periods.


(1) Zhou, Liang, and Shantanu Chakrabartty. "Secure dynamic authentication of passive assets and passive iots using self-powered timers." 2017 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2017.

(2) Zeng, Kencheng, et al. "Pseudorandom bit generators in stream-cipher cryptography." Computer 24.2 (1991): 8-17.

(3) Ahmad, A. "Achievement of higher testability goals through the modification of shift registers in LFSR-based testing." International journal of electronics 82.3 (1997): 249-260.

(4) Mrugalski, Grzegorz, Janusz Rajski, and Jerzy Tyszer. "Ring generators-new devices for embedded test applications." IEEE Transactions on Computer-Aided Design of Integrated Circuits and

Systems 23.9 (2004): 1306-1320.

(5) Zhang, Jia-Min, et al. "Further Results on the Decomposition of an NFSR Into the Cascade Connection of an NFSR Into an LFSR." IEEE Trans. Information Theory 61.1 (2015): 645-654.

(6) Dubrova, Elena, and Martin Hell. "Espresso: A stream cipher for 5G wireless communication systems." Cryptography and Communications 9.2 (2017): 273-289.

(7) Chabloz, Jean-Michel, Shohreh Sharif Mansouri, and Elena Dubrova. "An algorithm for constructing a fastest Galois NLFSR generating a given sequence." International Conference on Sequences and Their Applications. Springer, Berlin, Heidelberg, 2010.

(8) Dubrova, Elena. "An equivalence-preserving transformation of shift registers." International Conference on Sequences and Their Applications. Springer, Cham, 2014.

(9) Lidl, Rudolf, and Harald Niederreiter. Introduction to finite fields and their applications. Cambridge university press, 1994.

(10) Kaashoek, M. Frans, and David R. Karger. "Koorde: A simple degree-

optimal distributed hash table." International Workshop on Peer-to-Peer Systems. Springer, Berlin, Heidelberg, 2003.

(11) Mayhew, Gregory L., and Solomon W. Golomb. "Linear spans of modified de Bruijn sequences." IEEE transactions on information theory 36.5 (1990): 1166-1167.

(12) Champness, Neil R. "Coordination polymers: from metal–organic frameworks to spheres." Angewandte Chemie International Edition 48.13 (2009): 2274-2275.

(13) Dubrova, Elena. "Generation of full cycles by a composition of NLFSRs." Designs, codes and cryptography 73.2 (2014): 469-486.

(14) Dubrova, Elena. "A list of maximum-period NLFSRs." (2012).

(15) Janicka-Lipska, Izabela, and Janusz Stokłosa. "Boolean feedback functions for full-length nonlinear shift registers." Journal of Telecommunications and Information Technology (2004): 28-30.

(16) Almuhammadi, Sultan, et al. "NLFSR Functions with Optimal Periods." International Conference on Computational Science and Its Applications. Springer, Cham, 2018.

(17) Rachwalik, Tomasz, et al. "Generation of Nonlinear Feedback Shift Registers with special-purpose hardware." Communications and Information Systems Conference (MCC), 2012 Military. IEEE, 2012.

(18) Mandal, Kalikinkar, and Guang Gong. Cryptographic D-morphic analysis and fast implementations of composited de Bruijn sequences. Technical Report CACR 2012-27, University of Waterloo, 2012.

(19) Günther, Christoph G. "Alternating step generators controlled by de Bruijn sequences." Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1987.

(20) Ghebleh, Mohammad, Ali Kanso, and Hassan Noura. "An image encryption scheme based on irregularly decimated chaotic maps." Signal Processing: Image Communication 29.5 (2014): 618-627.

(21) Poluyanenko, Nikolay. "Development of the search method for non-linear shift registers using hardware, implemented on field programmable gate arrays." EUREKA: Physics and Engineering 1 (2017): 53-60.