Counting functions and expected values for the k-error linear complexity

DOI10.1006/FFTA.2001.0326MaRDI QIDQ1609392zbMATH OpenOpenAlexFDO

Authors Wilfried Meidl, Harald Niederreiter

Publication date 15 August 2002

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/ffta.2001.0326

zbMATH Keywords

\(k\)-error linear complexitylinear complexitystream ciphersupper and lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Review text

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.

Recommendations

• On the expected value of the linear complexity and the k-error linear complexity of periodic sequences
• Counting Functions for the k-Error Linear Complexity of 2 n -Periodic Binary Sequences
• Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform
• A relationship between linear complexity and k-error linear complexity
• Error linear complexity measures for multisequences

Cites work

• An algorithm for the k-error linear complexity of binary sequences with period 2/sup n/
• Analysis and design of stream ciphers
• Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• scientific article; zbMATH DE number 54007 (Why is no real title available?)
• scientific article; zbMATH DE number 177032 (Why is no real title available?)
• scientific article; zbMATH DE number 1740050 (Why is no real title available?)
• scientific article; zbMATH DE number 1740058 (Why is no real title available?)
• scientific article; zbMATH DE number 1868122 (Why is no real title available?)
• Shift-register synthesis and BCH decoding
• The stability theory of stream ciphers

Cited in

(14)

• Joint linear complexity of multisequences consisting of linear recurring sequences
• Lower bounds on error complexity measures for periodic LFSR and FCSR sequences
• Characterization of \(2^{n}\)-periodic binary sequences with fixed 2-error or 3-error linear complexity
• Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform
• Counting functions and expected values for the lattice profile at \(n\)
• The expectation and variance of the joint linear complexity of random periodic multisequences
• Expected π-Adic Security Measures of Sequences
• scientific article; zbMATH DE number 5651473 (Why is no real title available?)
• scientific article; zbMATH DE number 1740050 (Why is no real title available?)
• On the expected value of the linear complexity and the k-error linear complexity of periodic sequences
• On the k-Operation Linear Complexity of Periodic Sequences
• Asymptotic analysis on the normalized k-error linear complexity of binary sequences
• An algorithm for computing the error sequence of \(p^{n}\)-periodic binary sequences
• Error linear complexity measures for multisequences

This page was built for publication: Counting functions and expected values for the \(k\)-error linear complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1609392)