Linear Complementary Pairs of Quasi-Cyclic and Quasi-Twisted Codes

Kanat Abdukhalikov Department of Mathematical Sciences, UAE University, PO Box 15551, Al Ain, UAE Email: [email protected] Duy Ho Department of Mathematics and Statistics, UiT The Arctic University of Norway, Tromsø 9037, Norway Email: [email protected] San Ling School of Physical and Mathematic · 2025

Read Linear Complementary Pairs of Quasi-Cyclic and Quasi-Twisted Codes by Kanat Abdukhalikov Department of Mathematical Sciences, UAE University, PO Box 15551, Al Ain, UAE Email: [email protected] Duy Ho Department of Mathematics and Statistics, UiT The Arctic University of Norway, Tromsø 9037, Norway Email: [email protected] San Ling School of Physical and Mathematic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15231.txt.

Introduction

Kanat Abdukhalikov, Duy Ho, San Ling, and Gyanendra Verma study pairs of error-correcting codes in a 2025 math paper. A linear complementary pair is two codes that fit together like a lock and key: together they span the whole space, and they share no nonzero word. Such pairs guard data against probing attacks.

The codes here are quasi-cyclic and quasi-twisted, built from blocks that shift with a twist, at index two. The authors give a polynomial test that tells exactly when two such codes form a complementary pair. They back the test with worked examples whose security strength is the best possible. Results like this help engineers pick code pairs for protected storage and communication.

Catalog record

CREATORKanat Abdukhalikov Department of Mathematical Sciences, UAE University, PO Box 15551, Al Ain, UAE Email: [email protected] Duy Ho Department of Mathematics and Statistics, UiT The Arctic University of Norway, Tromsø 9037, Norway Email: [email protected] San Ling School of Physical and Mathematic
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15231

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Linear Complementary Pairs of Quasi-Cyclic and Quasi-Twisted Codes Kanat Abdukhalikov Department of Mathematical Sciences, UAE University, PO Box 15551, Al Ain, UAE Email: [email protected] Duy Ho Department of Mathematics and Statistics, UiT The Arctic University of Norway, Tromsø 9037, Norway Email: [email protected] San Ling School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371 Email: [email protected] Gyanendra K. Verma Department of Mathematical Sciences, UAE University, PO Box 15551, Al Ain, UAE Email: [email protected] Abstract In this paper, we provide a polynomial characterization of linear complementary pairs of quasi-cyclic and quasi-twisted codes of index 2 2 . We also give several examples of linear complementary pairs of quasi-cyclic and quasi-twisted codes with optimal security parameters. Keywords : Quasi-cyclic codes, quasi-twisted codes, linear complementary pairs of codes. Mathematics subject classification : 94B05, 94B15, 94B60. 1 Introduction Quasi-cyclic codes are a class of codes that includes cyclic codes. Townsend and Weldon introduced these codes [ 30 ] in 1967. It is already known that quasi-cyclic codes are asymptotically good. Beyond classical communication and data storage applications, quasi-cyclic codes are used in modern post-quantum cryptographic systems, such as QC-MDPC code-based protocols, due to their balance of security and compact key sizes. A systematic study of the algebraic structure of quasi-cyclic codes over finite fields and rings has been done in [ 22 , 23 , 24 , 25 ] . In 2023, Abdukhalikov et al. [ 1 ] investigated one-generator quasi-cyclic codes over finite fields and determined the duals in polynomial representation. Lally and Fitzpatrick [ 20 ] gave the polynomial characterization of quasi-cyclic codes by proving that every quasi-cyclic code has a generating set consisting of \ell -tuples polynomials with certain properties derived from reduced Gröbner basis. Based on these structural properties, more asymptotic results, minimum distance bounds, and further applications of quasi-cyclic codes were obtained in the literature ( [ 26 , 29 , 32 ] ). Further, using polynomial characterization, quasi-cyclic codes of index 2 have been investigated in [ 2 ] . Quasi-twisted codes are another generalization of cyclic codes that includes constacyclic and quasi-cyclic codes. Additionally, they are known to be asymptotically good ( [ 12 , 31 , 19 ] ). Many record-breaking codes with excellent parameters have been constructed within this class (e.g., see [ 4 , 6 , 28 ] ). A pair of linear codes of the same length over a finite field is called a linear complementary pair (LCP) of codes if the codes intersect trivially and the direct sum of the codes is the whole ambient space. LCPs of codes have been extensively studied due to their nice algebraic structure and wide applications in cryptography. Ngo et al. [ 27 ] introduced LCPs of codes in 2015 and showed their applications in resistance against physical attacks like side-channel attacks (SCA) and fault injection attacks (FIA). This method is known as Direct Sum Masking (DSM). The security parameters of a given LCP (C,D) over a finite field depend on \min\{d(C),d(D^{\perp})\} , where d(C) denotes the minimum Hamming distance of C and d(D^{\perp}) denotes the dual distance of D (for details, see [ 9 , 10 ] ). Linear complementary dual (LCD) codes are a special case of an LCP of codes where D=C^{\perp} . The security parameters of an LCD code depend only on the minimum distance of the code. In 2018, Carlet et al. [ 10 ] characterized LCPs of quasi-cyclic codes using the Chinese Remainder Theorem (CRT) decomposition of codes and also provided necessary and sufficient conditions for pairs of constacyclic and double circulant codes to be an LCP of codes. Moreover, they proved that if (C,D) is an LCP of constacyclic or 2D cyclic code, then C and D^{\perp} are permutation equivalent. Güneri et al. [ 16 ] showed the equivalence of C and D^{\perp} holds for an LCP of mD -cyclic codes as well. These results show that finding LCD codes and LCPs of codes is the same in the context of security parameters. However, C and D^{\perp} need not be permutation equivalent for an LCP of quasi-cyclic codes [ 10 , Example 3.3] . In [ 11 ] , Carlet et al. proved that for q>2 , there exists an LCP of linear codes with security parameters as good as the optimal distance of linear codes, and for q=2 , the security parameters of optimal binary LCPs of linear codes are lower bounded by one less than the optimal distance of linear codes. In [ 13 , 15 , 21 ] , the authors discussed optimal binary LCPs of linear codes. In this work, we give a polynomial characterization of LCPs of quasi-cyclic and quasi-twisted codes with index 2 . Using these characterizations, we provide several examples of optimal LCPs of quasi-twisted codes over \mathbb{F}_{q} . The rest of the paper is organized as follows. In Section 2 , we recall the basics of LCPs of codes and the decomposition of quasi-cyclic codes. In Section 3 , we establish necessary and sufficient conditions for LCPs of quasi-cyclic codes of index 2 . We discuss LCPs of one-generator quasi-cyclic codes in Section 4 . We characterize LCPs of quasi-twisted codes in Section 5 . In Section 6 , we give several examples of LCPs of quasi-cyclic codes. 2 Preliminaries We denote \mathbb{F}_{q} as a finite field with q elements. A linear code over \mathbb{F}_{q} of length n is a subspace of \mathbb{F}_{q}^{n} . We say C is an [n,k] code over \mathbb{F}_{q} code if C is a linear code of length n and \dim_{\mathbb{F}_{q}}(C)=k . Let C and D be linear codes of length n over \mathbb{F}_{q} . Then (C,D) is called a linear complementary pair (LCP) of codes if they have the trivial intersection and their direct sum is the ambient space \mathbb{F}_{q}^{n} . That is, C\oplus D=\mathbb{F}_{q}^{n}. Note that if C has parameters [n,k] , then D must have parameters [n,n-k] . Linear complementary dual (LCD) codes are a special class of LCPs of codes where D is the dual code of C . Equivalently, C is an LCD code if C\cap C^{\perp}=\{0\} . Let \lambda\in\mathbb{F}_{q}^{*} . We define the cyclic \lambda -shift operator as T_{\lambda}(x_{0},x_{1},\dots,x_{n-1})=(\lambda x_{n-1},x_{0},\dots,x_{n-2}). A linear code is said to be a \lambda -quasi-twisted code of length n and index \ell (in short, (\lambda,\ell) -quasi-twisted) if T_{\lambda}^{\ell}(c)\in C for all c\in C . If \lambda=1 , then C is called a quasi-cyclic code of index \ell . When \ell=1 , then C is called a \lambda -constacyclic code, and when \ell=1 \lambda=1 , C is called a cyclic code. If C is a \lambda -quasi-twisted code of length n and index \ell , then one can assume that \ell divides n . Thus, we assume that n=m\ell . Let R_{\lambda}=\mathbb{F}_{q}[x]/\langle x^{m}-\lambda\rangle and for \lambda=1 , we denote R_{1} by R . Note that \lambda -constacyclic codes over \mathbb{F}_{q} of length m are ideals of R_{\lambda} . Let C be a \lambda -quasi-twisted code of length n=m\ell and index \ell over \mathbb{F}_{q} . It is well known that C can be identified as an R_{\lambda} -submodule of R_{\lambda}^{\ell} (for instance, see [ 18 ] ). The correspondence is given by (c_{0,0},c_{0,1},\dots,c_{0,\ell-1},c_{1,0},\dotsc_{1,\ell-1},\dots,c_{m-1,0},\dots,c_{m-1,\ell-1})\mapsto(c_{0}(x),c_{1}(x),\dots c_{\ell}(x))\in R_{\lambda}^{\ell}, where c_{i}(x)=c_{0,i}+c_{1,i}x+\dots+c_{m-1,i}x^{m-1}\in

Read the complete text