Skip to content
Open access

On the Generalization of g-Circulant Matrices for Cryptographic MDS Matrix Construction

2026 · IEEE Access · Vol 14, pp. 167942-167958 · 0 citations · 26 references

TL;DR

This paper generalizes circulant-type matrices over a finite field using the quotient rings to establish conditions related to their MDS, involutory, and semi-involutory properties and studies their invertibility, MDS, and involutory properties.

Abstract

Maximum distance separable (MDS) matrices are widely used as linear diffusion layers in symmetric-key cryptography because of their optimal branch number. In this paper, we generalize circulant-type matrices over a finite field <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula> using the quotient rings <inline-formula> <tex-math notation="LaTeX">$\frac {\mathbb {F}_{q}[x]}{\langle x^{k}-\lambda \rangle }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\frac {\mathbb {F}_{q}[x;\theta]}{\langle x^{k}-\lambda \rangle }$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\lambda \in \mathbb {F}_{q}^{*}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\theta :\mathbb {F}_{q}\rightarrow \mathbb {F}_{q}$ </tex-math></inline-formula> is a field automorphism. Using the first quotient ring, we introduce consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices, which generalize circulant and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices. We study their invertibility, MDS, and involutory properties and give an explicit formula for the number of invertible consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices. This formula reduces the search space for MDS testing, as shown in Table 3. The second quotient ring allows us to define consta-<inline-formula> <tex-math notation="LaTeX">$\theta _{g}$ </tex-math></inline-formula>-circulant matrices, extending <inline-formula> <tex-math notation="LaTeX">$\theta $ </tex-math></inline-formula>-circulant matrices through the parameters <inline-formula> <tex-math notation="LaTeX">$\lambda $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>. We establish conditions related to their MDS, involutory, and semi-involutory properties. Over finite fields of characteristic 2, suitable Hadamard powers preserve these properties. Table 6 gives an exhaustive comparison for matrices of order 4 over <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{7}$ </tex-math></inline-formula>. Among 2401 matrices for each fixed pair <inline-formula> <tex-math notation="LaTeX">$(\lambda,g)$ </tex-math></inline-formula>, no MDS matrix is obtained for <inline-formula> <tex-math notation="LaTeX">$(1,1)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$(1,3)$ </tex-math></inline-formula>, whereas 48 MDS matrices are obtained for each of <inline-formula> <tex-math notation="LaTeX">$(6,1)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$(6,3)$ </tex-math></inline-formula>. Thus, <inline-formula> <tex-math notation="LaTeX">$\lambda \neq 1$ </tex-math></inline-formula> produces MDS matrices not obtained in the circulant and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant cases with <inline-formula> <tex-math notation="LaTeX">$\lambda =1$ </tex-math></inline-formula>. This paper concludes with two open problems on orthogonal and involutory consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant MDS matrices over finite fields of characteristic 2.

Read PDF

Similar papers

Open access Oct 2026

Singer-Difference-Set Qudit Stabilizer Codes From Non-Degenerate Quadrics in PG(d, q): Construction, Structural Theorems, and Monte-Carlo Performance

We propose <inline-formula> <tex-math notation="LaTeX">$\mathcal {Q}(q,d)$ </tex-math></inline-formula>, a new family of <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>-ary non-CSS qudit stabilizer codes parameterised by a prime power <inline-formula> <tex-math notation="LaTeX...

Michel Kulhandjian, L. Hanzo · 0 citations
Open access 2026

New Lower Bounds for Weak Superimposed Codes

A new general lower bound on the largest code rate of weak superimposed codes for all integers is derived by improving the best known lower bound on the largest asymptotic code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula> by the Lovász local lemma.

Jin-Ping Fan, Yu-Jie Gu, Y. Miao · 0 citations
Open access 2026

Hardware-Efficient 5 × 5 S-Boxes With Strong Cryptographic Criteria for Lightweight Cryptography

Substitution boxes (S-Boxes) are essential nonlinear components in cryptography. This work presents a randomized, coordinate-function-first framework for constructing and selecting <inline-formula> <tex-math notation="LaTeX">$5\times 5$ </tex-math></inline-formula> S-Boxes. Balance is imposed by construction at the Boo...

Quang-Huy Tran, Thi-Bac Do, T. Dương et al. · 0 citations
Preprint Oct 2026

Statistics of entries of matrices from the general linear group over a finite field

Let $\mathrm{GL}_n(\mathbb{F}_q)$ be the group of $n\times n$ invertible matrices over a finite field $\mathbb{F}_q$. How many matrices in $\mathrm{GL}_n(\mathbb{F}_q)$ are there with a subset of their entries prescribed? Motivated by the random matrix theory of classical compact groups, we address this question and va...

Ofir Gorodetsky · 0 citations
Preprint Nov 2026

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{\Omega(\sqrt{k})}$. This improves on the prior best lower bound of $2^{\Omega(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction o...

Oliver Janzer, P. Manohar · 1 citation
Preprint Oct 2026

Multiplying matrices via polynomials: exposition and barriers

We give an exposition of OpenAI's recent proof that the exponent $\omega_\mathbb{C}$ of matrix multiplication over the complex numbers satisfies $\omega_\mathbb{C}\leq9/4$. Our version of the proof gives $\omega_\mathbb{F}\leq9/4$ over every field $\mathbb{F}$. We also treat the rectangular matrix multiplication expone...

A. Amanov, Maxim van den Berg, Jeroen Zuiddam · 4 citations · ⚡2

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.