REVIEW PAPER
NONLINEAR FEEDBACK SHIFT REGISTERS AND JOINING OF CROSS-PAIRS STATES
1
University of Bergen
2
Wojskowy Instytut Łączności im. prof. dr. hab. Janusza Groszkowskiego
Publication date: 2014-12-05
SBN 2014;6(2): 271-284
KEYWORDS
ABSTRACT
We explain the origins of Boolean feedback functions of Nonlinear Feedback
Shift Registers (NFSR) of fixed order n generating de Bruijn binary sequences. They
all come into existence by cross joining operations starting from one maximum period
feedback shift register, e.g., a linear one which always exists for any order n. The result
obtained yields some constructions of NFSR generating maximum period 2n − 1 binary
sequences.
REFERENCES (30)
1.
S. Babbage, M. Dodd, ”The MICKEY stream ciphers”, in New Stream Cipher Designs: The eSTREAM Finalists. LNCS vol. 4986, pp. 191–209. Springer-Verlag, 2008.
3.
A. H. Chan, R. A. Games, J. J. Rushanan, On the quadratic m-sequences, Proceedings of Fast Software Encryption, LNCS vol. 809, pp. 166–173. Springer-Verlag, 1994.
4.
C. Canniere, B. Preneel, ”Trivium”, in New Stream Cipher Designs: The eSTREAM Finalists, LNCS vol. 4986, pp. 244–266. Springer-Verlag, 2008.
5.
P. Dąbrowski, G. Labuzek, T. Rachwalik, J. Szmidt, Searching for nonlinear feedback shift registers with parallel computing, Inform. Proc. Letters, 114(2014), pp. 268–272.
6.
E. Dubrova, A scalable method for constructing Galois NLFSRs with period 2 n − 1 using cross-join pairs, IEEE Trans. on Inform. Theory, 59(1), 2013, pp. 703–709.
7.
J. C. Fletcher, M. Perlman, Nonlinear nonsingular feedback shift registers, United States Patent 3911330, 1975.
8.
C. Flye Sainte-Marie, Solution to question nr. 48. L’Interm´ediaire des Math´ematiciens, 1(1894). pp. 107–110.
9.
H. Fredricksen, A class of nonlinear de Bruijn cycles, J. of Combinatorial Theory (A), 19(1975), pp. 192–199.
10.
H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24(2), 1982, pp. 195–221.
11.
B. M. Gammel, R. Goetffert, O. Kniffler, Achterbahn 128/80, The eSTREAM project, www.ecrypt.eu.org/stream/, www.matpack.de/achterbahn.
12.
S. W. Golomb, Shift register sequences. San Francisco, Holden-Day, 1967, revised edition, Laguna Hills, CA, Aegean Park Press, 1982.
13.
S. W. Golomb, G. Gong, Signal Design for Good Correlation. For Wireless Communication, Cryptography, and Radar, Cambridge University Press, 2005.
14.
E. R. Hauge, T. Helleseth, De Bruijn sequences, irreducible codes and cyclotomy, Discrete Math., 159(1996), pp. 143–154.
15.
M. Hell, T. Johansson, A. Maximov, W. Meier, ”The Grain Family of Stream Ciphers”, in New Stream Cipher Designs: The eSTREAM Finalists. LNCS vol. 4986, pp. 179–190. Springer-Verlag, 2008.
16.
T. Helleseth, T. Kløve, The number of cross-join pairs in maximum length linear sequences, IEEE Trans. on Inform. Theory, 31(1991), pp. 1731–1733.
17.
F. Hemmati, A large class of nonlinear shift register sequences, IEEE Trans. on Inform. Theory, vol. 28, pp. 355-359, 1982.
18.
C. J. A. Jansen, Investigations on nonlinear streamcipher systems: Construction and evaluation methods, Ph.D. Thesis, Technical University of Delft, 1989.
19.
R. Lidl, H. Niederreiter, Introduction to Finite Fields and their Applications (Revised Edition), Cambridge University Press, Cambridge, 1994.
20.
K. B. Magleby, The synthesis of nonlinear feedback shift registers, Technical Report no. 6207-1. Stanford Electronics Laboratories, 1963.
21.
K. Mandal, G. Gong, Cryptographically strong de Bruijn sequences with large periods. Selected Areas in Cryptography. L. R. Knudsen, K. Wu (Eds.). LNCS, vol. 7707, pp. 104–118. Springer-Verlag, 2012.
22.
G. L. Mayhew, S. W. Golomb, Linear spans of modified de Bruijn sequences, IEEE Trans. Inform. Theory, 36(5), 1990, pp. 1166–1167.
23.
J. Mykkeltveit Generating and counting the double adjacencies in a pure cyclic shift register, Trans. on Computers, C-24, 1975, pp. 299–304.
24.
J. Mykkeltveit, M-K. Siu, P. Tong, On the cyclic structure of some nonlinear shift register sequences, Inform. and Control, 43(1979), pp. 202–215.
25.
J. Mykkeltveit, J. Szmidt On cross joining de Bruijn sequences, Contemporary Mathematics, vol. 632, pp. 333–344, American Mathematical Society, 2015.
26.
T. Rachwalik, J. Szmidt, R. Wicik, J. Zab locki, Generation of nonlinear feedback shift registers with special purpose hardware, Military Communications and Information Systems Conference, MCC 2012, IEEE Xplore Digital Library, 2012, pp. 151–154.
27.
R. Wicik, T. Rachwalik, Modified alternating step generators, Military Communications and Information Systems Conference, MCC 2013. IEEE Xplore Digital Library, 2013, pp. 203-215.
28.
M. S. Turan, On the nonlinearity of maximum-length NFSR feedbacks, Cryptography and Communications, 4(3-4), 2012, pp. 233-243.
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
