Abstract
In this paper we first refine Mykkeltveit et al.’s technique for producing de Bruijn sequences through compositions. We then conduct an analysis on an approximation of the feedback functions that generate de Bruijn sequences. The cycle structures of the approximated feedback functions and the linear complexity of a sequence produced by an approximated feedback function are determined. Furthermore, we present a compact representation of an (n + 16)-stage nonlinear feedback shift register (NLFSR) and a few examples of de Bruijn sequences of period 2n, 35 ≤ n ≤ 40, which are generated by the recursively constructed NLFSR together with the evaluation of their implementation.
Chapter PDF
Similar content being viewed by others
Keywords
References
Chan, A.H., Games, R.A.: On the Quadratic Spans of de Bruijn Sequences. IEEE Transactions on Information Theory 36(4), 822–829 (1990)
Chan, A.H., Games, R.A., Key, E.L.: On the Complexities of de Bruijn Sequences. Journal of Combinatorial Theory, Series A 33(3), 233–246 (1982)
de Bruijn, N.G.: A Combinatorial Problem. Proc. Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758–764 (1946)
The eStream Project, http://www.ecrypt.eu.org/stream/
Etzion, T., Lempel, A.: Construction of de Bruijn Sequences of Minimal Complexity. IEEE Transactions on Information Theory 30(5), 705–709 (1984)
Fredricksen, H.: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms. SIAM Review 24(2), 195–221 (1982)
Fredricksen, H.: A Class of Nonlinear de Bruijn Cycles. Journal of Combinatorial Theory, Series A 19(2), 192–199 (1975)
Golomb, S.W.: On the Classification of Balanced Binary Sequences of Period 2n − 1. IEEE Transformation on Information Theory 26(6), 730–732 (1980)
Golomb, S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1981)
Golomb, S.W., Gong, G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, New York (2004)
Gong, G., Youssef, A.: Cryptographic Properties of the Welch-Gong Transformation Sequence Generators. IEEE Transactions on Information Theory 48(11), 2837–2846 (2002)
Gong, G.: Randomness and Representation of Span n Sequences. In: Golomb, S.W., Gong, G., Helleseth, T., Song, H.-Y. (eds.) SSC 2007. LNCS, vol. 4893, pp. 192–203. Springer, Heidelberg (2007)
Good, I.J.: Normal Recurring Decimals. Journal of London Math. Soc. 21(3) (1946)
Green, D.H., Dimond, K.R.: Nonlinear Product-Feedback Shift Registers. Proceedings of the Institution of Electrical Engineers 117(4), 681–686 (1970)
Green, D.H., Dimond, K.R.: Some Polynomial Compositions of Nonlinear Feedback Shift Registers and their Sequence-Domain Consequences. Proceedings of the Institution of Electrical Engineers 117(9), 1750–1756 (1970)
Jansen, C.J.A., Franx, W.G., Boekee, D.E.: An Efficient Algorithm for the Generation of de Bruijn Cycles. IEEE Transactions on Information Theory 37(5), 1475–1478 (1991)
Kjeldsen, K.: On the Cycle Structure of a Set of Nonlinear Shift Registers with Symmetric Feedback Functions. Journal Combinatorial Theory Series A 20, 154–169 (1976)
Lempel, A.: On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers. IEEE Transactions on Computers C-19(12), 1204–1209 (1970)
Mandal, K., Gong, G.: Probabilistic Generation of Good Span n Sequences from Nonlinear Feedback Shift Registers. CACR Technical Report (2012)
Mayhew, G.L., Golomb, S.W.: Characterizations of Generators for Modified de Bruijn Sequences. Advanced Applied Mathematics 13(4), 454–461 (1992)
Mykkeltveit, J., Siu, M.-K., Tong, P.: On the Cycle Structure of Some Nonlinear Shift Register Sequences. Information and Control 43(2), 202–215 (1979)
Rachwalik, T., Szmidt, J., Wicik, R., Zablocki, J.: Generation of Nonlinear Feedback Shift Registers with Special-Purpose Hardware. Report 2012/314, Cryptology ePrint Archive (2012), http://eprint.iacr.org/
http://www.ecrypt.eu.org/stream/ciphers/achterbahn/achterbahn.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mandal, K., Gong, G. (2013). Cryptographically Strong de Bruijn Sequences with Large Periods. In: Knudsen, L.R., Wu, H. (eds) Selected Areas in Cryptography. SAC 2012. Lecture Notes in Computer Science, vol 7707. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35999-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-35999-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35998-9
Online ISBN: 978-3-642-35999-6
eBook Packages: Computer ScienceComputer Science (R0)