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.
Citation: Shakir Ali, Amal S. Alali, Atif Ahmad Khan, Indah Emilia Wijayanti, Kok Bin Wong. XOR count and block circulant MDS matrices over finite commutative rings[J]. AIMS Mathematics, 2024, 9(11): 30529-30547. doi: 10.3934/math.20241474
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.
[1] | I. Adhiguna, I. S. N. Arifin, F. Yuliawan, I. Muchtadi-Alamsyah, On orthogonal circulant MDS matrices, Int. J. Math. Comput. Sci., 17 (2022), 1619–1637. |
[2] | S. Ali, A. A. Khan, B. Singh, On circulant involutory and orthogonal MDS matrices over finite commutative rings, Appl. Algebr. Eng. Comm., 2024. https://doi.org/10.1007/s00200-024-00656-4 |
[3] | W. Bosma, J. Cannon, Handbook of Magma functions, University of Sydney, 1995. |
[4] | T. Cui, S. Chen, C. Jin, H. Zheng, Construction of higher-level MDS matrices in nested SPNs, Inform. Sciences, 554 (2021), 297–312. https://doi.org/10.1016/j.ins.2020.12.022 doi: 10.1016/j.ins.2020.12.022 |
[5] | X. D. Dong, C. B. Son, E. Gunawan, Matrix characterization of MDS linear codes over modules, Linear Algebr. Appl., 277 (1998), 57–61. https://doi.org/10.1016/S0024-3795(97)10073-8 doi: 10.1016/S0024-3795(97)10073-8 |
[6] | S. T. Dougherty, Algebraic coding theory over finite commutative rings, Springer, 2017. |
[7] | J. Jean, T. Peyrin, S. M. Sim, J. Tourteaux, Optimizing implementations of lightweight building blocks, IACR T. Symmetric Cry., 4 (2017), 130–168. https://doi.org/10.46586/tosc.v2017.i4.130-168 doi: 10.46586/tosc.v2017.i4.130-168 |
[8] | D. Joan, V. Rijmen, The design of Rijndael: AES-the advanced encryption standard, Inform. Secur. Cryptogr., 2002. |
[9] | K. Khoo, T. Peyrin, A. Y. Poschmann, H. Yap, FOAM: Searching for hardware optimal SPN structures and components with a fair comparison, Springer, Berlin, Heidelberg, 16 (2014), 433–450. https://doi.org/10.1007/978-3-662-44709-3_24 |
[10] | P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schl$\ddot{a}$ffer, et al., Gr$\phi$stl-a SHA-3 candidate, In: Dagstuhl Seminar Proceedings, Schloss Dagstuhl-Leibniz-Zentrum f$\ddot{u}$r Informatik, 2009. |
[11] | F. D. Gazzoni, P. Barreto, V. Rijmen, The Maelstrom-0 hash function, In VI Brazilian Symposium on Information and Computer Systems Security, 2006. |
[12] | J. Guo, T. Peyrin, A. Poschmann, The PHOTON family of lightweight hash functions, Adv. Cry.-CRYPTO, 6841 (2011), 222–239. https://doi.org/10.1007/978-3-642-22792-9_13 doi: 10.1007/978-3-642-22792-9_13 |
[13] | K. C. Gupta, I. G. Ray, On constructions of involutory MDS matrices, In Progress in Cryptology AFRICACRYPT, LNCS, Springer, Berlin, Heidelberg, 7918 (2013), 43–60. https://doi.org/10.1007/978-3-642-38553-7_3 |
[14] | K. C. Gupta, I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptogr. Commun., 7 (2014), 257–287. https://doi.org/10.1007/s12095-014-0116-3 doi: 10.1007/s12095-014-0116-3 |
[15] | K. C. Gupta, S. K. Pandey, I. G. Ray, S. Samanta, Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results, Adv. Math. Commun., 13 (2019), 779–843. https://doi.org/10.3934/amc.2019045 doi: 10.3934/amc.2019045 |
[16] | H. Han, C. Tang, Y. Lou, M. Xu, Construction of efficient MDS matrices based on block circulant matrices for lightweight application, Fund. Inform., 145 (2016), 111–124. |
[17] | H. M. Heys, S. E. Tavares, The design of substitution-permutation networks resistant to differential and linear cryptanalysis, In Proceedings of the 2nd ACM Conference on Computer and Communications Security, 1994,148–155. |
[18] | A. Kesarwani, S. Pandey, S. Sarkar, A. Venkateswarlu, Recursive MDS matrices over finite commutative rings, Discrete Appl. Math., 304 (2021), 384–396. https://doi.org/10.1016/j.dam.2021.08.016 doi: 10.1016/j.dam.2021.08.016 |
[19] | L. K$\ddot{o}$lsch, XOR counts and lightweight multiplication with fixed elements in binary finite fields, Springer, Cham, 11476 (2019), 285–312. https://doi.org/10.1007/978-3-030-17653-2_10 |
[20] | J. Lacan, J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Commun. Lett., 8 (2004), 570–572. https://doi.org/10.1109/LCOMM.2004.833807 doi: 10.1109/LCOMM.2004.833807 |
[21] | J. Philip, Circulant matrices, Wiley Press, New York, 1979. |
[22] | A. R. Rao, P. Bhimasankaram, Linear algebra, 2 Eds., Hindustan Book Agency, 2000. |
[23] | V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, E. De Win, The cipher SHARK, In: Fast Software Encryption, LNCS, 1039 (1996), 99–111. https://doi.org/10.1007/3-540-60865-6_47 |
[24] | M. Sajadieh, M. Dakhilalian, H. Mala, P. Sepehrdad, Recursive diffusion layers for block ciphers and Hash functions, In: Fast Software Encryption, LNCS, Springer, Berlin, Heidelberg, 7549 (2012), 385–401. |
[25] | S. Sarkar, S. M. Sim, A deeper understanding of the XOR count distribution in the context of lightweight cryptography, In Progress in Cryptology-AFRICACRYPT: 8th International Conference on Cryptology in Africa, Fes, Morocco, Springer International Publishing, 8 (2016), 167–182. https://doi.org/10.1007/978-3-319-31517-1_9 |
[26] | S. M. Sim, K. Khoo, F. Oggier, T. Peyrin, Lightweight MDS involution matrices, In Fast Software Encryption: 22nd International Workshop, FSE 2015, Istanbul, 2015. |
[27] | S. Wu, M. Wang, W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, In Selected Areas in Cryptography: 19th International Conference, Springer, Berlin, Heidelberg, 2013,355–371. https://doi.org/10.1007/978-3-642-35999-6_23 |