On a Theorem of Kyureghyan and Pott

Minglong Qi, Shengwu XiongarXiv 2018 · arXiv

Abstract

This paper identifies and rectifies significant mathematical errors found in the foundational 2003 study by Kyureghyan and Pott regarding the linear complexity of Sidel’nikov-Lempel-Cohn-Eastman (SLCE) sequences. By identifying a logical flaw in the negation of a key lemma, the authors demonstrate that previously established theorems regarding the linear feedback polynomials of these sequences are incorrect. Through the use of Jacobsthal sums and concrete counterexamples, this work provides corrected versions of these theorems, ensuring accurate assessment of the cryptographic strength of SLCE sequences.

Introduction

In the fields of cryptography and digital communications, sequences that appear random but are deterministic—such as Sidel’nikov-Lempel-Cohn-Eastman (SLCE) sequences—are essential. These sequences are favored for their excellent autocorrelation properties, meaning they do not align with shifted versions of themselves.

A critical measure of a sequence's security is its linear complexity, defined as the length of the shortest Linear Feedback Shift Register (LFSR) capable of generating it. A low linear complexity allows an attacker to predict the sequence with minimal data. In 2003, Kyureghyan and Pott published a study attempting to determine the linear feedback polynomials for these sequences. However, subsequent analysis by Qi and Xiong revealed that two major results were mathematically flawed, potentially leading to incorrect conclusions regarding sequence security.

Methodology

The authors employ classical tools from finite field theory and discrete mathematics to re-evaluate the sequences:

  • Polynomial Analysis: The authors examine the greatest common divisor (GCD) between the sequence polynomial and $x^{q-1} + 1$ to determine the feedback polynomial.
  • Jacobsthal Sums: These specific character sums are used to evaluate the distribution of quadratic residues in finite fields. The authors use these sums to verify if certain polynomials divide the sequence's generator.
  • Counterexample Construction: The authors utilize "proof by contradiction" through specific prime powers (e.g., $q=49, 193, 769, 12289$) to show that the original 2003 formulas produce demonstrably false results.
  • Logical Correction: The authors identify that the original error stemmed from an incorrect logical negation of a fundamental lemma. They re-derive the "necessary and sufficient" conditions by correctly applying the negation.

Analysis of the Logical Error

The "aha moment" of this research is the realization of a subtle but catastrophic logic gap in the 2003 paper. The original authors' necessary and sufficient conditions were not actually equivalent to the logical negation of their own proven lemma. This created an "absurd" mathematical situation where a specific polynomial $g(x)$ could simultaneously be a factor and not be a factor of the sequence polynomial.

Furthermore, the paper demonstrates that Jacobsthal sums $I_r(a)$ must be evaluated across a specific set of elements to truly determine if a factor exists. The original conditions were either too broad or incorrectly mapped to the finite field elements.

Key Results and Corrections

The paper formally invalidates Corollary 4 and Theorem 2 from the Kyureghyan-Pott (2003) paper and provides the following corrections:

  1. Counterexample for $q=49$: The authors show that for $q=49$, the original theory predicts a simple GCD, but the actual GCD contains an additional factor $(x^2 + x + 1)^2$.
  2. Corrected Corollary 2: The authors provide the accurate conditions under which the GCD of the sequence polynomial and $x^{q-1}+1$ is simply a power of $(x+1)$.
  3. Corrected Theorem 1: This provides the definitive formula for the linear feedback polynomial of SLCE sequences when $q = 2^k r + 1$ (where $r$ is an odd prime). This allows researchers to accurately calculate the linear complexity for these specific cases.

Limitations and Future Work

While these corrections are vital, they specifically target cases where $q = 2^k r + 1$. This is not yet a universal solution for every possible value of $q$. Additionally, calculating Jacobsthal sums for very large fields remains computationally intensive.

The authors suggest that their method of "readopting the negation" could be applied to other types of sequences, such as those based on different cyclotomic classes, to ensure their linear complexity profiles are correctly understood and secured against cryptographic attacks.

Summary updated

BibTeX
@misc{qi2018theorem,
  author = {Minglong Qi and Shengwu Xiong},
  title = {{On a Theorem of Kyureghyan and Pott}},
  year = {2018},
  eprint = {1810.02599},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.02599},
}
Figure