XOR count and block circulant MDS matrices over finite commutative rings

1.   Introduction

The linear diffusion layer is widely used in the design of symmetric-key cryptography. It takes a crucial part in providing resistance against differential and linear cryptanalysis. If all square submatrices of a linear diffusion matrix are non-singular, then it is called a Maximum Distance Separable (MDS) matrix, and in other words, a perfect diffusion matrix with optimal diffusion property is called an MDS matrix. A typical application is in the MixColumns operation of AES ^[8]. Furthermore, except for block ciphers, MDS matrices are also broadly used in many other ciphers, such as Maelstrom-0 ^[11], PHOTON ^[12], SHARK ^[23], and Gr$\phi$stl ^[10]. There are several approaches to constructing MDS matrices, which can be applied as diffusion layers for block ciphers and hash functions. The first method is based on the algebraic structures such as Cauchy, Vandermonde, and Hadamard matrices (cf.; ^[13,18,20]). The next efficient method to be used in constructing MDS matrices is based on recursive construction (see ^[18,24,27], for more details). Also, a brief survey of various theories in the construction of MDS matrices is provided in ^[15].

Circulant matrices have attracted significant attention for the efficient construction of MDS matrices. A circulant matrix is a unique type of matrix in which each row vector is a cyclic shift of the previous row vector, rotated one element to the right. In the diffusion layer, circulant matrices are utilized by the Advanced Encryption Standard (AES) ^[8]. The advantage of circulant matrices is that they can be fully described by just $n$ elements, instead of requiring storage of all $n^2$ elements. In the study of circulant MDS matrices over finite fields, significant contributions have been made, as referenced in ^[1,14,15,21]. Han et al. ^[16] introduced a special generalization called block circulant matrices with circulant blocks. The authors demonstrated that block circulant matrices can perform better than circulant matrices in the implementation of the InvMixColumn operations. In 2021, Cui et al. ^[4] demonstrated that a Galois field is a subclass of a commutative ring, suggesting the possibility of finding more cost-effective MDS matrices within commutative rings rather than Galois fields. Taking this into account, Ali et al. ^[2] provided key insights into circulant MDS matrices over finite commutative rings of characteristic 2 and proved several important results regarding the non-existence of certain circulant MDS matrices over rings.

Inspired by the work of Han et al. ^[16] and Cui et al. ^[4], in the present article, we first derive the expression for the determinant of block circulant matrices over a finite commutative ring of characteristic 2. It is known that block circulant matrices can produce more efficient MDS matrices compared to circulant matrices. Using this expression, we construct block circulant MDS matrices of order $4\times 4$ and $8\times 8$ over rings. Furthermore, we examine the work of Khoo et al. ^[9], where they proposed analyzing the number of XOR operations required to compute the multiplication of a fixed element. For more studies related to implementation and d-XOR count, see the references ^[7,19,25]. In 2015, Sim et al. ^[26] proved the following result about the XOR-count:

Theorem A. [26,Theorem 1] The total XOR-count for a field $GF(2^n)$ is

This theorem proved that the sum of XORs of the elements of the finite field is invariant under the change of an irreducible polynomial of the same degree. Further, Sarkar and Sim ^[25] studied the XOR-count distribution under different bases of a finite field and proved the following:

Theorem B. [25,Proposition 2] The total XOR-count of the elements in $GF(2^n)$ is

and it is invariant under the choice of basis.

In 2021, Kesarwani et al. ^[18] extended the study of XOR count over a local rings. Using this result, we explore the XOR count distributions for two rings associated with two distinct reducible polynomials of the same degree and compare their corresponding XOR distributions. We obtain distinct XOR count distributions, which increase the probability of finding lightweight MDS matrices.

The organization of the paper is as follows: In Section 2, we start by explaining important terms like MDS matrices, circulant matrices, and block circulant matrices. Then, we show some interesting results about circulant matrices over finite commutative rings. We even figure out how to find the determinant of a circulant matrix over a ring of characteristic 2. In Section 3, we prove one of the main results about block circulant matrices in which we calculate their determinants. We even show how to make special $4\times 4$ and $8\times 8$ block circulant MDS matrices over ring. Further, we find out the condition when a ring $\frac{\mathbb{Z}_2[x]}{\langle (f(x))^{2^l}\rangle}$ contains a copy of finite field of order $2^m$, where $m$ is the degree of irreducible polynomial $f(x)$, and by using this result, we prove some results on MDS matrices over the ring $\frac{\mathbb{F}_2[x]}{\langle(1+x+x^3+x^4+x^8)^{2^t}\rangle}.$ We start Section 4, from the definition of XOR count of a finite field, and then we calculate the XOR count distribution of two rings, $R_1 = \frac{\mathbb{F}_2[x]}{\langle (1+x^2+x^6)\rangle}$ and $R_2 = \frac{\mathbb{F}_2[x]}{\langle (1+x^4+x^6)\rangle }$. In the last section, we wrap our study with some examples of MDS matrices and their XOR counts.

2.   Preliminaries

Some notations used throughout the paper are presented as follows:

In this section, we discuss some useful definitions such as MDS code, MDS matrix, circulant matrix, block circulant matrix and some important results. Throughout our paper, $m, \; n, \; l, \; k, \; d, \; s,$ and $t$ are positive integers.

Definition 1. ^[6] A linear code $C(n, k)$ of length $n$ and dimension $k$ over $R$ with minimum Hamming distance $d$ satisfying $d = n - k + 1$ is said to be a maximal distance separable (MDS) code.

Definition 2. A matrix $M_{n\times n}$ is an $MDS$ matrix if and only if all its square submatrices are non-singular.

In 1997, Dong et al. ^[5] gave a matrix characterization of MDS codes over modules, which we state as follows:

Lemma 1. [5,Theorem 2.1] Let $C(n, k)$ be a linear code over $R$ with a parity check matrix $H$ of the form $H = (B|I_{n-k})$. Then, $C(n, k)$ is an MDS code if and only if the determinants of every $t\times t$ submatrix, $t \in \{1, 2, \dots, min\{k, n-k\}\}$ of $B$ is an element of $U(R)$.

Note that MDS matrices are perfect diffusion matrices with maximum branch number. A permutation layer with a good diffusion matrix in block cipher can improve the avalanche characteristics of the block cipher, which increases the cipher's resistance to differential and linear cryptanalysis ^[17]. The MDS matrices are extensively used in designing block ciphers and hash functions that provide security against differential and linear cryptanalysis.

Definition 3. Let $R$ be a ring and $b_{i} \in R$ for all $\; i = 0, \; 1, \dots, \; d-1$. Then, any $d\times d$ matrix of the form

is called a circulant matrix of order $d$, and it is denoted by $circ(b_{0}, b_{1}, b_{2}, \dots, b_{d-1})$.

Since a circulant matrix can also be written as a polynomial in some suitable permutation matrix, we have the following result:

Lemma 2. [22,page 290] Let $d\geq 1$ be a fixed integer. Then, any circulant matrix $B = circ(b_{0}, b_{1}, \dots, b_{d-1})$ of order $d$ can be written in the form

Lemma 3. [21,Theorem 3.1.1] Let $A$ be a matrix of order $d$ and $T = circ(0, 1, 0, \dots, 0)$ be a matrix of order $d$. Then, $A$ is a circulant if and only if $AT = TA$, where it follows that all circulant matrices of the same order commute.

Lemma 4. [2,Lemma 7] Let $B = circ(b_{0}, b_{1}, \dots, b_{2d-1})$ be a circulant matrix of order $2d$ where $b_{0}, b_{1}, \dots, b_{2d-1} \in R$. Then,

Definition 4. An $(s, t)$-block circulant matrix of order $st$ is a matrix of the form

where $A_{1}, A_{2}, A_{3}, \dots, A_{s}$ are square matrices of order $t$ and $bCirc(A_{1}, \dots, A_{s})$ represent a block circulant matrix.

It is clear that if $s = 1$ or $t = 1$, an $(s, t)$-block circulant degenerates to an ordinary circulant matrix. But a block circulant is not necessarily a circulant. For example, the matrix

is a block circulant matrix but fails to be a circulant if $a\neq d.$

Definition 5. Let $D = bCirc(A_{1}, A_{2}, \dots, A_{s})$ be an $(s, t)$-block circulant, if each block $A_{i}$ is a circulant, $D$ is called an $(s, t)$-block circulant with circulant blocks. The class of such types of matrices is denoted by $\mathcal{B}_{s, t}(R).$

For example, the matrix of type

is in $\mathcal{B}_{3, 2}(R).$

In ^[2], first and third authors calculated the determinant of the circulant matrix over a finite commutative ring of characteristic 2.

Lemma 5. [2,Proposition 10] Let $circ(b_{0}, b_{1}, \dots, b_{2^d-1})$ be a circulant matrix over $R$. Then,

Corollary 6. [2,Corollary 11] For any positive integer $d$, we have

3.   The main results

The significance of MDS matrices of order $2^d$ is paramount in the development of block ciphers and primarily owing to their ease of implementation. Our particular emphasis is directed towards matrices within $\mathcal{B}_{s, t}(R)$, with the underlying assumption that $s = 2^{d_1}$ and $t = 2^{d_2}$ throughout the subsequent sections, where $d, \; d_1$, and $d_2$ are positive integers.

Now, we state and prove the first main result of this paper:

Theorem 7. Let $D = \mathit{\text{bCirc}}(A_{1}, A_{2}, \dots, A_{s}) \in \mathcal{B}_{s, t}(R)$, where $A_{i} = \mathit{\text{Circ}}(a_{i, 1}, a_{i, 2}, \dots, a_{i, t})$, $1 \leq i \leq s$, $s = 2^{d_{1}}$, $t = 2^{d_{2}}$. Then,

for some $z, \; z_i \in N(R)$.

Proof. Let $D = bCirc(A_{1}, A_{2}, \dots, A_{s})$ be a block circulant matrix of order $st \times st$ over the ring $\mathcal{B}_{s, t}(R)$. In view of Lemmas 3 and 5, we have

and $A^t_{i} = \sum\limits_{j = 1}^{t} a^t_{i, j}I_t$.

Case (i): When $s > t$, $i.e.$, $d_{1} > d_{2}$. Then, we have

From Corollary 6, we obtain, $\det(A_i) = z_{i}+\sum\limits_{j = 1}^{t} a^t_{i, j}, \; \; \text{for some}\; z_{i}\in N(R).$ This gives,

Using Eq (3.2) in Eq (3.1), we obtain

This yields that,

The last relation gives

Thus, we obtain

and

Case (ii): When $s \leq t$, $i.e.$, $d_1 \leq d_2$. Then, we have

This implies that,

The above relation yields

This implies,

That is,

This completes the proof. □

As an application of Theorem 7, we derive the following results. Precisely, if we take finite field of characteristic 2 in Theorem 7, then we obtain

Corollary 8. [16,Theorem 4.4] Let $D = \mathit{\text{bCirc}}(A_{1}, A_{2}, \dots, A_{s}) \in \mathcal{B}_{s, t}(\mathbb{F}_{2^n})$, where $A_{i} = \mathit{\text{Circ}}(a_{i, 1}, a_{i, 2}, \dots, a_{i, t})$, $1 \leq i \leq s$, $s = 2^{d_{1}}$, $t = 2^{d_{2}}$. Then

and

In the following propositions, we construct $4\times 4$ and $8\times 8$ block circulant MDS matrices over the ring $\mathbb{F}_{2^8}\times \mathbb{F}_{2^8}$, where $h(x) = x^8+x^4+x^3+x+1$ is the generating polynomial of $\mathbb{F}_{2^8}$, $\alpha$ and $\beta$ are the roots of this generating polynomial, and $\overline{\gamma} = (\alpha, \; \beta)$, $\bar{\textbf{1}} = (1, 1)\in \mathbb{F}_{2^8}\times \mathbb{F}_{2^8}.$

Proposition 9. Let $\alpha$ and $\beta$ be the roots of the polynomial $h(x)$. Then, $D = bCirc(circ(\bar{\textbf{1}}, \; \bar{\gamma}), circ(\bar{\gamma}^{-1}, \; \bar{\gamma}+\bar{\textbf{1}}))\in \mathcal{B}_{2, 2}(\mathbb{F}_{2^8}\times \mathbb{F}_{2^8})$ is an MDS matrix, and $D^{-1} = \gamma^2D.$

Proof. Application of [16,Proposition 5.3], makes it clear that $D$ is an MDS matrix. By employing Theorem 7, we can write

where $A_1 = circ(\bar{\textbf{1}}, \; \bar{\gamma}), \; B = circ(\bar{\gamma}^{-1}, \; \bar{\gamma}+\bar{\textbf{1}}).$ By Corollary 2.6, we obtain $\det(A_1) = \bar{\gamma}^2+\bar{\textbf{1}}$ and $\det(A_2) = \bar{\gamma}^2+\bar{\textbf{1}}+(\bar{\gamma}^{-1})^2,$ and hence

□

Proposition 10. Let $\alpha$ and $\beta$ be the roots of the polynomial $h(x)$. Then, $D = bCirc(circ(\bar{\textbf{1}}, \; \bar{\textbf{1}}, \; \bar{\gamma}^{-1}+\bar{\gamma}, \; \bar{\gamma}), \; cir(\bar{\textbf{1}}+\bar{\gamma}+\bar{\gamma}^{-1}, \; \bar{\textbf{1}}+\bar{\gamma}, \; \bar{\gamma}^{-1}, \; \bar{\gamma}^{-1}+\bar{\gamma}))\in \mathcal{B}_{2, 4}(\mathbb{F}_{2^8}\times \mathbb{F}_{2^8})$ is an MDS matrix, and $D^{-1} = \gamma^{-4}D\times D^2.$

Proof. In view of [16,Proposition 5.4], we can easily see that $D$ is an MDS matrix. With the help of Theorem 7, we can write

where $A_1 = circ(\bar{\textbf{1}}, \; \bar{\textbf{1}}, \; \bar{\gamma}^{-1}+\bar{\gamma}, \; \bar{\gamma}), \; A_2 = cir(\bar{\textbf{1}}+\bar{\gamma}+\bar{\gamma}^{-1}, \; \bar{\textbf{1}}+\bar{\gamma}, \; \bar{\gamma}^{-1}, \; \bar{\gamma}^{-1}+\bar{\gamma}))$. Application of Corollary 6 yields, $\det(A_1) = {(\bar{\gamma}^{-1})}^2$ and $\det A_2 = {(\bar{\gamma}^{-1})}^2+{(\bar{\gamma})}^2$

This implies,

□

Proposition 11. Let $\alpha$ and $\beta$ be the roots of the polynomial $h(x)$. Then, $D = bCirc(circ(\bar{\textbf{1}}, \bar{\gamma}^{-1}), circ(\bar{\gamma}^{-1}+\bar{\textbf{1}}, \bar{\gamma}^{2}), circ(\bar{\gamma}, \bar{\gamma}^{-1}+\bar{\textbf{1}}), circ(\bar{\gamma}^{2}+\bar{\textbf{1}}, \bar{\textbf{1}}+\bar{\gamma}+\bar{\gamma}^{-1}))\in \mathcal{B}_{4, 2}(\mathbb{F}_{2^8}\times \mathbb{F}_{2^8})$ is an MDS matrix.

Proposition 12. Let $D = bCirc(circ(a_1, a_2), \; circ(a_3, a_4))$ be an MDS matrix over $R$. Then, $a_i\neq a_j+\eta \; (1\leq i, \; j\leq 4),$ for any $\eta\in N(R)$.

Proof. Since $D = bCirc(circ(a_1, a_2), \; circ(a_3, a_4))$. So, we have

Let us suppose on the contrary, $a_i = a_j+\eta,$ where $1\leq i, \; j\leq 4.$ Since $C = circ(a_i, \; a_j) = circ(a_i, \; a_i+\eta)$ is a submatrix of $D$, so $\det (C) = a^2_i+a^2_i+\eta^2 = \eta^2.$ This implies that $\det(C)\in N(R)$. Hence, we obtained a contradiction as $D$ is an MDS matrix. Therefore $a_i\neq a_j+\eta \; (1\leq i, \; j\leq 4),$ for any $\eta\in N(R).$ □

In the following lemma, we prove that the ring $\mathfrak{R}_l = \frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle}$ contains a finite field of order $2^m,$ where $f(x)$ is any irreducible polynomial of degree $m$.

Lemma 13. Let $f(x)$ be any irreducible polynomial of degree $m$ over $\mathbb{F}_2$ and $\mathfrak{R}_l = \frac{\mathbb{F}_2[x]}{\langle (f(x))^{2^l}\rangle}$ be a ring. Then, $\mathfrak{R}_l$ has a field of order $2^m.$

Proof. Let $f(x)$ be an irreducible polynomial of degree $m$ over $\mathbb{F}_2$. Now, we define a map $\phi: \frac{\mathbb{F}_2[x]}{\langle f(x)\rangle}\longrightarrow \frac{\mathbb{F}_2[x]}{\langle (f(x))^{2^l}\rangle}$ as $\phi(h(x)+\langle f(x)\rangle) = (h(x))^{2^l}+\langle (f(x))^{2^l}\rangle\; \text{for all} \; h(x)\in \mathbb{F}_2[x].$ First, we prove that $\phi$ is well defined. Let $h_1(x)+\langle f(x)\rangle\; \text{and}\; h_2(x)+\langle f(x)\rangle \in \frac{\mathbb{F}_2[x]}{\langle f(x)\rangle}$ such that $h_1(x)+\langle f(x)\rangle = h_2(x)+\langle f(x)\rangle.$ This implies that $h_1(x)-h_2(x)\in \langle f(x)\rangle$, that is, $h_1(x)-h_2(x) = g(x)\cdot f(x)\; \text{for some} \; g(x)\in\mathbb{F}_2[x]$. Therefore, we write $(h_1(x)-h_2(x))^{2^l} = (g(x)\cdot f(x))^{2^l},$ that is, $(h_1(x)-h_2(x))^{2^l} = (g(x))^{2^l}(f(x))^{2^l} = 0 \mod (f(x))^{2^l}$. Hence, $\phi(h_1(x)+\langle f(x)\rangle) = \phi (h_2(x)+\langle f(x)\rangle)$.

Next, we want to prove that $\phi$ is a ring homomorphism. For any $h_1(x)+\langle f(x)\rangle, \; h_2(x)+\langle f(x)\rangle \in \frac{\mathbb{F}_2[x]}{\langle f(x)\rangle}$, we have

Also, we have

Hence, $\phi$ is a ring homomorphism. To show that $\phi$ is an embedding, we prove that $\phi$ is injective. Let $h(x) + \langle f(x) \rangle \in \text{Ker}(\phi)$. Therefore, we have $\phi(h(x)+\langle f(x)\rangle) = \langle (f(x))^{2^l}\rangle,$ which implies $(h(x))^{2^l} + \langle (f(x))^{2^l}\rangle = \langle (f(x))^{2^l}\rangle.$ Thus, $(h(x))^{2^l} \in \langle (f(x))^{2^l} \rangle$, $f(x) \mid h(x)$. That is, $h(x) + \langle f(x) \rangle = \langle f(x) \rangle$. Henceforth, we conclude that $\text{Ker}(\phi) = \{ \langle f(x) \rangle \}$.

Thus, $\phi$ is injective. Hence, $\frac{\mathbb{F}_2[x]}{\langle (f(x))^{2^l}\rangle}$ contains a field of order $2^m$ which is isomorphic to $\frac{\mathbb{F}_2[x]}{\langle f(x)\rangle}$. □

Lemma 14. Let $\psi: M\Bigg(d, \frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle }\Bigg)\longrightarrow M\Bigg(d, \frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle }\Bigg)$ be a map, for any $A = (a_{i, j})\in$ $M\Bigg(d, \frac{\mathbb{F}_2[x]}{\langle((f(x))^{2^l}\rangle }\Bigg)$ define $\psi$ as $\psi((a_{ij})) = (a_{ij}+\eta_{ij}) = A'$, where $\eta_{ij} \in N\Big(\frac{\mathbb{F}_2[x]}{\langle (f(x))^{2^l}\rangle}\Big)$ for $1\leq i, \; j\leq d$. Then, $A$ is invertible if and only if $A'$ is invertible.

Proof. Let

be an invertible matrix. Since,

be a map defined by $\psi((a_{ij})) = (a_{ij} + \eta_{ij}) = A'$. That is,

We now prove that $A'$ is invertible in $M\Bigg(d, \frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle}\Bigg)$. For this, we calculate the determinant of $A'$ as

where

Since $A$ is invertible, $\det(A)$ is a unit in $\frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle}$. Therefore, $\det(A') = \det(A) + t$, where $t \in N\Bigg(\frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle}\Bigg)$, which implies that $\det(A')$ is also a unit element in $\frac{\mathbb{F}_2[x]}{\langle(f(x))^{2^l}\rangle}$. Hence, $A'$ is invertible.

Similarly, we can prove the converse of this theorem. □

Theorem 15. Let $A = (a_{ij})\in GL\Bigg(d, \frac{\mathbb{F}_2[x]}{\langle((f(x))^{2^l}\rangle }\Bigg)$ be an MDS matrix, and $\eta_{ij} \in N\Big(\frac{\mathbb{F}_2[x]}{\langle (f(x))^{2^l}\rangle}\Big)$. Then, $A' = (a_{ij}+\eta_{ij})$ is an MDS matrix.

Proof. The proof of this theorem directly follows from Lemma 14. □

Theorem 16. Let $\mathcal{R}_t = \frac{\mathbb{F}_2[x]}{\langle(1+x+x^3+x^4+x^8)^{2^t}\rangle}$ be a ring with a positive integer $t$ and $\beta$ be a root of the irreducible polynomial $1+x+x^3+x^4+x^8,$ and $\alpha = \beta^{2^t}$. Then, $D = bCirc(circ(1+\eta_1, \alpha+\eta_2), \; circ(\alpha^{-1}+\eta_3, \alpha+1+\eta_4))$ is an MDS matrix, where $\eta_1, \eta_2, \eta_3\; and\; \eta_4\in N(\mathcal{R}_t).$

Proof. The proof of this theorem follows from Lemma 13 and Theorem 15. □

Corollary 17. In particular, if we take $\eta_1 = \eta_2 = \eta_3 = \eta_4 = \eta$ in Theorem 16, then $D^2 = \frac{1}{\alpha^2}I_4.$

Proof. We have

□

Theorem 18. Let $\mathcal{R}_t = \frac{\mathbb{F}_2[x]}{\langle(1+x+x^3+x^4+x^8)^{2^t}\rangle}$ be a ring and $\beta$ be a root of the irreducible polynomial $1+x+x^3+x^4+x^8$, and $\alpha = \beta^{2^t}$. Then, $D = bCirc(circ(1+\eta_1, 1+\eta_2, \alpha+\alpha^{-1}+\eta_3, \alpha+\eta_4), circ(1+\alpha+\alpha^{-1}+\eta'_1, \; 1+\alpha+\eta'_2, \; \alpha^{-1}+\eta'_3, \; \alpha+\alpha^{-1}+\eta'_4))$ is an MDS matrix, where $\eta_1, \eta_2, \eta_3, \; \eta_4, \; \eta'_1, \eta'_2, \; \eta'_3\; and\; \eta'_4\in N(\mathcal{R}_t).$

Proof. The proof of this theorem is on similar lines as that of Lemma 13 and Theorem 15. □

Corollary 19. If we take $\eta_1 = \eta_2 = \eta_3 = \eta_4 = \eta'_1 = \eta'_2 = \eta'_3 = \eta'_4$ in Theorem 72, then $D^4 = (\alpha^4+z)I,$ for some $z\in N(\mathcal{R}_t).$

4.   XOR count distribution of finite commutative rings of characteristic 2

In this section, we delve into the XOR count distribution for elements within two rings: $R_1 = \frac{\mathbb{F}_2[x]}{\langle (1+x^2+x^6)\rangle}$ and $R_2 = \frac{\mathbb{F}_2[x]}{\langle (1+x^4+x^6)\rangle}$. Employing a method delineated by Kesarwani et al. ^[18], which entails determining the XOR count of a local ring with characteristic 2. We apply the same method in finite fields to define the XOR count for elements within $R_1$ and $R_2$. For a more comprehensive understanding of XOR count, readers are encouraged to delve into the detailed discussions provided in ^[19]. Let us commence this section by outlining the definition of XOR count.

Definition 6. [25,Definition 1] The XOR count of an element $\theta$ in the field $\mathbb{F}_{2^n}$ is the number of XORs required to implement the multiplication of $\theta$ with an arbitrary element $\beta$. XOR counts of all elements of $\mathbb{F}_{2^n}$ referred to as the XOR count distribution.

We begin by outlining the procedure for computing the number of XOR operations needed to execute a multiplication by elements $\alpha^3$ within the finite rings $R_1$ and $R_2.$

For ring $R_1 = \frac{\mathbb{F}_2[x]}{\langle (1+x^2+x^6)\rangle} = \{a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3+a_4\alpha^4+a_5\alpha^5;\; where\; \alpha = x+\langle 1+x^2+x^6\rangle, \; a_i\in \mathbb{F}_2\}.$ Consider the multiplication of $\alpha^3$ with an arbitrary element $\beta = b_0+b_1\alpha+b_2\alpha^2+b_3\alpha^3+b_4\alpha^4+b_5\alpha^5$, where $b_i \in \mathbb{F}_2,$ as

The product of $\alpha^3$ and $\beta$ can be expressed as

where there are three XOR operations. Consequently, the XOR count of the element $\alpha^3$ in $R_1$ is 3.

For the ring $R_2 = \frac{\mathbb{F}_2[x]}{\langle (1+x^4+x^6)\rangle } = \{a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3+a_4\alpha^4+a_5\alpha^5;\; where\; \alpha = x+\langle 1+x^4+x^6\rangle, \; a_i\in \mathbb{F}_2\}.$ Consider the multiplication of $\alpha^3$ with an arbitrary element $\beta = b_0+b_1\alpha+b_2\alpha^2+b_3\alpha^3+b_4\alpha^4+b_5\alpha^5$, where $b_i \in \mathbb{F}_2$ as

The product of $\alpha^3$ and $\beta$ takes the form

which contains four XORs. Hence, the XOR count for the element $\alpha^3$ in $R_2$ is 4.

Then, we can calculate the number of XORs required for the multiplication of each element in rings $R_1$ and $R_2$ by using the same approach. Table 1 shows the number of XOR gates for each elements of the finite rings of order $2^6$ defined by two reducible polynomials $(1+x^2+x^6)$ and $(1+x^4+x^6)$. The Magma computation system ^[3] is used to complete all of the computations in Table 1.

In Table 1, we observe that the sum of all XOR distributions of the elements in $R_1$ and $R_2$ amounts to 776 and 764, respectively. Our investigation aligns with the findings of Sarkar and Sim ^[25] in the realm of finite fields, where they demonstrate that there is no advantage in varying the choice of irreducible polynomials over $\mathbb{F}_{2}$. They proved that the total XOR count of elements in $\mathbb{F}_{2^n}$ remains constant, $i.e.$, $n\sum\limits_{i = 2}^{n}\binom{n}{i}(i-1)$. However, our exploration reveals a contrasting scenario: When employing two reducible polynomials of equal degree, distinct XOR distributions emerge. Specifically, in our investigation, we observe the XOR sums for the respective rings $R_1$ and $R_2$ to be 776 and 764.

5.   Examples

In this section, we present two examples of block circulant MDS matrices over the rings $R_1$ and $R_2$. Moreover, in connection with Theorem 15, we provide some additional MDS matrices.

Example 1. Let $R_1 = \frac{\mathbb{F}_2[x]}{ (\langle 1+x^2+x^6 \rangle)}$ be a finite commutative ring of characteristic 2. By Lemma 13, we can say that $R_1$ contains a finite field of order 8. Let $\alpha$ be the root of the irreducible polynomial $1+x+x^3$ over $\mathbb{F}_2$, and the matrix $A = bCirc(circ(1, \; \alpha), \; circ(1+\alpha, \; 1+\alpha^2)).$ That is,

is an MDS matrix, and $A^2 = (1+\alpha^4)I_4$. In Theorem 15, if we take $\eta_{ij} = \alpha^3+\alpha+1$ and $\eta'_{ij} = \alpha^5+\alpha^4+1$, then we obtain two more MDS matrices $A_1$ and $A_2$, as follows:

Example 2. Let $R_2 = \frac{\mathbb{F}_2[x]}{ (\langle 1+x^4+x^6 \rangle)}$ be a finite commutative ring of characteristic 2. In view of Lemma 13, we can say that $R_2$ contains a finite field of order 8. Let $\alpha$ be a root of the irreducible polynomial $1+x+x^3$. Then, the matrix

is an MDS matrix, and $A^2 = \alpha^4I_4$. Moreover, if we take $\eta_{ij} = \alpha^3+\alpha^2+1$ and $\eta'_{ij} = \alpha^5+\alpha+1$, in Theorem 15, then we obtain two MDS matrices $B_1$ and $B_2$. That is, we obtain

and

5.1.   XOR count of a matrix over finite commutative ring of characteristic 2

The XOR count of one row of a diffusion matrix can be computed using the following formula.

where $\gamma_i$ is the XOR count of the $i$-th entry in the row of the matrix, $k$ is the order of the diffusion matrix, $l$ is the number of nonzero coefficients in the row, and $n$ is the dimension of vector space (see, ^[25] for more details).

Remark 1. Using Eq (5.1) and Table 1, we calculate the XOR counts of matrices $A$, $A_1$, and $A_2$ in Example 1 to be 132, 212, and 264, respectively.

Remark 2. By employing Eq (5.1) and referring to Table 1, we compute the XOR counts for matrices $B$, $B_1$, and $B_2$ in Example 2 as 108, 256, and 256, respectively.

6.   Conclusions

In this paper, we studied the construction of block circulant MDS matrices over finite commutative rings with unity. Our investigation has delved into the determinant of such matrices, extending previous findings from finite fields to the ring $R$. Additionally, we explored conditions under which $R$ contains a finite field of order $2^m$, taking advantage of this discovery, we constructed block circulant MDS matrices of orders 4 and 8. To enhance the practical implementation of MDS matrices, we analyzed the XOR distribution within specific rings, including $R_1 = \frac{\mathbb{F}_2[x]}{\langle (1+x^2+x^6)\rangle}$ and $R_2 = \frac{\mathbb{F}_2[x]}{\langle (1+x^4+x^6)\rangle }$, providing the XOR counts distribution of these two rings. Furthermore, we presented some examples of MDS matrices alongside their corresponding XOR counts within the framework of finite commutative rings.

However, unlike previous research, our investigation has found that different XOR patterns appear when we use two reducible polynomials of the same degree. We specifically noticed different XOR distributions of rings $R_1$ and $R_2$, which are 776 and 764, respectively. This finding emphasizes how the choice of polynomials influences the way XOR behaves in specific mathematical scenarios involving certain types of rings. Our investigation has aligned with previous findings in the realm of finite fields, where they (cf.; ^[25]) demonstrated that there is no advantage in varying the choice of irreducible polynomials within $\mathbb{F}_{2^n}$, as they (cf.; ^[25]) proved that the total XOR count of elements in $\mathbb{F}_{2^n}$ remains constant.

The future work revolves around investigating the XOR count, particularly in relation to changes in the basis. We aim to determine whether altering the basis results in any modifications to the XOR distribution. Additionally, we seek to identify the conditions under which there is no variation in the XOR count distribution, particularly concerning reducible polynomials.

Author contributions

All authors have equally contributed. All authors have read and approved the final version of the manuscript for publication.

Acknowledgments

The authors thank to the anonymous reviewers for their valuable suggestions and comments which significantly improved both the quality and the presentation of this paper.

The authors extend their appreciation to Princess Nourah bint Abdulrahman University (PNU), Riyadh, Saudi Arabia, for funding this research under Researchers Supporting Project Number (PNURSP2024R231). A Substantial part of this work was done when the first and third authors were visiting Professor/Scientist at Department of Mathematics, Universitas Gadjah Mada (UGM), Indonesia (July, 2024) hosted by the Algebra Society of Indonesia and UGM. The first and third authors appreciate the gracious hospitality they received at UGM, Indonesia, during their visit. The research of the third author is financially supported by the University Grants Commission (UGC), Government of India (Ref. No.: 221610203798).

Conflicts of interest

The authors declare that they have no conflicts of interest.