# American Institute of Mathematical Sciences

November  2019, 2(4): 279-297. doi: 10.3934/mfc.2019018

## On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory

 1 School of Computer Science, Anhui Univ. of Technology, Ma'anshan, 243002, China 2 Department of Computing, Curtin University, Perth, WA 6102, Australia 3 School of Computer Science, Anhui Univ. of Technology, Ma'anshan, 243002, China 4 Dept of Mathematics & Statistics, Curtin University, Perth, WA 6102, Australia

Published  December 2019

The linear complexity and the $k$-error linear complexity of a binary sequence are important security measures for the security of the key stream. By studying binary sequences with the minimum Hamming weight, a new tool, named as the hypercube theory, is developed for $p^n$-periodic binary sequences. In fact, the hypercube theory is based on a typical sequence decomposition and it is a very important tool for investigating the critical error linear complexity spectrum proposed by Etzion et al. To demonstrate the importance of hypercube theory, we first give a standard hypercube decomposition based on a well-known algorithm for computing linear complexity and show that the linear complexity of the first hypercube in the decomposition is equal to the linear complexity of the original sequence. Second, based on such decomposition, we give a complete characterization for the first decrease of the linear complexity for a $p^n$-periodic binary sequence. This significantly improves the current existing results in literature. As to the importance of the hypercube, we finally derive a counting formula for the $m$-hypercubes with the same linear complexity.

Citation: Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
##### References:
 [1] C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers[M], Lecture Notes in Computer Science, 561. Springer-Verlag, Berlin, 1991. doi: 10.1007/3-540-54973-0. [2] T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 4681-4686.  doi: 10.1109/TIT.2009.2027495. [3] R. A. Games and A. H. Chan, A fast algorithm for determining the complexity of a binary sequence with period $2^n$, IEEE Trans on Information Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619. [4] F. Fu, H. Niederreiter and M. Su, The characterization of $2^n$-periodic binary sequences with fixed 1-error linear complexity, In: Gong G., Helleseth T., Song H.-Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88–103. doi: 10.1007/11863854_8. [5] Y. K. Han, J. H. Chung and K. Yang, On the $k$-error linear complexity of $p^m$-periodic binary sequences, IEEE Transactions on Information Theory, 53 (2007), 2297-2304.  doi: 10.1109/TIT.2007.896863. [6] K. Kurosawa, F. Sato, T. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694-698.  doi: 10.1109/18.825845. [7] A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273-280.  doi: 10.1109/TIT.2002.806136. [8] W. Meidl and H. Niederreiter, Linear complexity k-error linear complexity, and the discrete Fourier transform, J. Complexity, 18 (2002), 87-103.  doi: 10.1006/jcom.2001.0621. [9] W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109-122.  doi: 10.1023/B:DESI.0000035466.28660.e9. [10] W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 1151-1155.  doi: 10.1109/TIT.2004.842709. [11] R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986. doi: 10.1007/978-3-642-82865-2. [12] M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455. [13] S. M. Wei, G. Z. Xiao and Z. Chen, A fast algorithm for determining the minimal polynomial of a sequence with period $2p^n$ over $GF(q)$, IEEE Trans on Information Theory, 48 (2002), 2754-2758.  doi: 10.1109/TIT.2002.802609. [14] G. Z. Xiao, S. M. Wei, K. Y. Lam and K. Imamura, A fast algorithm for determining the linear complexity of a sequence with period $p^n$ over $GF(q)$, IEEE Trans on Information Theory, 46 (2000), 2203-2206.  doi: 10.1109/18.868492. [15] J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Cryptogr., 58 (2011), 279-296.  doi: 10.1007/s10623-010-9379-7. [16] J. Q. Zhou, A counterexample concerning the 3-error linear complexity of $2^n$-periodic binary sequences, Des. Codes Cryptogr., 64 (2012), 285-286.  doi: 10.1007/s10623-011-9576-z. [17] J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 55-75.  doi: 10.1007/s10623-013-9805-8. [18] J. Q. Zhou, W. Q. Liu and X. F. Wang, Complete characterization of the first descent point distribution for the $k$-error linear complexity of $2^n$-periodic binary sequences, Adv. in Math. of Comm., 11 (2017), 429-444.  doi: 10.3934/amc.2017036. [19] J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable $k$-error linear complexity for periodic sequences, Information Security and Cryptology, 70–85, Lecture Notes in Comput. Sci., 8567, Springer, Heidelberg, 2014. doi: 10.1007/978-3-319-12087-4_5. [20] F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, Journal of Electronics (China), 24 (2007), 390-395.

show all references

##### References:
 [1] C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers[M], Lecture Notes in Computer Science, 561. Springer-Verlag, Berlin, 1991. doi: 10.1007/3-540-54973-0. [2] T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 4681-4686.  doi: 10.1109/TIT.2009.2027495. [3] R. A. Games and A. H. Chan, A fast algorithm for determining the complexity of a binary sequence with period $2^n$, IEEE Trans on Information Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619. [4] F. Fu, H. Niederreiter and M. Su, The characterization of $2^n$-periodic binary sequences with fixed 1-error linear complexity, In: Gong G., Helleseth T., Song H.-Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88–103. doi: 10.1007/11863854_8. [5] Y. K. Han, J. H. Chung and K. Yang, On the $k$-error linear complexity of $p^m$-periodic binary sequences, IEEE Transactions on Information Theory, 53 (2007), 2297-2304.  doi: 10.1109/TIT.2007.896863. [6] K. Kurosawa, F. Sato, T. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694-698.  doi: 10.1109/18.825845. [7] A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273-280.  doi: 10.1109/TIT.2002.806136. [8] W. Meidl and H. Niederreiter, Linear complexity k-error linear complexity, and the discrete Fourier transform, J. Complexity, 18 (2002), 87-103.  doi: 10.1006/jcom.2001.0621. [9] W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109-122.  doi: 10.1023/B:DESI.0000035466.28660.e9. [10] W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 1151-1155.  doi: 10.1109/TIT.2004.842709. [11] R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986. doi: 10.1007/978-3-642-82865-2. [12] M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455. [13] S. M. Wei, G. Z. Xiao and Z. Chen, A fast algorithm for determining the minimal polynomial of a sequence with period $2p^n$ over $GF(q)$, IEEE Trans on Information Theory, 48 (2002), 2754-2758.  doi: 10.1109/TIT.2002.802609. [14] G. Z. Xiao, S. M. Wei, K. Y. Lam and K. Imamura, A fast algorithm for determining the linear complexity of a sequence with period $p^n$ over $GF(q)$, IEEE Trans on Information Theory, 46 (2000), 2203-2206.  doi: 10.1109/18.868492. [15] J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Cryptogr., 58 (2011), 279-296.  doi: 10.1007/s10623-010-9379-7. [16] J. Q. Zhou, A counterexample concerning the 3-error linear complexity of $2^n$-periodic binary sequences, Des. Codes Cryptogr., 64 (2012), 285-286.  doi: 10.1007/s10623-011-9576-z. [17] J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 55-75.  doi: 10.1007/s10623-013-9805-8. [18] J. Q. Zhou, W. Q. Liu and X. F. Wang, Complete characterization of the first descent point distribution for the $k$-error linear complexity of $2^n$-periodic binary sequences, Adv. in Math. of Comm., 11 (2017), 429-444.  doi: 10.3934/amc.2017036. [19] J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable $k$-error linear complexity for periodic sequences, Information Security and Cryptology, 70–85, Lecture Notes in Comput. Sci., 8567, Springer, Heidelberg, 2014. doi: 10.1007/978-3-319-12087-4_5. [20] F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, Journal of Electronics (China), 24 (2007), 390-395.
 [1] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 [2] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 [3] Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047 [4] Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $4p^n$. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019 [5] Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369 [6] Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297 [7] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [8] Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003 [9] Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334 [10] Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477 [11] Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299 [12] Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 [13] Steffen Klassert, Daniel Lenz, Peter Stollmann. Delone measures of finite local complexity and applications to spectral theory of one-dimensional continuum models of quasicrystals. Discrete and Continuous Dynamical Systems, 2011, 29 (4) : 1553-1571. doi: 10.3934/dcds.2011.29.1553 [14] Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385 [15] Roland Zweimüller. Asymptotic orbit complexity of infinite measure preserving transformations. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 353-366. doi: 10.3934/dcds.2006.15.353 [16] Erik M. Bollt, Joseph D. Skufca, Stephen J . McGregor. Control entropy: A complexity measure for nonstationary signals. Mathematical Biosciences & Engineering, 2009, 6 (1) : 1-25. doi: 10.3934/mbe.2009.6.1 [17] Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044 [18] Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015 [19] Valentin Afraimovich, Lev Glebsky. Measures related to $(\epsilon,n)$-complexity functions. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 23-34. doi: 10.3934/dcds.2008.22.23 [20] Enrico Capobianco. Born to be big: Data, graphs, and their entangled complexity. Big Data & Information Analytics, 2016, 1 (2&3) : 163-169. doi: 10.3934/bdia.2016002

Impact Factor: