🔢 mathematics

Symmetric measures of pseudorandomness for binary sequences

This paper compares ordinary and symmetric variants of pseudorandomness measures for binary sequences, demonstrating that symmetrization can significantly reduce complexity values for both periodic and aperiodic sequences, with expected values differing by a term of order $N$ .

Original authors: Yixin Ren, Arne Winterhof

Published 2026-03-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yixin Ren, Arne Winterhof

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a security guard at a high-tech bank. Your job is to inspect the "keys" (binary sequences of 0s and 1s) used to unlock the vaults. Some keys look random and chaotic, which is good. Others might have hidden patterns that make them easy to guess, which is bad.

In the world of cryptography, mathematicians use two main rulers to measure how "random" and secure a key is:

Linear Complexity: How hard is it to build a machine that can predict the next number in the sequence?
2-adic Complexity: A more advanced version of the same idea, looking at the sequence through a different mathematical lens (related to how numbers behave in base 2).

For a long time, security experts only looked at the key as it was written: 010110.... But this paper asks a clever question: "What if we look at the key backwards?"

The "Mirror" Test

The authors introduce a concept called Symmetric Measures. Instead of just measuring the complexity of the key, they measure the complexity of the key and its mirror image (the key written backwards), then take the lower of the two scores.

Think of it like a security check where you have to pass two tests:

Test A: Can you break the code as it is?
Test B: Can you break the code if you read it in a mirror?

Your final security score is the easiest of the two. If the mirror version is weak, the whole key is considered weak, even if the original looked strong.

The Two Main Discoveries

1. The Periodic Case (The Looping Key)

Imagine a key that repeats itself forever, like a song on a loop.

The Finding: The authors found that for certain "prime number" based keys, the mirror version is significantly easier to crack than the original.
The Analogy: Imagine a secret handshake. The original handshake is complex and hard to memorize. But if you do it backwards, it turns out to be a simple, clumsy wave that anyone can copy. In this specific case, the "Symmetric" score (the easy wave) is much lower than the "Ordinary" score (the complex handshake).
The Twist: However, they also proved that for Linear Complexity (the first ruler), the original and the mirror are always equally hard to break. It's like a perfect palindrome: no matter which way you read it, the difficulty is the same.

2. The Aperiodic Case (The One-Time Key)

Now imagine a key that is used only once and never repeats. This is the most common scenario in modern encryption.

The Finding: Here, the difference is massive. The authors found families of keys where the mirror version is drastically weaker than the original.
The Analogy: Think of a long, winding maze. Walking through it forward might take hours (high complexity). But if you look at the map backwards, you realize there's a secret tunnel right at the start that lets you exit in seconds (low complexity).
The Result: When you average this out over millions of random keys, the "Symmetric" security score is significantly lower than the "Ordinary" score. The gap is so big that it's like the difference between a fortress and a cardboard box.

Why Does This Matter?

The paper concludes that symmetrization reveals hidden weaknesses.

If you design a security system based only on the "Ordinary" complexity, you might think your keys are unbreakable. But this paper shows that if an attacker decides to look at the keys in reverse (or if the system accidentally processes them backwards), those keys might collapse much faster than expected.

In simple terms:

Old View: "This key looks strong."
New View (This Paper): "Wait, if we flip it over, it's actually quite weak. We need to design keys that are strong in both directions."

The authors provide mathematical proof that ignoring the "mirror" version of a key leaves a giant hole in your security, especially for short, one-time keys. They essentially tell cryptographers: "Don't just check the front door; check the back door too, because that's where the lock might be broken."

1. Problem Statement

The paper addresses a gap in the analysis of pseudorandomness for binary sequences, specifically regarding symmetric complexity measures.

Context: In stream cipher design, the security of a sequence is often evaluated by its resistance to attacks based on Linear Feedback Shift Registers (LFSRs) and Feedback with Carry Shift Registers (FCSRs). The standard metrics are Linear Complexity ( $L$ ) and 2-adic Complexity ( $\lambda$ ).
The Issue: While standard complexity measures are well-studied, their symmetric variants (defined as the minimum complexity between a sequence $S$ and its reversal $S^{rev}$ ) have not been systematically compared to ordinary measures, particularly in the aperiodic (finite) setting.
Research Question: How do symmetric measures ( $L_{sym}, \lambda_{sym}$ ) compare to ordinary measures ( $L, \lambda$ ) in both periodic and aperiodic settings? Do they offer a significantly lower bound on complexity, potentially revealing weaknesses in sequences that appear secure under standard metrics?

2. Methodology

The authors employ a combination of number theory, combinatorics, and probabilistic analysis to compare ordinary and symmetric complexity measures.

Definitions:
- Periodic Setting: Sequences with period $T$ . Complexity is derived from the generating polynomial $S_T(x)$ and its reverse.
- Aperiodic Setting: Finite sequences $S_N$ of length $N$ .
- Symmetric Measures: Defined as $C_{sym}(S) = \min\{C(S), C(S^{rev})\}$ .
Analytical Tools:
- Number Theory: Utilization of properties of primes, orders of elements modulo $p$ ( $ord_p(2)$ ), and reversible integers (integers whose binary representation reversed is also an integer, often prime).
- Recurrence Relations: Direct proofs using the recurrence definitions of linear complexity to establish invariance under reversal in periodic cases.
- Probabilistic Bounds: Calculation of expected values ( $E$ ) over the space of all $2^N$ binary sequences. The authors derive upper and lower bounds for these expectations, often using counting arguments for sequences with low complexity.
- Explicit Constructions: Building specific families of sequences (e.g., based on non-palindromic primes) to demonstrate strict inequalities between ordinary and symmetric complexities.

3. Key Contributions and Results

A. The Periodic Case

Symmetric 2-adic Complexity:
- The authors prove that for binary periodic sequences constructed from non-palindromic primes, the symmetric 2-adic complexity can be strictly smaller than the ordinary 2-adic complexity.
- Theorem 1: By selecting a prime $p$ and its reverse $q$ (where $q$ is also a prime or integer with specific order properties), they construct a sequence where $\lambda(S) = \log_2(2^T-1)$ but $\lambda_{sym}(S) = \lambda(S) - \log_2(q)$ . This demonstrates that a sequence can have high ordinary complexity but low symmetric complexity.
Symmetric Linear Complexity:
- Proposition 1: The authors provide a direct proof that for any periodic sequence, the linear complexity is invariant under reversal ( $L(S) = L(S^{rev})$ ).
- Implication: In the periodic setting, the symmetric linear complexity is identical to the ordinary linear complexity ( $L_{sym}(S) = L(S)$ ). Thus, symmetrization offers no reduction in linear complexity for periodic sequences.

B. The Aperiodic (Finite) Case

In the finite setting, the behavior differs significantly from the periodic case.

Reduction in 2-adic and Rational Complexity:
- The authors construct explicit families of finite sequences where both the $N$ -th symmetric rational complexity ( $\Lambda_{sym}$ ) and symmetric 2-adic complexity ( $\lambda_{sym}$ ) are substantially smaller than their ordinary counterparts.
- Proposition 2: They establish that the expected value of the $N$ -th rational complexity exceeds the expected value of the symmetric rational complexity by at least a term of order $N$ (specifically $\approx 3N/8$ ).
- Theorem 2: Lower bounds are established showing that $E[\Lambda_{sym}] \ge 2^{N/2 - r(N)}$ and $E[\lambda_{sym}] \ge N/2 - \log(N)$ , confirming that while symmetric complexity is lower, it remains high for random sequences.
Reduction in Linear Complexity:
- Unlike the periodic case, the symmetric linear complexity in the aperiodic setting can be smaller than the ordinary linear complexity.
- Proposition 3: The expected value of the exponential linear complexity ( $E[2^{L_{sym}}]$ ) is shown to be smaller than the ordinary exponential linear complexity ( $E[2^L]$ ) by a term of order $3N/4$ .
- Theorem 3: Lower bounds for the expected symmetric linear complexity are derived, showing $E[L_{sym}] \ge N/2 - \log(N)$ .
Expected Value Analysis:
- The paper provides precise asymptotic formulas for the expected values of symmetric measures.
- Corollary 1 & 2: The expected symmetric rational complexity is $O(2^{N/2})$ , and the expected symmetric linear complexity is $O(N/2)$ . However, the difference between ordinary and symmetric expectations grows exponentially ( $2^{N/2}$ ) or linearly ( $N$ ), indicating that symmetrization has a visible effect on an exponential scale.

4. Significance and Implications

Security Assessment: The results highlight that relying solely on ordinary complexity measures may be insufficient for certain applications. A sequence might appear secure (high ordinary complexity) but possess a "weak" reversal with significantly lower complexity. In the aperiodic setting, this weakness is detectable via symmetric measures.
Periodic vs. Aperiodic Distinction: The paper clarifies a crucial theoretical distinction:
- Periodic: Symmetrization does not reduce linear complexity (invariant) but can reduce 2-adic complexity.
- Aperiodic: Symmetrization can reduce both linear and 2-adic complexities significantly.
Cryptographic Design: For stream ciphers using finite keystreams, designers must ensure that both the sequence and its reversal possess high complexity. The paper suggests that "symmetric complexity" should be a standard metric in the evaluation of finite binary sequences.
Theoretical Contribution: The work bridges the gap between the study of reversible primes and pseudorandomness measures, providing new lower bounds and explicit constructions that refine the understanding of complexity distributions in binary sequences.

Conclusion

Ren and Winterhof demonstrate that symmetrization is a powerful lens for analyzing pseudorandomness. While it does not alter linear complexity in periodic sequences, it reveals substantial weaknesses in both linear and 2-adic complexities for finite (aperiodic) sequences. The expected symmetric complexity is strictly lower than the ordinary complexity, with the gap growing significantly as sequence length increases, necessitating the inclusion of symmetric measures in cryptographic security evaluations.