Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr

Wenjuan Jia, Juntao Gao, Peng ZhangJournal of Systems Engineering and Electronics 2019 · DOI

TL;DR

This paper introduces a novel class of binary generalized cyclotomic sequences with length $pqr$, where $p, q, r$ are distinct odd primes. The authors analyze their linear complexity and autocorrelation properties, demonstrating that these sequences offer high linear complexity and good autocorrelation, making them suitable for cryptographic applications.

What Problem Does This Paper Address?

In cryptography, sequences with good pseudorandom properties are crucial. Two key metrics for evaluating these properties are linear complexity and autocorrelation. High linear complexity makes a sequence difficult to predict using linear feedback shift registers (LFSRs), while good autocorrelation (values close to zero for non-zero shifts) helps distinguish a sequence from its shifted versions, which is important for synchronization and error correction. While various generalized cyclotomic sequences have been studied, there's a continuous need to develop new sequences with improved cryptographic characteristics. This paper addresses this by proposing a new class of binary generalized cyclotomic sequences of order two and length $pqr$ and thoroughly analyzing their linear complexity and autocorrelation.

Methods

The paper defines a new class of binary generalized cyclotomic sequences of order two and length $N=pqr$ based on Whiteman's generalized cyclotomy. The core of the methodology involves:

  • Defining the Sequence: The sequence $s_i$ is defined based on whether the index $i$ (modulo $N$) falls into specific sets ($C_0$ or $C_1$) derived from generalized cyclotomic classes.
  • Linear Complexity Analysis: The linear complexity is determined by calculating the number of roots of the sequence's generating polynomial $S(x)$ over the field $\mathbb{F}_{2^m}$, where $m = \text{ord}_N(2)$. This involves analyzing the structure of the sets $D_0$ and $D_1$ and using properties of finite fields and roots of unity. The minimal polynomial is derived from the greatest common divisor of $x^N-1$ and $S(x)$.
  • Autocorrelation Analysis: The autocorrelation function $AC(s_i, \tau)$ is calculated by examining the sum $\sum_{i=0}^{N-1} (-1)^{s_i + s_{i+\tau}}$. This involves partitioning the indices based on their membership in various sets ($P_1, P_2, P_3, Q_2, Q_3, R, O$) and utilizing properties of Legendre symbols and specific conditions on $p, q, r$.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation results rather than training on specific datasets.

Key Insights and Ideas

  • High Linear Complexity: The proposed sequences exhibit high linear complexity, especially when the element 2 belongs to the set $D_1$. This is a significant cryptographic advantage, as it makes the sequences resistant to the Berlekamp-Massey attack.
  • Good Autocorrelation: The autocorrelation values are shown to be close to 0 for most non-zero shifts, particularly when $r$ is a large prime. This property is crucial for applications requiring good synchronization and low sidelobes.
  • Dependence on Prime Properties: The linear complexity and autocorrelation values are shown to depend on the specific properties of the primes $p, q, r$, particularly their residues modulo 4 and the distribution of 2 within the cyclotomic classes.
  • Novel Sequence Construction: The paper introduces a new construction for generalized cyclotomic sequences, offering a different characteristic set compared to previously studied sequences.

Key Results

  • Linear Complexity: The paper provides explicit formulas for the linear complexity of the sequences, showing it's generally large and depends on whether $2 \in D_0$ or $2 \in D_1$, and the residue of $r$ modulo 4. For instance, when $r \equiv 1 \pmod 4$ and $2 \in D_0$, $LC(s_i) = pqr - \delta$, where $\delta = (p-1)(q-1) + (p-1)(r-1) + 1$.
  • Autocorrelation Values: The autocorrelation values are precisely determined for various shifts $\tau$. For instance, when $\tau \in P_1$, the autocorrelation is $AC(s_i, \tau) = qr - pq + (p-1)(r-3) + q - 4 + \frac{(p-1)(q-1)}{pqr}(1+(-1)^\tau)$. The paper highlights that these values are close to 0 or 1.
  • Simulation Results: Tables and figures (Fig. 1, Fig. 2) present simulation results that validate the theoretical findings for linear complexity and autocorrelation, showing high linear complexity and autocorrelation values close to 0 or 1.

Limitations and Future Work

  • Limitations: The analysis is primarily theoretical. While simulations are provided, a comprehensive empirical evaluation across various cryptographic scenarios is not presented. The paper focuses on binary sequences; extending to polyphase sequences could be a future direction. The exact values of autocorrelation can be complex and depend on the specific values of $p, q, r$ and $\tau$.
  • Future Work: The authors suggest that the exact values of autocorrelation can be determined using the presented methods, and that for large primes $p, q, r$, the autocorrelation values are close to 0 or 1, indicating good cryptographic potential. Further exploration of these sequences in specific cryptographic primitives (e.g., stream ciphers) would be beneficial. The paper also implicitly suggests investigating sequences with different orders or lengths.

Summary updated

BibTeX
@article{jia2019linear,
  author = {Wenjuan Jia and Juntao Gao and Peng Zhang},
  title = {{Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr}},
  journal = {Journal of Systems Engineering and Electronics},
  year = {2019},
  doi = {10.21629/jsee.2019.04.03},
}
Figure