Counting Functions and Expected Values for the k-Error Linear Complexity

AbstractIn cryptology, complexity measures for sequences of elements of a finite field, such as the linear complexity, play an important role. Cryptographically strong sequences or finite strings must not only have a large linear complexity, but also the change of a few terms must not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity Ln,k(S) of a string S with terms in a finite field Fq and length n. In this article, bounds for the number of strings S of length n with k-error linear complexity Ln,k(S)=c or Ln,k(S)≤c for a given c are established. Under certain conditions on n, k, and c, exact formulas are also determined. On the basis of these results we derive bounds for the expected value of Ln,k(S) for random strings S of length n