The 4-error linear complexity distribution for $2^n$-periodic binary sequences

Jianqin Zhou, Jun Liu, Wanquan LiuarXiv 2013 · arXiv

Introduction

In modern cryptography, the security of stream ciphers depends heavily on the unpredictability of pseudorandom binary sequences. A standard metric for this unpredictability is linear complexity (LC), defined as the length of the shortest Linear Feedback Shift Register (LFSR) capable of generating the sequence. While a high LC is desirable, it can be misleading if the sequence is structurally fragile—meaning a small number of bit flips could drastically reduce its complexity. This vulnerability is quantified by the $k$-error linear complexity, the minimum LC achievable by altering $k$ or fewer bits within a single period.

While complete counting functions for the distribution of $k$-error LC have been established for $k=1, 2,$ and $3$, the case for $k=4$ has remained a significant mathematical challenge. This paper provides the exact mathematical distribution of the 4-error linear complexity for binary sequences with a period of $2^n$.

Methodology: Games-Chan and Combinatorial Sieving

The researchers employed a two-pronged theoretical approach to derive the counting functions:

  1. The Games-Chan Algorithm: This efficient algorithm is specifically tailored for binary sequences with periods of $2^n$. It allows for the recursive determination of linear complexity by analyzing the relationship between the first and second halves of the sequence.
  2. Combinatorial Sieving: The primary obstacle in $k$-error analysis is "double-counting." Multiple distinct error vectors (bit-flip combinations) can result in the same final sequence with a reduced LC. The authors utilized inclusion-exclusion principles and combinatorial sieving to filter these overlaps, ensuring each unique sequence is counted exactly once.
Representative sets of binary vectors used to categorize error patterns in the derivation of the 4-error linear complexity distribution.

Key Insights and Categorization

The derivation hinges on several critical observations:

  • The Parity Property: For $2^n$-periodic sequences, a maximum LC of $2^n$ occurs if and only if the sequence has an odd Hamming weight (an odd number of 1s). Since flipping exactly 4 bits (an even number) preserves the parity of the weight, the 4-error LC for sequences with an initial LC of $2^n$ remains $2^n$. Consequently, the authors focused their efforts on sequences where the initial LC is less than $2^n$.
  • Structural Breakdown: The distribution cannot be captured by a single formula. Instead, sequences are categorized into six distinct algebraic classes based on their initial LC (e.g., forms like $2^{n-2} - 2^{n-m}$). Each class requires a unique combinatorial derivation to account for how 4-bit errors interact with the sequence's internal period structure.
Additional sets of binary sequences illustrating the structural breakdown required for the sieve method.

Key Results and Empirical Validation

The central achievement of this work is Theorem 3.1, which presents a comprehensive piecewise function providing the exact number of $2^n$-periodic binary sequences for any given 4-error linear complexity $L$.

To verify these complex formulas, the authors conducted empirical tests on sequences with a period of 32 ($n=5$). Their derived formulas perfectly matched the experimental counts. For instance, out of the $2^{31}$ possible sequences with LC < 32, the formula correctly identified that exactly 567,279,616 sequences have a 4-error LC of 21, and 36,457 sequences have a 4-error LC of 0.

Conclusion

By solving the distribution for $k=4$, this paper advances the theoretical understanding of sequence predictability and provides a robust framework for analyzing higher values of $k$. The combination of the Games-Chan algorithm with meticulous combinatorial sieving offers a path forward for further characterizing the security landscape of stream ciphers.

Summary updated

BibTeX
@misc{zhou2013error,
  author = {Jianqin Zhou and Jun Liu and Wanquan Liu},
  title = {{The 4-error linear complexity distribution for $2^n$-periodic binary sequences}},
  year = {2013},
  eprint = {1310.0132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1310.0132},
}
Figure