Error linear complexity measures for multisequences

DOI10.1016/J.JCO.2006.10.005MaRDI QIDQ883329zbMATH OpenOpenAlexFDO

Authors Wilfried Meidl, Harald Niederreiter, Ayineedi Venkateswarlu

Publication date 4 June 2007

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2006.10.005

zbMATH Keywords

joint linear complexitylower boundsstream ciphers

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

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.

Recommendations

• Periodic multisequences with large error linear complexity
• Progress in Cryptology - INDOCRYPT 2003
• Improved results on periodic multisequences with large error linear complexity
• Joint linear complexity of periodic multi-sequences
• Periodic sequences with maximal linear complexity and large \(k\)-error linear complexity

Cites work

• An algorithm for the k-error linear complexity of binary sequences with period 2/sup n/
• Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
• Counting functions and expected values for the \(k\)-error linear complexity
• Enumeration results on the joint linear complexity of multisequences
• Expected Value of the Linear Complexity of Two-Dimensional Binary Sequences
• Extension of the Berlekamp-Massey algorithm to N dimensions
• scientific article; zbMATH DE number 1583787 (Why is no real title available?)
• scientific article; zbMATH DE number 4191553 (Why is no real title available?)
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• scientific article; zbMATH DE number 1740050 (Why is no real title available?)
• scientific article; zbMATH DE number 1996484 (Why is no real title available?)
• scientific article; zbMATH DE number 3318360 (Why is no real title available?)
• Linear Complexity and Random Sequences
• Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform
• On the Lattice Basis Reduction Multisequence Synthesis Algorithm
• Progress in Cryptology - INDOCRYPT 2003
• Proof of a Conjecture on the Joint Linear Complexity Profile of Multisequences
• The asymptotic behavior of the joint linear complexity profile of multisequences
• The expectation and variance of the joint linear complexity of random periodic multisequences
• The expected value of the joint linear complexity of periodic multisequences
• The Probabilistic Theory of the Joint Linear Complexity of Multisequences
• The stability theory of stream ciphers

Cited in

(18)

• Periodic multisequences with large error linear complexity
• Joint linear complexity of multisequences consisting of linear recurring sequences
• Lower bounds on error complexity measures for periodic LFSR and FCSR sequences
• The minimal polynomial over \(\mathbb F_q\) of linear recurring sequence over \(\mathbb F_{q^m}\)
• Counting functions and expected values for the \(k\)-error linear complexity
• On the linear complexity for multidimensional sequences
• The expectation and variance of the joint linear complexity of random periodic multisequences
• On the joint 2-adic complexity of binary multisequences
• The linear complexity deviation of multisequences: formulae for finite lengths and asymptotic distributions
• Determining the k-error joint linear complexity spectrum for a binary multisequence with period p^n
• Joint linear complexity of periodic multi-sequences
• An algorithm fork-error joint linear complexity of binary multisequences
• scientific article; zbMATH DE number 5651473 (Why is no real title available?)
• The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence
• scientific article; zbMATH DE number 1740050 (Why is no real title available?)
• Multisequences with large linear and \(k\)-error linear complexity from a tower of Artin-Schreier extensions of function fields
• Progress in Cryptology - INDOCRYPT 2003
• Improved results on periodic multisequences with large error linear complexity

This page was built for publication: Error linear complexity measures for multisequences

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