Constructing New NLFSR Functions with Optimal Periods

Constructing New NLFSR Functions with Optimal Periods

Ibraheem Al-Hejri (King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia) and Sultan Almuhammadi (King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia)
DOI: 10.4018/IJITN.2020040106

Abstract

Pseudorandom bit generators are essential components in many security applications. The security of the system relies on the security of its components. Feedback shift registers are commonly used to generate pseudorandom bits. Nonlinear feedback shift registers (NLFSRs) are known to be more secure than the linear ones. However, there is no mathematical foundation on how to construct NLFSR feedback functions with optimal periods. This article considers a new type of NLFSR capable of constructing feedback functions of degree 3 with optimal periods. Using their construction method, the authors propose new functions of this type.
Article Preview
Top

2. Preliminaries

An FSR contains n binary storage cells, also called stages as illustrated in Figure 1. Each cell is capable of holding a single bit, and each stage i ∈ {0, 1, …, n – 1} is associated with a state variable xi that shows the current value of the stage. The feedback function fi : {0, 1}n → {0, 1} computes the updated value of the cell n – 1 . The state of an FSR can be presented as a vector of values of its state variables (x0,x1xn– 1). The period of an FSR is defined as the length of longest repeated output sequence can be obtained. The period is called optimal if its length is 2n – 1. The output sequence can be yielded by extracting the bit one by one. The value of the stage 0 determines the output of an FSR, while the input of an FSR is determined by the value of the stage n – 1. Including the output bit is essential in order to maximize the function period. Therefore, the FSR takes the following form:

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 13: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 12: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing