k-Error linear complexity for multidimensional arrays.

In this paper, we focus on linear complexity measures of multidimensional sequences over finite fields, generalizing the one-dimensional case and including that of multidimensional arrays (identified with multidimensional periodic sequence) as a particular instance. A cryptographically strong sequence or array should not only have a high linear complexity, it should also not be possible to decrease significantly the linear complexity by changing a few terms. This leads to the concept of the $k$-error linear complexity. We make computations for some typical families of multidimensional arrays to confirm that they have a large $k$-error linear complexity for small $k$. Particularly, we give lower and upper bounds on the expected values of the linear complexity and $k$-error linear complexity of multidimensional arrays.