Counting functions and expected values for the \(k\)-error linear complexity (Q1609392)

The notion of linear complexity is quite well known in cryptology, especially in relation to stream ciphers. For example, so called cryptographically strong sequences naturally must have a large linear complexity. Further refinement that requires that a change of a few terms must not cause a significant decrease of the linear complexity leads to the concept of the \(k\)-error linear complexity. The paper addresses some fundamental issues concerning this concept. Particularly, bounds for the number of strings of length \(n\) with a given \(k\)-error linear complexity are established. On the basis of these results, bounds for the expected value of \(k\)-error linear complexity for a random string of a given length are then derived.