🔢 mathematics

Two Families of Linear Codes Containing Non-GRS MDS Codes

This paper constructs two new families of linear codes derived from generalized Reed-Solomon codes, providing explicit parity-check matrices, necessary and sufficient conditions for the MDS property, and characterizing specific non-GRS MDS, self-orthogonal, and self-dual subfamilies.

Original authors: Kanat Abdukhalikov, Gyanendra K. Verma

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kanat Abdukhalikov, Gyanendra K. Verma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a digital fortress designed to protect secret messages. In the world of coding theory, this fortress is built using "Linear Codes." Think of these codes as a set of rules for arranging bricks (data) so that if some bricks get knocked out (errors) or stolen (noise), you can still perfectly reconstruct the original wall.

The "gold standard" for these fortresses is called an MDS Code (Maximum Distance Separable). These are the ultimate fortresses: they offer the maximum possible protection for the amount of space they take up. If you have a wall of a certain height and width, an MDS code ensures that even if a huge chunk of it is destroyed, you can still figure out what the whole wall looked like.

The Old Blueprint: GRS Codes

For a long time, the only known way to build these perfect fortresses was using a specific, well-understood blueprint called Generalized Reed-Solomon (GRS) codes. It's like a famous, reliable architectural style used for centuries. Everyone knows how to build them, and they work great.

However, there's a problem: Predictability is dangerous.
In cryptography (secret keeping), if an enemy knows exactly how your fortress is built, they can find a secret backdoor. Because GRS codes are so famous and uniform, hackers have developed specific attacks (like the Sidelnikov-Shestakov attack) that can break them. We need fortresses that look perfect on the outside (MDS) but are built using a completely different, unknown blueprint (Non-GRS) so the hackers can't find the backdoor.

The New Discovery: Two New Families

The authors of this paper, Kanat Abdukhalikov and Gyanendra K. Verma, have discovered two new families of blueprints for building these perfect, yet mysterious, fortresses.

Here is how they did it, using simple analogies:

1. The "Missing Row" Trick (Family $C_{i,j}$ )

Imagine the standard GRS blueprint is a giant grid of numbers, like a spreadsheet.

The Old Way: You use the whole spreadsheet.
The New Way: The authors take the spreadsheet and delete two specific rows of numbers, then rearrange the remaining rows in a clever way.
The Magic: Even though they removed parts of the original design, the resulting structure is still a perfect fortress (an MDS code). But because the pattern of missing rows is unique, the resulting code looks nothing like the old GRS blueprint. It's a "Non-GRS" code.
The Result: They figured out exactly which rows to delete and under what conditions the fortress remains perfect. They also found a way to build "Self-Dual" fortresses, which are special structures that are their own mirror images—useful for advanced quantum computing.

2. The "Jumping Power" Trick (Family $C_{h,k}$ )

Imagine the standard blueprint lists powers of a number: $1, x, x^2, x^3, x^4...$

The Old Way: You use the first $k$ powers in order.
The New Way: The authors take the first few powers ( $1, x, x^2...$ ) but then skip ahead and grab a much higher power (like $x^{100}$ ) instead of the next one in line.
The Magic: This "jump" creates a structure that is still a perfect fortress (MDS) but has a completely different internal rhythm. It's like building a staircase where you take normal steps for a while, then suddenly take a giant leap, then continue with normal steps. The resulting shape is stable and strong, but it doesn't look like the standard staircase.

Why Does This Matter?

Security: Because these new codes are "Non-GRS," they are immune to the specific attacks that break the old GRS codes. This makes them ideal for cryptography (keeping secrets safe) and secure communication.
Quantum Computing: The authors also showed how to build "Self-Orthogonal" codes (codes that fit inside their own shadows). These are the building blocks for Quantum Error Correction, which is essential for making quantum computers work without crashing.
New Possibilities: They didn't just say "it's possible"; they gave explicit recipes (formulas and examples) showing exactly how to build these codes for different sizes of data. They even showed how to build them for very large data sets, which was a hard problem before.

The Big Picture

Think of the world of data protection as a game of hide-and-seek.

GRS Codes are like hiding behind a standard, white fence. Everyone knows where to look.
This Paper introduces two new types of hiding spots: one where you remove parts of the fence to create a unique pattern, and another where you build the fence with giant, irregular gaps.
These new hiding spots are just as strong as the old ones (MDS), but because they look so different, the "seekers" (hackers) can't find them.

The authors have essentially handed us two new, secret keys to building unbreakable digital fortresses, expanding our toolkit for keeping the digital world safe.

1. Problem Statement

The paper addresses the construction and classification of Maximum Distance Separable (MDS) codes that are not equivalent to Generalized Reed-Solomon (GRS) codes (non-GRS MDS codes).

Context: MDS codes are optimal in terms of error correction capability for a given length and dimension. While GRS codes are the most well-known family of MDS codes, they are limited in length (at most $q+1$ ) and possess specific algebraic structures.
Motivation:
- Theoretical: The "MDS Conjecture" suggests that for most parameters, all MDS codes are GRS codes. Finding non-GRS MDS codes challenges this classification and expands the understanding of arcs in finite projective geometries.
- Cryptographic: Non-GRS MDS codes offer resistance against specific attacks (e.g., Sidelnikov-Shestakov and Wieschebrink attacks) that can break cryptographic systems based on GRS codes.
Gap: Existing constructions (e.g., Twisted Reed-Solomon codes) have been studied, but the authors aim to discover new families with distinct structural properties and explicit parity-check matrices.

2. Methodology

The authors employ algebraic coding theory techniques, specifically focusing on:

Generator Matrix Modification: They construct new codes by modifying the generator matrices of standard GRS codes. Specifically, they remove specific rows from the Vandermonde matrix associated with GRS codes and, in some cases, replace them with higher-degree monomials.
Schur Square Method: To prove that the constructed codes are non-GRS, they utilize the Schur (Hadamard) product.
- Key Lemma: An MDS code $C$ with $\dim(C) \le (n-1)/2$ is a GRS code if and only if $\dim(C \star C) = 2\dim(C) - 1$ .
- Strategy: They demonstrate that for their constructed codes, $\dim(C \star C) \ge 2\dim(C)$ , thereby proving they are not GRS.
Symmetric Functions: The analysis relies heavily on elementary symmetric functions ( $\sigma_t$ ) and complete symmetric functions ( $S_t$ ) to derive parity-check matrices and establish MDS conditions.
Self-Orthogonality/Duality: They investigate conditions under which these codes can be made self-orthogonal ( $C \subseteq C^\perp$ ) or self-dual ( $C = C^\perp$ ) by scaling the generator matrix with a vector $v$ .

3. Key Contributions and Results

The paper introduces two distinct families of linear codes, denoted as $C_{i,j}$ and $C_{h,k}$ .

Family 1: Codes $C_{i,j}$

Construction: Generated by a matrix $G_{i,j}$ obtained by removing the $(i+1)$ -th and $(j+1)$ -th rows from the generator matrix of a GRS code of length $n$ and dimension $k+2$ .
MDS Conditions: The authors derive a necessary and sufficient condition for $C_{i,j}$ $C_{i, j}$ to be MDS. This condition involves the non-vanishing of a specific determinant related to elementary symmetric functions of subsets of the evaluation points $\Lambda$ $Λ$ .
- Condition: $\sigma_{k-i}(\beta)\sigma_{k-j+1}(\beta) - \sigma_{k-i+1}(\beta)\sigma_{k-j}(\beta) \neq 0$ for all distinct subsets $\beta \subset \Lambda$ .
Parity-Check Matrix: An explicit parity-check matrix $H_{i,j}$ is derived, involving terms of the form $u_m \Gamma_{i,m}$ , where $u_m$ are inverse Vandermonde products and $\Gamma$ involves symmetric functions.
Non-GRS Property: Using the Schur square method, they prove that for specific ranges of $k$ (e.g., $k \ge 5$ ) and $n$ , these codes are non-GRS.
Self-Duality: They provide conditions for $C_{i,j,v}$ to be self-dual. Notably, they show that for certain parameters, self-dual codes exist only if specific symmetric sums ( $S_1, S_2, S_3$ ) vanish.

Family 2: Codes $C_{h,k}$

Construction: Generated by a matrix $G_{h,k}$ consisting of the first $k-1$ rows of a Vandermonde matrix (powers $0$ to $k-2$ ) and one additional row with power $h$ (where $h \ge k-1$ ).
MDS Conditions: The code is MDS if and only if the complete symmetric function $S_{h-k+1}(\beta) \neq 0$ for all distinct subsets $\beta \subset \Lambda$ .
Parity-Check Matrix: A structured parity-check matrix $H_{h,k}$ is constructed using coefficients derived from symmetric functions and the inverse Vandermonde terms.
Non-GRS Property: The authors prove that for a wide range of parameters (including cases where $h = k$ $h = k$ and $h > k$ $h > k$ ), these codes are non-GRS.
- Significance: Remark 4.1 highlights that the Schur square dimension of these codes is often $2k+1$ or higher, distinguishing them from other known non-GRS constructions (like those in [25, 23]) which have Schur square dimension $2k$ .
Explicit Constructions: The paper provides explicit constructions of non-GRS MDS codes with lengths up to $(q/p)^{1/2}$ and even $q+2$ (for even characteristic fields), utilizing specific choices of evaluation points based on polynomial bases.

Self-Orthogonal and Self-Dual Properties

The paper characterizes when these families can be scaled to become self-orthogonal or self-dual.
Theorem 4.9 & Corollary 4.10: For the second family ( $C_{h,k}$ ), self-duality is possible if and only if $r=1$ (where $h=k-1+r$ ) and specific symmetric sums vanish. In fields of even characteristic, the condition simplifies to $r=1$ and $S_1=0$ .
Examples: Several concrete examples are provided over finite fields (e.g., $F_{17}, F_{25}, F_{37}$ ) demonstrating the construction of self-dual and self-orthogonal codes with specific generator matrices.

4. Significance

Expansion of Code Families: The paper successfully identifies two new infinite families of non-GRS MDS codes, contributing to the classification of MDS codes and the study of arcs in finite projective spaces.
Cryptographic Relevance: By providing explicit constructions of non-GRS MDS codes, the work offers new candidates for cryptographic schemes that require resistance against algebraic attacks targeting GRS structures.
Explicit Parity-Check Matrices: Unlike some previous works that only prove existence, this paper provides explicit formulas for parity-check matrices, which are crucial for practical decoding algorithms.
Self-Dual Constructions: The characterization of self-dual variants within these families is valuable for quantum error correction (where self-orthogonal codes are essential) and lattice theory.
Future Directions: The authors suggest that generalizing these constructions to deleting an arbitrary number of rows (beyond two) is a natural but significantly more complex direction for future research.

In summary, this paper advances the theory of MDS codes by rigorously constructing and analyzing two new families that break the GRS equivalence, providing the necessary algebraic tools (parity-check matrices, Schur square analysis) to verify their properties and utility.