🔢 mathematics

On the Direct Construction of MDS and Near-MDS Matrices

This paper introduces direct construction methods for both recursive and nonrecursive Near-MDS (NMDS) matrices, as well as nonrecursive MDS and involutory MDS/NMDS matrices derived from generalized Vandermonde matrices, while also proving foundational results related to NMDS codes.

Original authors: Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

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 super-secure digital vault (a cryptographic system) to protect your secrets. To make this vault truly safe, you need a mechanism that scrambles your data so thoroughly that if even a tiny piece of the original message is changed, the entire scrambled result looks completely different. This is called diffusion.

In the world of cryptography, the "scramblers" used for this job are mathematical grids called Matrices.

This paper is about inventing new, better ways to build these scramblers. Here is the breakdown in simple terms:

1. The Goal: The Perfect Scrambler (MDS) vs. The "Good Enough" Scrambler (NMDS)

Think of a Matrix as a recipe for mixing ingredients.

MDS Matrices (Maximum Distance Separable): These are the "Gold Standard." They are like a master chef who mixes ingredients so perfectly that no matter how you look at the result, every single part of the original recipe is represented. They offer the highest possible security. However, they are very expensive to cook (computationally heavy), requiring a lot of energy and time.
NMDS Matrices (Near-MDS): These are the "Budget-Friendly" chefs. They mix ingredients almost as well as the masters, but with a tiny bit less perfection. The security is slightly lower, but they are much faster and use less energy. This is perfect for lightweight devices like smart cards, sensors, or IoT gadgets that have tiny batteries.

The Problem: For the "Gold Standard" (MDS), mathematicians have had many recipes for a long time. But for the "Budget-Friendly" (NMDS), especially the kind that can be built recursively (repeating a simple step over and over), there were no direct recipes. People had to guess and check (search) for them, which is slow and inefficient.

2. The Solution: New Recipes from a Special Toolbox

The authors of this paper say, "Let's stop guessing and start building directly." They introduce a new toolbox called Generalized Vandermonde Matrices.

To understand this, imagine a standard Vandermonde Matrix as a ladder. Each rung is a power of a number (1, x, x², x³...). It's a very structured, predictable ladder.

The Twist: The authors use a Generalized ladder. They skip some rungs or rearrange them in specific ways. This creates a structure that is flexible enough to be either the "Gold Standard" (MDS) or the "Budget-Friendly" (NMDS), depending on how they tune the numbers.

3. The Two Main Strategies

Strategy A: The "Recursive" Method (The Staircase)

Imagine you have a small, simple staircase (a small matrix). If you walk up it once, you get somewhere. If you walk up it twice, you get somewhere else. If you walk up it n times, you reach the top.

The Innovation: The paper provides a direct formula to design that first small staircase so that when you walk up it n times, you end up with a perfect (or near-perfect) scrambler.
Why it matters: Before this, no one knew how to design the small staircase specifically to create a "Near-MDS" result. Now, they have a blueprint. This is huge for lightweight cryptography because walking up a small staircase repeatedly is very fast and cheap for computers.

Strategy B: The "Non-Recursive" Method (The Big Mixing Bowl)

Sometimes you don't want to repeat steps; you want one giant, powerful mix.

The Innovation: The authors show how to take two of these "Generalized Ladders" and combine them (mathematically multiplying one by the inverse of the other) to create a massive, perfect scrambler.
The Magic Trick: They discovered that by carefully choosing which "rungs" to skip in their ladders (using something called a set $I$ ), they can force the resulting mix to be either MDS or NMDS.

4. The "Self-Undoing" Feature (Involutory Matrices)

In cryptography, you need to encrypt (lock) and decrypt (unlock). Usually, you need two different keys or two different recipes.

The Cool Discovery: The authors found a way to build matrices that are Involutory. This means the matrix is its own inverse.
The Analogy: Imagine a lock that, when you turn the key to lock it, it also unlocks it if you turn it again. You don't need a second key; the same tool does both jobs. This saves massive amounts of space and power in hardware.
The Breakthrough: They provided the first direct recipe for building "Near-MDS" matrices that are also self-undoing.

5. Why This Paper Matters

Filling the Gap: It solves a missing piece in the puzzle. We finally have direct recipes for "Near-MDS" recursive matrices, which were previously missing.
Efficiency: It gives engineers a way to build secure systems for tiny devices (like medical implants or smart home sensors) without draining their batteries.
Mathematical Proof: They didn't just guess; they proved that their recipes work using solid math, clearing up some confusion in the field about how these codes behave.

Summary

Think of this paper as a cookbook that finally gives us the exact instructions for baking a "near-perfect" cake (NMDS) that is also easy to make (recursive) and can be eaten with the same fork used to bake it (involutory). Before, we only had instructions for the "perfect" cake or had to guess how to make the "near-perfect" one. Now, we have a clear, direct path to building secure, efficient digital locks for the future of the Internet of Things.

1. Problem Statement

The paper addresses the challenge of constructing Maximum Distance Separable (MDS) and Near-MDS (NMDS) matrices, which are critical components in the diffusion layers of symmetric-key cryptographic primitives (block ciphers and hash functions).

MDS Matrices: Offer optimal branch numbers, ensuring maximum diffusion, but often require high implementation costs (hardware area/latency) for large orders.
NMDS Matrices: Offer a sub-optimal branch number but provide a better trade-off between security and efficiency, making them ideal for lightweight cryptography.
The Gap: While extensive research exists on search-based methods (exhaustive search) and direct constructions for MDS matrices, there is a significant lack of direct construction methods for recursive NMDS matrices. Furthermore, existing direct constructions for involutory (self-inverse) NMDS matrices are non-existent in the literature. Exhaustive search is infeasible for large matrix orders or large finite fields due to the exponential growth of the search space.

2. Methodology

The authors propose a direct construction framework based on algebraic structures, specifically Generalized Vandermonde Matrices and Companion Matrices, rather than relying on exhaustive search.

A. Recursive Constructions (Companion Matrices)

The paper focuses on constructing matrices $B$ such that $B^m$ (where $m \ge n$ ) is an MDS or NMDS matrix.

Theoretical Basis: The authors utilize the property that a companion matrix $C_g$ associated with a polynomial $g(x)$ having distinct roots can be diagonalized as $C_g = V D V^{-1}$ , where $V$ is a Vandermonde matrix and $D$ is a diagonal matrix of eigenvalues.
Strategy:
- They derive conditions on the roots ( $\lambda_i$ ) of the polynomial $g(x)$ to ensure that the resulting matrix $C_g^m$ satisfies the rank conditions required for MDS or NMDS codes.
- For NMDS: They intentionally introduce specific linear dependencies (zero-sum constraints) among subsets of roots to satisfy the NMDS criteria (where $d_1 = n-k$ and $d_2 = n-k+2$ ).
- For MDS: They ensure that no such zero-sum dependencies exist for any subset of size $n$ .

B. Non-Recursive Constructions (Generalized Vandermonde Matrices)

The authors utilize Generalized Vandermonde Matrices ( $V^\perp(x; I)$ ), which are standard Vandermonde matrices with specific exponents removed (defined by a set $I$ ).

Mechanism: They construct MDS/NMDS matrices in the form $A = V_1^{-1} V_2$ , where $V_1$ and $V_2$ are generalized Vandermonde matrices over a finite field $\mathbb{F}_q$ .
Determinant Analysis: Using theorems regarding the determinants of generalized Vandermonde matrices (involving elementary symmetric polynomials), they derive precise algebraic conditions on the elements $x_i$ to ensure that all square submatrices of $A$ are non-singular (for MDS) or satisfy specific rank deficiencies (for NMDS).
Involutory Construction: To create involutory matrices (where $A = A^{-1}$ ), they impose a symmetric algebraic relationship between the elements of $V_1$ and $V_2$ (specifically $x_{n+i} = l + x_i$ over fields of characteristic 2), ensuring the resulting product is its own inverse.

3. Key Contributions

The paper makes four primary contributions:

First Direct Construction of Recursive NMDS Matrices:
- The authors propose new methods to construct recursive NMDS matrices using companion matrices. This fills a critical gap, as no prior direct construction existed for this class.
- They provide specific theorems (Theorem 10, Lemma 11) detailing the conditions on polynomial roots to achieve the NMDS property.
Direct Construction of Recursive MDS Matrices:
- A new direct construction for recursive MDS matrices is introduced (Theorem 11), offering an alternative to existing coding-theoretic approaches (like shortened BCH or Gabidulin codes).
Generalized Vandermonde Framework for Non-Recursive Matrices:
- The paper introduces a novel approach using Generalized Vandermonde matrices with specific exponent sets $I \in \{1, n-1, 1, n\}$ .
- MDS: Theorems 12, 15, and 17 provide direct constructions for non-recursive MDS matrices.
- NMDS: Theorems 13 and 16 provide the first direct constructions for non-recursive NMDS matrices using this framework.
Involutory MDS and NMDS Constructions:
- Involutory MDS: A method is developed to construct involutory MDS matrices (Corollary 7).
- Involutory NMDS: The paper presents the first direct construction of involutory NMDS matrices over finite fields (Corollary 8), a significant advancement for lightweight cryptography where self-inverse diffusion layers reduce decryption costs.
Theoretical Proofs:
- The paper provides formal proofs for several "folklore" results regarding NMDS codes and generalized Hamming weights that are frequently cited but previously lacked rigorous proof in the literature.

4. Results and Validation

Theoretical Validation: The authors prove that their constructions satisfy the necessary rank conditions for MDS and NMDS codes (e.g., any $k$ columns of the generator matrix are linearly independent for MDS; specific rank deficiencies for NMDS).
Concrete Examples: The paper provides explicit numerical examples over finite fields (e.g., $\mathbb{F}_{2^4}$ $F_{2^{4}}$ and $\mathbb{F}_{2^8}$ $F_{2^{8}}$ ) demonstrating the feasibility of the proposed methods.
- Example 4 & 5: Show recursive NMDS matrices constructed from specific polynomials.
- Example 11 & 12: Demonstrate the construction of $6 \times 6$ involutory MDS and $4 \times 4$ involutory NMDS matrices, respectively.
Comparison: Table 1 in the paper summarizes the novelty, highlighting that the proposed methods are the first to offer direct constructions for recursive NMDS and involutory NMDS matrices.

5. Significance

Lightweight Cryptography: By providing direct constructions for NMDS matrices, the paper enables the design of diffusion layers that are more efficient in terms of hardware area and power consumption compared to MDS matrices, without sacrificing security guarantees.
Scalability: Direct constructions are essential for generating matrices of large orders where exhaustive search is computationally impossible. This work extends the ability to design secure ciphers for larger block sizes.
Implementation Efficiency: The construction of involutory matrices is particularly valuable for hardware implementations, as it allows the same circuitry to be used for both encryption and decryption, significantly reducing chip area.
Theoretical Expansion: The work broadens the theoretical design space for MDS/NMDS matrices by moving beyond standard Cauchy and Vandermonde constructions, utilizing the algebraic properties of symmetric polynomials and generalized exponents.

In conclusion, this paper bridges the gap between theoretical coding theory and practical cryptographic implementation by offering the first systematic, direct methods for constructing recursive and involutory NMDS matrices, thereby advancing the state-of-the-art in lightweight cryptography.