Linear Complexity over Fq of Generalized Cyclotomic Quaternary Sequences with Period 2p

Minglong Qi, Shengwu Xiong, Jingling Yuan, Wenbi Rao, Luo ZhongIEICE Trans. Fundam. Electron. Commun. Comput. Sci 2015 · DOI

TL;DR

This paper analyzes the linear complexity of generalized cyclotomic quaternary sequences, a crucial metric for their suitability in cryptography. The authors determine the exact linear complexity for various conditions on the prime parameters, showing it's generally greater than half the sequence length, indicating good cryptographic properties. They also identify specific conditions under which the linear complexity reaches its maximum possible value.

What Problem Does This Paper Address?

In cryptography, especially for stream ciphers, sequences with good "random-like" properties are essential. Two key properties are good balance (ensuring roughly equal numbers of 0s and 1s) and high linear complexity. Linear complexity, in essence, measures how difficult it is to predict the next element of a sequence using a linear feedback shift register (LFSR). A higher linear complexity means a longer LFSR is needed, making the sequence harder to break. Generalized cyclotomic sequences are a family of sequences known for their good algebraic structure and potential cryptographic applications. This paper focuses on determining the linear complexity of a specific type: generalized cyclotomic quaternary sequences (using four symbols, not just binary) with a period of $2pq$, where $p$ and $q$ are distinct odd primes. The challenge lies in precisely calculating this complexity, which depends on the interplay of the field characteristics and the prime factors of the period.

Methods

The core of this paper involves detailed number-theoretic analysis and algebraic manipulation. The authors leverage the Berlekamp-Massey algorithm, a standard tool for finding the minimal polynomial of a sequence, which directly relates to its linear complexity. They analyze the generating polynomial of the sequences and, crucially, its zeros in an extension field. By understanding the number and nature of these zeros, they can deduce the degree of the greatest common divisor (GCD) between the generating polynomial and $x^{2T}-1$ (where $2T$ is the period), which in turn determines the linear complexity. The paper employs extensive use of number theory concepts such as quadratic residues, Legendre symbols, primitive roots, and the Chinese Remainder Theorem to break down the problem into various cases based on the properties of primes $p$, $q$, and $r$ (the field characteristic). Several lemmas are proven and utilized, building upon existing results to establish properties of various sets and mappings related to the cyclotomic structure.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Generalization of Known Results: The paper extends previous work on linear complexity of cyclotomic sequences to the quaternary case, which is less explored.
  • Interplay of Field and Prime Properties: The linear complexity is highly sensitive to the relationship between the field characteristic $r$ and the primes $p, q$, particularly their residues modulo 4 and 8, and their divisibility properties.
  • Minimal vs. Maximal Complexity: The authors show that the linear complexity is generally greater than half the period ($2pq$), a threshold considered sufficient for cryptographic use. They also identify specific conditions under which the linear complexity reaches its maximum possible value ($2pq$), which is highly desirable for security.
  • Case-by-Case Analysis: The complexity of the analysis is evident in the numerous theorems and lemmas that meticulously break down the problem based on different congruences and divisibility conditions of $p, q, r$.

Key Results

The paper provides explicit formulas for the linear complexity of generalized cyclotomic quaternary sequences of period $2pq$ over $GF(r)$ under various conditions. For instance, under certain conditions, the minimal linear complexity is found to be $\frac{5pq+p+q+1}{4}$, which is greater than half the period. Under specific choices of $r$, $p$, and $q$ (e.g., when $r$ is a quadratic non-residue modulo $p$ and $q$, and satisfies certain divisibility conditions), the linear complexity can reach the maximal value of $2pq$. The paper presents a comprehensive set of theorems (Theorem 3.1 through 3.12) detailing these complexities for different scenarios.

Limitations and Future Work

The paper focuses on specific types of generalized cyclotomic quaternary sequences and specific field characteristics. While the analysis is exhaustive for the cases considered, it does not cover all possible parameters or variations of these sequences. The authors suggest that further research could explore other types of generalized cyclotomic sequences or sequences over different fields. The complexity of the derived formulas, while precise, can be computationally intensive to evaluate for arbitrary large primes $p$ and $q$.

Summary updated

BibTeX
@article{qi2015linear,
  author = {Minglong Qi and Shengwu Xiong and Jingling Yuan and Wenbi Rao and Luo Zhong},
  title = {{Linear Complexity over Fq of Generalized Cyclotomic Quaternary Sequences with Period 2p}},
  journal = {IEICE Trans. Fundam. Electron. Commun. Comput. Sci.},
  year = {2015},
  doi = {10.1587/transfun.e98.a.1569},
}
Figure