Article Contents
Article Contents

# Involutory-Multiple-Lightweight MDS Matrices based on Cauchy-type Matrices

• * Corresponding author: Morteza Esmaeili
• One of the best methods for constructing maximum distance separable ($\operatorname{MDS}$) matrices is based on making use of Cauchy matrices. In this paper, by using some extensions of Cauchy matrices, we introduce several new forms of $\operatorname{MDS}$ matrices over finite fields of characteristic 2. A known extension of a Cauchy matrix, called the Cauchy-like matrix, with application in coding theory was introduced in 1985. One of the main contributions of this paper is to apply Cauchy-like matrices to introduce $2n \times 2n$ involutory $\operatorname{MDS}$ matrices in the semi-Hadamard form which is a generalization of the previously known methods. We make use of Cauchy-like matrices to construct multiple $\operatorname{MDS}$ matrices which can be used in the Feistel structures. We also introduce a new extension of Cauchy matrices to be referred to as Cauchy-light matrices. The introduced Cauchy-light matrices are applied to construct $n \times n$ $\operatorname{MDS}$ matrices having at least $3n-3$ entries equal to the unit element $1$; such a matrix is called a lightweight $\operatorname{MDS}$ matrix and can be used in the lightweight cryptography. A simple closed-form expression is given for the determinant of Cauchy-light matrices.

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14G50.

 Citation:

•  [1] D. Augot and M. Finiasz, Direct construction of recursive MDS diffusion layers using shortened BCH codes, in Fast Software Encryption. FSE 2014, Vol. 8540, Springer, Berlin, Heidelberg, 2014, 3-17. doi: 10.1007/978-3-662-46706-0_1. [2] P. Barreto and V. Rijmen, The Khazad legacy-level block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). [3] P. Barreto and V. Rijmen, The Anubis block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). [4] C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in $GF(2^n)$ with applications to MDS matrices, in Advances in Cryptology. CRYPTO 2016. Part 1, Lecture Notes in Comput. Sci., Vol. 9814, Springer, Berlin, 2016,625-653. doi: 10.1007/978-3-662-53018-4_23. [5] T. P. Berger, G. Paul and S. Vaudenay, eds., Construction of recursive MDS diffusion layers from gabidulin codes, in Progress in Cryptology. INDOCRYPT 2013, Vol. 8250, Springer, Cham, 2013,274-285. doi: 10.1007/978-3-319-03515-4. [6] J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4. [7] G. Filho, P. Barreto and V. Rijmen, The Maelstrom-$0$ hash function, in Proceedings of the Sixth Brazilian Symposium on Information and Computer Systems Security, (2006). [8] J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, in Advances in Cryptology. CRYPTO 2011, Vol. 6841, Springer, Heidelberg, 2011,222-239. doi: 10.1007/978-3-642-22792-9. [9] K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, in Security Engineering and Intelligence Informatics. CD-ARES 2013, Vol. 8128, Springer, Berlin, Heidelberg, 2013, 29-43. doi: 10.1007/978-3-642-40588-4_3. [10] K. C. Gupta and I. G. Ray, On constructions of involutory MDS matrices, in Progress in Cryptology. AFRICACRYPT 2013, Vol. 7918, Springer, Heidelberg, 2013, 43-60. doi: 10.1007/978-3-642-38553-7_3. [11] K. C. Gupta and I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptogr. Commun., 7 (2015), 257-287.  doi: 10.1007/s12095-014-0116-3. [12] K. C. Gupta, S. K. Pandey, I. G. Ray and S. Samanta, Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results, Adv. Math. Commun., 13 (2019), 779-843.  doi: 10.3934/amc.2019045. [13] H. Hou and S. Y. Han, A new construction and an efficient decoding method for Rabin-like codes, IEEE Transactions on Communications, 66 (2018), 521-533.  doi: 10.1109/TCOMM.2017.2766140. [14] P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers building efficient MDS matrices, in Selected Areas in Cryptography. SAC 2004, Vol. 3357, Springer, Berlin, 2005, 84-99. doi: 10.1007/978-3-540-30564-4_6. [15] K. Khoo, T. Peyrin, A. Y. Poschmann and H. Yap, FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison, in Cryptographic Hardware and Embedded Systems. CHES 2014, Vol. 8731, Springer, Berlin, Heidelberg, 2014,433-450. doi: 10.1007/978-3-662-44709-3_24. [16] L. Kölsch, XOR-counts and lightweight multiplication with fixed elements in binary finite fields, in Advances in Cryptology. EUROCRYPT 2019, Vol. 11476, Springer, Cham, 2019,285-312. doi: 10.1007/978-3-030-17653-2_10. [17] H. Kranz, G. Leander, K. Stoffelen and F. Wiemer, Shorter linear straight-line programs for MDS matrices, IACR Transactions on Symmetric Cryptology, 2017 (2017), 188-211. [18] J. Lacan and J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Communications Letters, 8 (2004), 570-572.  doi: 10.1109/LCOMM.2004.833807. [19] S. Li, S. Sun, C. Li, Z. Wei and L. Hu, Constructing low-latency involutory MDS matrices with lightweight circuits, IACR Transactions on Symmetric Cryptology, 2019 (2019), 84-117. [20] M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, in Fast Software Encryption. FSE 2016, Vol. 9783, Springer, Berlin, Heidelberg, 2016,101-120. doi: 10.1007/978-3-662-52993-5_6. [21] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, The Clarendon Press, Oxford University Press, New York, 1995. [22] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. [23] C. Paar, Optimized arithmetic for Reed-Solomon encoders, in Proceedings of IEEE International Symposium on Information Theory, Ulm, Germany, (1997), 250-250. doi: 10.1109/ISIT.1997.613165. [24] R. M. Roth and G. Seroussi, On generator matrices of MDS codes, IEEE Trans. Inform. Theory, 31 (1985), 826-830.  doi: 10.1109/TIT.1985.1057113. [25] R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inform. Theory, 35 (1989), 1314-1319.  doi: 10.1109/18.45291. [26] M. Sajadieh, M. Dakhilalian, H. Mala and B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in GF($2^q$), Des. Codes Cryptogr., 64 (2012), 287-308.  doi: 10.1007/s10623-011-9578-x. [27] C. Schindelhauer and C. Ortolf, Maximum distance separable codes based on circulant Cauchy matrices, in Structural Information and Communication Complexity. SIROCCO 2013, Vol. 8179, Springer, Cham, 2013,334-345. doi: 10.1007/978-3-319-03578-9_28. [28] C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J., 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x. [29] T. Shirai and K. Shibutani, Improving immunity of feistel ciphers against differential cryptanalysis by using multiple MDS matrices, in Fast Software Encryption. FSE 2004, Vol. 3017, Springer, Berlin, Heidelberg, 2004,260-278. doi: 10.1007/978-3-540-25937-4_17. [30] S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, Lightweight MDS involution matrices, in Fast Software Encryption. FSE 2015, Vol. 9054, Springer, Berlin, Heidelberg, 2015,471-493. doi: 10.1007/978-3-662-48116-5_23. [31] J. R. Stembridge, A concise proof of the Littlewood-Richardson rule, Electron. J. Combin., 9 (2002), 1-4.  doi: 10.37236/1666. [32] S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, in Selected Areas in Cryptography. SAC 2012, Vol. 7707, Springer, Heidelberg, 2012,355-371. doi: 10.1007/978-3-642-35999-6.