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.  Google Scholar

[2]

T. EtzionN. KalouptsidisN. KolokotronisK. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Y. K. HanJ. 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.  Google Scholar

[6]

K. KurosawaF. SatoT. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986. doi: 10.1007/978-3-642-82865-2.  Google Scholar

[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.  Google Scholar

[13]

S. M. WeiG. 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.  Google Scholar

[14]

G. Z. XiaoS. M. WeiK. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

J. Q. ZhouW. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

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.  Google Scholar

[2]

T. EtzionN. KalouptsidisN. KolokotronisK. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Y. K. HanJ. 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.  Google Scholar

[6]

K. KurosawaF. SatoT. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986. doi: 10.1007/978-3-642-82865-2.  Google Scholar

[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.  Google Scholar

[13]

S. M. WeiG. 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.  Google Scholar

[14]

G. Z. XiaoS. M. WeiK. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

J. Q. ZhouW. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[1]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[2]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

[3]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[4]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[5]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[6]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[7]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[8]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[9]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[10]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[11]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004

[12]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[13]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[14]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[15]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[16]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[17]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267

[18]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

 Impact Factor: 

Metrics

  • PDF downloads (71)
  • HTML views (270)
  • Cited by (0)

[Back to Top]