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

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.