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:
- 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.
- 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.
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.
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