Linearized Polynomial Chinese remainder codes

Technical Summary: Linearized Polynomial Chinese Remainder Codes

Problem Statement
Rank-metric and sum-rank-metric codes, such as Gabidulin and LRPC codes, are critical for applications in telecommunications, distributed storage, and cryptography. However, the diversity of existing code families is often constrained by their specific construction methods, which rely on particular base codes or techniques. There is a need for a more generalized framework that can unify these constructions and offer flexible parameter spaces while maintaining efficient decoding capabilities.

Methodology
The authors introduce a new family of codes called Linearized Chinese Remainder Theorem codes (qCRT codes). The construction relies on the algebraic structure of linearized polynomial rings over finite fields, denoted as $\mathbb{F}_{q^m}\langle X^q \rangle$.

1. Algebraic Foundations: The paper establishes an effective, non-commutative generalization of the Chinese Remainder Theorem (CRT) tailored to linearized polynomials. Unlike classical polynomial rings, these rings are non-commutative skew polynomial rings where multiplication is defined by composition. The authors prove the existence of right Euclidean division, right greatest common divisors (RGCD), and left least common multiples (LLCM). They provide constructive algorithms for these operations, including a generalized extended Euclidean algorithm to compute Bézout relations.
2. Code Construction: A qCRT code is defined as the image of a linear map $\Psi_A$ applied to a space of linearized polynomials of bounded $q$-degree. Specifically, a message polynomial $P$ is multiplied by a fixed polynomial $A$, and the result is mapped to a tuple of remainders modulo a set of coprime linearized polynomials $F = (f_1, \dots, f_s)$. The code length is determined by the sum of the $q$-degrees of the moduli.
3. Decoding Strategy: The decoding algorithm is inspired by the Chinese Remainder lifting technique. It operates under a uniform error model where errors have a specific rank weight.
   • Lifting: The received codeword (a tuple of remainders) is lifted back to a single linearized polynomial $\Phi(y)$.
   • Error Support Recovery: The algorithm exploits the structure of the lifted error. By analyzing the high-degree terms of the lifted polynomial (those exceeding the degree of the valid codeword), it attempts to recover the support of the error.
   • Linear System: Once the error support is identified, the algorithm solves a linear system over the base field $\mathbb{F}_q$ to recover the error coefficients and subsequently the original message.

Key Contributions

1. Mathematical Framework: The paper provides the necessary algebraic foundations for qCRT codes, including an effective CRT and its lifting for linearized polynomials. This allows for the construction of codes with diverse parameters.
2. Unification of Code Families: The authors demonstrate that several well-known code families are special cases of qCRT codes. Specifically:
   • Gabidulin codes are recovered when the moduli are of the form $X^q - \zeta_i^{q-1}X$.
   • Simple codes are obtained when the moduli have coefficients in the base field $\mathbb{F}_q$.
   • The construction also relates to skew Reed-Solomon codes.
3. Probabilistic Decoding Algorithm: A decoding algorithm is proposed for a subclass of qCRT codes where the moduli have coefficients in the base field $\mathbb{F}_q$. The paper provides an explicit analysis of the algorithm's failure rate under a uniform error model.
4. Extension to Small Extension Fields: The decoding strategy is extended to a broader class of codes where moduli reside in small extension fields ($\mathbb{F}_{q^l}$). The authors analyze how the extension degree $l$ impacts the probability of successfully recovering the error support.

Results and Analysis

• Decoding Performance: The success of the decoding algorithm depends on two factors: the ability to recover the full support of the lifted error from the high-degree terms, and the solvability of the resulting linear system.
• Failure Rate Analysis: The paper derives a formula for the probability that the support of the lifted error equals the support of the original error. Numerical experiments illustrate that for certain parameter choices, this probability is close to 1 for a wide range of error weights.
• Parameter Sensitivity: The analysis highlights the role of the extension degree $m$ (of the field $\mathbb{F}_{q^m}$) and the modulus extension degree $l$.
  • Increasing $m$ can allow the linear system bound to exceed the unique decoding radius, potentially enabling the decoding of more errors.
  • However, if $m$ is too large relative to other parameters, the probability of recovering the full error support may drop before the linear system bound is reached, becoming the limiting factor.
  • Similarly, increasing $l$ (the degree of the extension for moduli coefficients) generally reduces the success probability for a given error weight.

Significance and Claims
The paper claims that qCRT codes offer a flexible framework that expands the landscape of rank and sum-rank metric codes. By unifying existing constructions under a single algebraic umbrella, the authors provide a tool for designing codes with tailored properties. The proposed decoding algorithm is significant because it is derived directly from the CRT lifting process and offers a controlled failure rate, making it suitable for applications where probabilistic decoding is acceptable. The work suggests that the flexibility of the construction allows for optimization in various domains, though the paper focuses primarily on the theoretical construction and the analysis of the proposed decoding algorithm's performance.

The authors conclude that future work should aim to eliminate the failure rate of the current decoding algorithm to achieve robust polynomial-time decoding and explore specific applications in distributed storage, probabilistic checkable proofs, and cryptography.