Exploring the Feasibility of Meeting the MDS Criterion in Random Matrices and Searching for Efficient Random Involutory Hadamard MDS Matrices

  • Trần Thị Lượng Academy of cryptography techniques of Viet Nam Government Information Security Commission, Hanoi
Keywords: MDS matrix, random matrices, Hadamard MDS matrix, Circulant-like MDS matrix.


Maximum distance separable codes (MDS codes) have been studied for a long time in error correcting code theory and have important applications in cryptography. There are many different methods have been studied to build MDS matrices such as: from MDS codes, Cauchy matrices, Hadamard matrices, Vandermonde matrices, circulant and circulant-like matrices etc. In this paper, the construction of MDS matrix from random matrices is studied, and the possibility of satisfying the MDS condition of any random matrix is presented. Then, the method of random search of MDS matrices will be given. In addition, we propose algorithms to randomly search for efficient involutory Hadamard MDS matrices of size 4, and 8. These results will be meaningful to determine the possibility that MDS matrices can be obtained from random matrices and diversify the methods of searching for MDS matrices. The involutory Hadamard MDS matrices make the encryption and decryption processes identical, which makes them very efficient for both hardware and software implementation.

Author Biography

Trần Thị Lượng, Academy of cryptography techniques of Viet Nam Government Information Security Commission, Hanoi
Chủ nhiệm Bộ môn, Khoa An toàn thông tin


[1] A. M. Elhosary, N. Hamdy, I.A. Farag, A.E Rohiem, Optimum Dynamic Diffusion of Block Cipher Based on Maximum Distance Separable Matrices, International Journal of Information & Network Security (IJINS), Vol.2, No.4, August 2013, pp. 327-332, ISSN: 2089-3299.
[2] A. M. Youssef, S. E. Tavares and H. M. Heys, A New Class of Substitution Permutation Networks, Workshop on Selected Areas in Cryptography, SAC '96, Workshop Record, pp. 132-147, 1996.
[3] A. M. Youssef, S.Mister and S.E. Tavares, On the Design of Linear Transformations for Substitution Permutation Encryption Networks, in Workshop on Selected Areas in Cryptography (SAC’97), pp. 40-48, 1997.
[4] A. R. Rao, P. Bhimasankaram, Linear Algebra, Second Edition, Hindustan Book Agency.
[5]. F. J. MacWilliams, N.J.A. Sloane, Bell Laboratories, Murray Hill, NJ 07974, U. S. A. The Theory of Error-Correcting Codes, North-holland publishing company amsterdam . new york . oxford, 1977.
[6] J. Daemen, L. Knudsen, and V. Rijmen, The block cipher Square, Fast Software Encryption (FSE'97), LNCS 1267, pp. 149-165, Springer-Verlag, 1997.
[7] K. C. Gupta and I. G. Ray, On Constructions of Involutory MDS Matrices, In AFRICACRYPT 2013, pp 43-60, Springer 2013.
[8] K. C. Gupta, I. G. Ray, On Constructions of MDS Matrices From Circulant-Like Matrices For Lightweight Cryptography, Technical Report No. ASU/2014/1, Dated : 14th February, 2014.
[9] K. C. Gupta, I. G. Ray, On constructions of mds matrices from companion matrices for lightweight cryptography. In A. Cuzzocrea, C. Kittl, D. E. Simos, E. Weippl, L. Xu, A. Cuzzocrea, C. Kittl, D. E. Simos, E. Weippl, and L. Xu, editors, CD-ARES Workshops, volume 8128 of Lecture Notes in Computer Science, pages 29–43. Springer, 2013.
[10] M. Sajadieh, M. Dakhilalian, H. Mala, B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in GF(2q), Springer Science and Business Media, LLC 2011.
[11] P. Junod and S. Vaudenay, Perfect diffusion primitives for block cipher – Building efficient MDS matrices in Selected Areas in Cryptology (SAC 2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004.
[12] R. Elumalai, Dr. A. R. Reddy, Improving Diffusion Power of AES Rijndael with 8×8 MDS Matrix, International Journal of Scientific & Engineering Research Volume 2, Issue 3, March-2011.
[13] R. Klima, N. Sigmon, E. Stitzinger, Applications of abstract algebra with maple, CRC Press, Boca Raton London New York Washington, D.C, 1999.
[14] S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice Hall, 2004.
[15] T. P. Berger, A.V. Ourivski, Construction of new MDS codes from Gabidulin codes, LACO, University of Limoges, France, 2013.
[16] Venkateswarlu, A., Kesarwani, A., & Sarkar, S. On the Lower Bound of Cost of MDS Matrices. IACR Transactions on Symmetric Cryptology, pp. 266-290, 2022.
[17] Zhou, X., & Cong, T. Construction of generalized-involutory MDS matrices. Cryptology ePrint Archive, 2022.
[18] Gupta K.C., Pandey S.K., Venkateswarlu, Almost involutory recursive MDS diffusion layers, Design, Codes and Cryptography, 87 (2018), 609-626.
[19] Kolay S., Mukhopadhyay D., “Lightweight diffusion layer from the kth root of the mds matrix”, IACR Cryptology ePrint Archive, vol. 498, 2014.
[20] Luong T. T., “Constructing effectively mds and recursive mds matrices by reed-solomon codes”, Journal of Science and Technology on Information Security of Viet Nam Government Information Security Commission, vol.3, no. 2, pp. 10–16, 2016.
[21] Luong T. T., Cuong N. N., and Trinh B. D., 4x4 Recursive MDS Matrices Effective for Implementation from Reed-Solomon Code over GF(q) Field. International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences – MCO 2021, pp 386-391, 2021.
[22] Gupta, K. C., Pandey, S. K., & Samanta, S. Construction of Recursive MDS Matrices Using DLS Matrices. In Progress in Cryptology-AFRICACRYPT 2022: 13th International Conference on Cryptology in Africa, AFRICACRYPT 2022, Springer Nature Switzerland, pp. 18–22, 2022.
[23] Freyre P. Coauthors: D´ıaz N, D´ıaz R & P´erez C, Random Generation of MDS matrices, CTCRYPT 2014, 2014. DOI:10.13140/RG.2.1.5111.2160