The K-error Nonlinear Complexity Of Finite Length Binary Sequences With Large Nonlinear Complexity

The security of stream ciphers depends on the characteristics of the key stream.As the key in stream ciphers,random sequences must have good cryptographic properties,such as randomness,balance,low correlation and so on.The nonlinear complexity of sequences is an important parameter to measure the randomness of sequences.In prac-tical applications,we hope that the nonlinear complexity of sequences do not decrease greatly after a few items are changed.To assess the stability of nonlinear complexity,some scholars defined the k-error nonlinear complexity based on the definition of the k-error linear complexity.Through the study of k-error nonlinear complexity,we can better judge the applicability of sequence in practice.In this paper,we first construct binary sequences with length n and of nonlinear complexity c where(?)n-1/2(?)<c<n-1.Then,we proved that their k-error nonlinear complexity satisfies the upper bound.Finally,the results show that these finite-length binary sequences with great nonlinear complexity are also insecure in cryptographic applications.