Expansion complexity and linear complexity of sequences over finite fields

DOI10.1007/S12095-016-0189-2MaRDI QIDQ517722zbMATH OpenOpenAlexFDO

Authors László Mérai, Harald Niederreiter, Arne Winterhof

Publication date 27 March 2017

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06482

zbMATH Keywords

binomial coefficientscryptographyexpansion complexityfinite fieldslinear complexitypseudorandom sequences

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Abstract: The linear complexity is a measure for the unpredictability of a sequence over a finite field and thus for its suitability in cryptography. In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. We study the relationship between linear complexity and expansion complexity. In particular, we show that for purely periodic sequences both figures of merit provide essentially the same quality test for a sufficiently long part of the sequence. However, if we study shorter parts of the period or nonperiodic sequences, then we can show, roughly speaking, that the expansion complexity provides a stronger test. We demonstrate this by analyzing a sequence of binomial coefficients modulo $p$. Finally, we establish a probabilistic result on the behavior of the expansion complexity of random sequences over a finite field.

Recommendations

• Linear complexity and expansion complexity of some number theoretic sequences
• On the use of expansion series for stream ciphers
• Algebraic dependence in generating functions and expansion complexity
• The Probabilistic Theory of Linear Complexity
• Linear Complexity and Random Sequences

Cites work

• Algebraic coding theory
• Analysis and design of stream ciphers
• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 3176450 (Why is no real title available?)
• scientific article; zbMATH DE number 53676 (Why is no real title available?)
• scientific article; zbMATH DE number 204179 (Why is no real title available?)
• scientific article; zbMATH DE number 1866875 (Why is no real title available?)
• On the joint linear complexity profile of explicit inversive multisequences
• On the linear complexity profile of explicit nonlinear pseudorandom numbers.
• On the use of expansion series for stream ciphers
• Permutation polynomials, de Bruijn sequences, and linear complexity
• Shift-register synthesis and BCH decoding

Cited in

(13)

• On the \(N\)th linear complexity of automatic sequences
• Hamming correlation of higher order
• Perfect linear complexity profile and apwenian sequences
• Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
• Pseudorandom sequences derived from automatic sequences
• Algebraic dependence in generating functions and expansion complexity
• On the \(N\)th maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
• Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
• Sequences with almost perfect linear complexity profiles and curves over finite fields
• SOME METHODS TO DESIGN INTERLEAVED SEQUENCES OVER
• Linear complexity and expansion complexity of some number theoretic sequences
• Complexity of automatic sequences
• On the Nth 2-adic complexity of binary sequences identified with algebraic 2-adic integers

This page was built for publication: Expansion complexity and linear complexity of sequences over finite fields

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