Error linear complexity measures for multisequences
type: Item
instance of: scholarly article
title: Error linear complexity measures for multisequences
zbMATH Open document ID: 1128.94007
author: Wilfried Meidl
author: Harald Niederreiter
author: Ayineedi Venkateswarlu
published in: Journal of Complexity
publication date: 2007-06-04T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 5161129
zbMATH Keywords: joint linear complexity
zbMATH Keywords: stream ciphers
zbMATH Keywords: lower bounds
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
full work available at URL: j.jco.2006.10.005
OpenAlex ID: W2081053794
cites work: Q5598073
cites work: Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
cites work: Q4432454
cites work: Q3211239
cites work: The stability theory of stream ciphers
cites work: Expected Value of the Linear Complexity of Two-Dimensional Binary Sequences
cites work: The expectation and variance of the joint linear complexity of random periodic multisequences
cites work: Q2707427
cites work: Q3946078
cites work: Counting functions and expected values for the \(k\)-error linear complexity
cites work: Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform
cites work: The expected value of the joint linear complexity of periodic multisequences
cites work: Progress in Cryptology - INDOCRYPT 2003
cites work: The Probabilistic Theory of the Joint Linear Complexity of Multisequences
cites work: Q4330638
cites work: Proof of a Conjecture on the Joint Linear Complexity Profile of Multisequences
cites work: The asymptotic behavior of the joint linear complexity profile of multisequences
cites work: Linear Complexity and Random Sequences
cites work: Extension of the Berlekamp-Massey algorithm to N dimensions
cites work: An algorithm for the k-error linear complexity of binary sequences with period 2/sup n/
cites work: Enumeration results on the joint linear complexity of multisequences
cites work: On the Lattice Basis Reduction Multisequence Synthesis Algorithm
DOI: 10.1016/J.JCO.2006.10.005
description: scientific article; zbMATH DE number 5161129