🔢 mathematics

MDS matrices from skew polynomials with automorphisms and derivations

This paper presents a novel construction of Maximum Distance Separable (MDS) matrices using skew polynomial rings with automorphisms and derivations, introducing $\delta_\theta$ -circulant matrices and deriving necessary and sufficient conditions for them to be involutory and MDS, while also providing quasi-recursive MDS matrices that improve upon previous quasi-involutory results.

Original authors: Atif Ahmad Khan, Shakir Ali, Elif Segah Oztas, Abhishek Kesarwani

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Atif Ahmad Khan, Shakir Ali, Elif Segah Oztas, Abhishek Kesarwani

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

The Big Picture: Building Better Digital Locks

Imagine you are building a digital safe. To make it secure, you need two main things:

Confusion: Making the relationship between your password and the locked safe look like a random mess.
Diffusion: Making sure that if you change even one tiny bit of your password, the entire safe changes completely.

In the world of cryptography (digital security), MDS matrices are the special tools used to create this "diffusion." Think of an MDS matrix as a super-mixer. If you pour a drop of red ink (a piece of data) into a bucket of water (the matrix), a perfect MDS matrix ensures that the red color spreads evenly to every single drop in the bucket. If the mixing isn't perfect, some drops stay clear, and hackers can find patterns to break the lock.

This paper is about inventing new, better mixing tools using a specific type of mathematical "kitchen" called Skew Polynomial Rings.

The Ingredients: A Twist on Standard Math

Usually, mathematicians build these mixing tools using standard polynomial rings (like $x^2 + 2x + 1$ ). But the authors decided to use a "twisted" version called Skew Polynomials.

To understand the twist, imagine a standard recipe where you mix ingredients in a specific order. In this paper's "twisted" kitchen, the order matters even more because of two special rules:

The Automorphism ( $\theta$ ): Imagine a magical chef who changes the flavor of an ingredient before you mix it. If you have an apple, the chef might turn it into a pear before you put it in the bowl.
The Derivation ( $\delta$ ): Imagine a second rule where, as you mix, a little bit of "extra sauce" is added based on the ingredients.

The authors combined these two rules to create a new type of mixing tool called a $\delta\theta$ -circulant matrix.

The Analogy: Think of a standard "circulant" matrix as a conveyor belt where a pattern just slides to the right. The new $\delta\theta$ -circulant matrix is like a conveyor belt where, as the pattern slides, the items also get transformed by the "magical chef" and get a splash of "extra sauce."

The First Discovery: New Mixing Patterns

The authors showed that by using these twisted rules, they could build new mixing matrices that were previously impossible to make.

The Goal: They wanted matrices that are MDS (perfect mixers) and Involutory (self-reversing).
The "Self-Reversing" Analogy: Imagine a magic mirror. If you look in it, you see yourself. If you look in it again, you still see yourself. In math, an "involutory" matrix is a tool that, if you use it to scramble data and then use it again, the data goes back to normal. This is incredibly useful for encryption because it saves time and energy; you don't need a separate "unscrambler" tool.

The paper proves that by carefully choosing the "chef" and the "sauce," they can create these perfect, self-reversing mixers. This is a big deal because, in the old "standard" kitchen, it was very hard (sometimes impossible) to make these specific types of perfect mixers.

The Second Discovery: The "Quasi-Recursive" Machine

The second part of the paper focuses on a different kind of mixing tool called Quasi Recursive MDS matrices.

The Analogy: Imagine a machine that takes a shape, stamps it, then stamps the result again, and again.
The Innovation: The authors built a machine where the "stamping" process is so efficient that if you run the machine a specific number of times, the final result is not just a good mixer, but a perfect, self-reversing mixer.

Previously, other researchers had built machines that were "almost" self-reversing (called quasi-involutory). The authors of this paper improved the design so that the machine is strictly self-reversing. This is like upgrading a car engine from "almost getting 50 miles per gallon" to "getting exactly 50 miles per gallon." It's a strict improvement in efficiency.

How They Did It: The "Hadamard" Trick

Towards the end, the paper introduces a clever trick called the Hadamard product.

The Analogy: Imagine you have a perfect recipe for a cake. The authors found a way to take that recipe and "squirt" a special spice into every single ingredient individually.
The Result: They proved that if you take a known good mixing recipe and apply this "spice" (the Hadamard product), you instantly get many new, different, but equally perfect mixing recipes. This gives engineers a huge toolbox of options to choose from, rather than being stuck with just one or two.

Summary of What They Claim

New Tools: They created a new family of mixing matrices ( $\delta\theta$ -circulant) using a twisted mathematical framework.
Self-Reversing: They proved these new tools can be "self-reversing" (involutory), which makes them faster and cheaper to use in encryption.
Better than Before: Their method for making "quasi recursive" matrices produces strictly self-reversing results, improving upon previous methods that were only "almost" self-reversing.
Multiplying Options: They showed how to use a specific mathematical operation (Hadamard product) to generate many new valid matrices from just one good example.

What they did not claim:
The paper does not claim to have built a specific new encryption software, nor does it claim these tools are currently being used in commercial products. It is a theoretical math paper that provides the blueprints and proofs that these new, efficient tools exist and can be built. They leave the actual construction of specific security systems for future work.

Technical Summary: MDS Matrices from Skew Polynomials with Automorphisms and Derivations

Problem Statement
Maximum Distance Separable (MDS) matrices are fundamental to the design of diffusion layers in symmetric-key cryptography, providing optimal resistance against differential and linear cryptanalysis. While circulant and recursive MDS matrices are widely studied due to their efficient algebraic descriptions and implementation properties, existing constructions often face limitations. Specifically, classical circulant matrices of even order cannot be simultaneously MDS and involutory (self-inverse), a property highly desirable for reducing implementation costs in cryptographic primitives. Previous generalizations using skew polynomial rings with automorphisms ( $\theta$ -circulant matrices) have addressed some of these issues but often remain confined to specific finite fields or yield only quasi-involutory matrices. Furthermore, the incorporation of derivations into these algebraic structures to further generalize the class of constructible MDS matrices has not been fully explored.

Methodology
The authors develop their constructions within the framework of skew polynomial rings $F_q[X; \theta, \delta]$ , where $F_q$ is a finite field, $\theta$ is an automorphism of $F_q$ , and $\delta$ is a $\theta$ -derivation. The multiplication in this non-commutative ring is defined by the rule $Xa = \theta(a)X + \delta(a)$ .

The paper proceeds through the following methodological steps:

Definition of $\delta\theta$ -Circulant Matrices: The authors introduce a new class of structured matrices, termed $\delta\theta$ -circulant matrices, which generalize classical and $\theta$ -circulant matrices by incorporating the $\theta$ -derivation $\delta$ . The structure of these matrices is analyzed via their association with linear transformations on the quotient ring $F_q[X; \theta, \delta] / \langle X^m - 1 \rangle$ .
Algebraic Characterization: Necessary and sufficient conditions are derived for these matrices to satisfy the MDS property and the involutory property ( $A^2 = I$ ). This involves analyzing the weight of polynomials in the skew ring and the relationship between the generating polynomial and the resulting matrix.
Quasi Recursive Constructions: The study extends to quasi recursive MDS matrices, defined via a specific product of matrices involving powers of the automorphism and derivation. The authors focus on companion matrices associated with monic skew polynomials.
Hadamard Product Application: The paper utilizes the Hadamard product of polynomials to generate new families of MDS matrices from existing ones, preserving the MDS property under specific conditions.

Key Contributions and Results

$\delta\theta$ -Circulant Matrices:
- The paper defines $\delta\theta$ -circulant matrices and establishes a correspondence between these matrices and linear transformations in the skew polynomial ring.
- Theorem 2 provides a necessary and sufficient condition for a $\delta\theta$ -circulant matrix to be MDS: for any non-zero polynomial $Q_1(X)$ , the sum of the weights of $Q_1(X)$ and $Q_1(X)h(X) \pmod{X^m-1}$ must be at least $m+1$ .
- Theorem 3 establishes the condition for a $\delta\theta$ -circulant matrix to be involutory, linking it to the product of the generating polynomial and its inverse in the skew ring.
- The authors note that while $\theta$ -circulant matrices (where $\delta=0$ ) can yield involutory MDS matrices of even order, the introduction of $\delta$ expands the class of constructible matrices.
Quasi Recursive Involutory MDS Matrices:
- A central contribution is the construction of quasi recursive MDS matrices that are strictly involutory (not just quasi-involutory).
- Theorem 5 demonstrates that for a specific choice of automorphism $\theta(a) = a^{q^2}$ and a polynomial $g(X)$ generating an MDS code, the resulting quasi recursive matrix $N_g$ satisfies $N_g^2 = I_m$ . This represents a strict improvement over previous results (e.g., Cauchois et al. [15]) which produced quasi-involutory matrices confined to restricted field classes.
- Theorem 6 extends the criterion for recursive MDS matrices to the quasi recursive setting, relating the MDS property to the weight of right multiples of the generating polynomial.
Generation of New Matrices:
- Theorem 8 shows that if a polynomial $g(X)$ yields a quasi recursive MDS matrix, then its Hadamard power $(g(X))^{\diamond 2t}$ also yields a quasi recursive MDS matrix. This allows for the generation of multiple new MDS matrices from a single seed polynomial.
- Theorem 7 establishes that the reciprocal polynomial of a generator for involutory MDS matrices also generates involutory MDS matrices.

Significance and Claims
The paper claims that its primary significance lies in the generalization of existing MDS matrix constructions through the inclusion of $\theta$ -derivations. Specifically:

It introduces $\delta\theta$ -circulant matrices as a broader class than $\theta$ -circulant matrices, offering a unified algebraic setting for both circulant and recursive structures.
It provides a construction for involutory quasi recursive MDS matrices of even order, addressing a limitation in prior literature where such matrices were either non-existent in the classical setting or only quasi-involutory in the skew setting. This is significant for cryptographic efficiency, as involutory matrices eliminate the need for separate inverse implementations.
The work offers explicit criteria for the MDS and involutory properties, facilitating the systematic construction of such matrices.

The authors acknowledge that a complete characterization of MDS $\delta\theta$ -circulant matrices remains an open problem, particularly when the parameter $\beta$ (defining the derivation) does not lie in the fixed field of the automorphism. They also pose the question of whether these matrices possess orthogonality properties as a direction for future work.