XOR count and block circulant MDS matrices over finite commutative rings

Abstract

Block circulant MDS matrices are used in the design of linear diffusion layers for lightweight cryptographic applications. Most of the work on construction of block circulant MDS matrices focused either on finite fields or $ GL(m, \mathbb{F}_2) $. The main objective of this paper is to extend the above study of block circulant MDS matrices to finite commutative rings. Additionally, we examine the behavior of the XOR count distribution under different reducible polynomials of equal degree over $ \mathbb{F}_2 $. We show that the determinant of a block circulant matrix over a ring can be expressed in a simple form. We construct $ 4 \times 4 $ and $ 8 \times 8 $ block circulant matrices over a ring. Furthermore, for non-negative integer $ l $, we identify the conditions under which a 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 an irreducible polynomial of degree $ m $. To facilitate efficient implementation, we analyze XOR distributions within specific rings, such as $ 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} $. Our calculations reveal distinct XOR distributions when utilizing two reducible polynomials of equal degree, with XOR count distributions 776 and 764, respectively. However, when using irreducible polynomials of the same degree, the XOR count distributions remain the same. This difference is advantageous for applications in lightweight cryptography.

Keywords

• mds matrix
• finite commutative ring
• circulant matrix
• block circulant matrix
• xor count
• diffusion layer