Linear complexity of Ding-Helleseth generalized cyclotomic sequences of order eight

Abstract

During the last two decades, many kinds of periodic sequences with good pseudo-random properties have been constructed from classical and generalized cyclotomic classes, and used as keystreams for stream ciphers and secure communications. Among them are a family DH-GCS${}_d$ of generalized cyclotomic sequences on the basis of Ding and Helleseth's generalized cyclotomy, of length $pq$ and order $d=\gcd (p-1,q-1)$ for distinct odd primes $p$ and $q$. The linear complexity (or linear span), as a valuable measure of unpredictability, is precisely determined for DH-GCS${}_8$ in this paper. Our approach is based on Edemskiy and Antonova's computation method with the help of explicit expressions of Gaussian classical cyclotomic numbers of order $8$. Our result for $d=8$ is compatible with Yan's low bound $(pq-1)/2$ of the linear complexity for any order $d$, which means high enough to resist security attacks of the Berlekamp-Massey algorithm. Finally, we include SageMath codes to illustrate the validity of our result by examples.

18 pages, 7 tables