Counting functions and expected values for the \(k\)-error linear complexity (Q1609392)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting functions and expected values for the \(k\)-error linear complexity |
scientific article |
Statements
Counting functions and expected values for the \(k\)-error linear complexity (English)
0 references
15 August 2002
0 references
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.
0 references
linear complexity
0 references
\(k\)-error linear complexity
0 references
upper and lower bounds
0 references
stream ciphers
0 references