Error linear complexity measures for multisequences (Q883329)

It is known that good keystream sequences for stream ciphers are required to have a large linear complexity. An attention is given also to the \(k\)-error linear complexity notion for these sequences. Recent developments in word-based stream ciphers require the study of the complexity of multisequences, i.e. parallel streams of finitely many sequences. For such a scenario the notion of joint linear complexity of multisequences has been already investigated. Natural continuation in this direction is a theory of \(k\)-error linear complexity for multisequences, given in the paper. First, various options for error linear complexity measures for multisequences are introduced. Then formulas for counting functions for the error linear complexity measures for multisequences and bounds for the expected values in the case of finite multisequences are given. Several results for the class of periodic multisequences with prime period follow and the paper ends with a short conclusions section.