×

A new upper bound on the order of affine sub-families of NFSRs. (English) Zbl 1456.94037

Summary: Nonlinear feedback shift registers (NFSRs) are widely used as building blocks in the design of stream ciphers. Let NFSR\((f)\) be an NFSR with the characteristic function \(f\) and let \(G(f)\) be the set of output sequences of NFSR\((f)\). For a given NFSR\((f)\), if there exists an affine Boolean function \(l\) such that \(G(l)\subseteq G(f)\), then \(G(l)\) is called an affine sub-family of NFSR\((f)\). In this paper, by skillfully combining previous ideas, the authors give a new upper bound on the order of affine sub-families of NFSR\((f)\). Compared with the four known bounds, the bound is better than three of them, and in some cases is also better than the rest one.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory

Software:

Grain; Quark
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hell, M.; Johansson, T.; Maximov, A., The Grain family of stream ciphers, Lecture Notes in Computer Science, 4986, 179-190 (2008)
[2] Cannère, C. D.; Preneel, B., Trivium, Lecture Notes in Computer Science, 4986, 244-266 (2008) · Zbl 1285.94054
[3] Keeloq wikipedia article, http://en.wikipedia.org/wiki/KeeLoq.
[4] Aumasson, J. P.; Henzen, L.; Meier, W., Quark: A lightweight Hash, Journal of Cryptology, 26, 2, 313-339 (2013) · Zbl 1279.94053
[5] Chan, A. H.; Games, R. A.; Key, E. L., On the complexities of de Bruijn sequences, Journal of Combinatorial Theory, 33, 233-246 (1982) · Zbl 0506.05005
[6] Games, R. A., There are no de Bruijn sequences of span n with complexity 2^n−1 + n + 1, Journal of Combinatorial Theory, Series A, 34, 2, 248-251 (1983) · Zbl 0518.05002
[7] Fredricksen, H., A survey of full length nonlinear shift register cycle algorithms, Siam Review, 24, 2, 195-221 (1982) · Zbl 0482.68033
[8] Alhakim, A.; Nouiehed, M., Stretching de Bruijn sequences, Designs, Codes and Cryptography, 85, 2, 381-394 (2017) · Zbl 1371.05159
[9] Chang, Z.; Ezerman, M. F.; Ling, S., Construction of de Bruijn sequences from product of two irreducible polynomials, Cryptography and Communications, 10, 2, 251-275 (2018) · Zbl 1412.11028
[10] Dong, J.; Pei, D., Construction for de Bruijn sequences with large stage, Designs, Codes and Cryptography, 85, 2, 343-358 (2017) · Zbl 1381.94051
[11] Li, C.; Zeng, X.; Li, C., Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials, IEEE Transactions on Information Theory, 62, 1, 610-624 (2016) · Zbl 1359.94554
[12] Li, M.; Lin, D., De Bruijn sequences, adjacency graphs, and cyclotomy, IEEE Transactions on Information Theory, 64, 4, 2941-2952 (2018) · Zbl 1392.94908
[13] Sawada, J.; Williams, A.; Wong, D., A surprisingly simple de Bruijn sequence construction, Discrete Mathematics, 339, 1, 127-131 (2016) · Zbl 1322.05013
[14] Ma, Z.; Qi, W. F.; Tian, T., On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, Journal of Complexity, 29, 2, 173-181 (2013) · Zbl 1261.94028
[15] Tian, T.; Qi, W. F., On the density of irreducible NFSRs, IEEE Transactions on Information Theory, 59, 6, 4006-4012 (2013) · Zbl 1364.94510
[16] Tian, T.; Qi, W. F., On the largest affine sub-families of a family of NFSR sequences, Designs Codes and Cryptography, 71, 1, 163-181 (2014) · Zbl 1323.94096
[17] Tian, T.; Qi, W. F., Survey on sub-families of NFSR sequences, Journal of Cryptologic Research, 1, 1, 72-82 (2014)
[18] Zhang, J. M.; Qi, W. F.; Tian, T., Further results on the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, IEEE Transactions on Information Theory, 61, 1, 645-654 (2015) · Zbl 1359.94563
[19] Ma, Z.; Qi, W. F.; Tian, T., On affine sub-families of the NFSR in Grain, Designs Codes and Cryptography, 75, 2, 199-212 (2015) · Zbl 1331.94045
[20] Zhang J M, Research on linear structures of nonlinear feedback shift register sequences, Ph.D. thesis, PLA Information Engineering University, Zhengzhou, China, 2016.
[21] Jiang, Y. P.; Lin, D. D., On affine sub-families of Grain-like structures, Designs Codes and Cryptography, 82, 3, 531-542 (2017) · Zbl 1370.94471
[22] Zhang, J. M.; Tian, T.; Qi, W. F., On the affine sub-families of quadratic NFSRs, IEEE Transactions on Information Theory, 64, 4, 2932-2940 (2018) · Zbl 1392.94912
[23] Golomb, S., Shift Register Sequences (1967), San Francisco: Holden-Day, San Francisco
[24] 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) · Zbl 0431.68059
[25] Hell M, Johansson T, Maximov A, et al., A stream cipher proposal: Grain-128, IEEE International Symposium on Information Theory, 2006, 1614-1618.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.