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

Abstract

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

References

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.

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.

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.

A. R. Rao, P. Bhimasankaram, “Linear Algebra”, Second Edition, Hindustan Book Agency.

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.

J. Daemen, L. Knudsen, and V. Rijmen, “The block cipher Square”, Fast Software Encryption (FSE’97), LNCS 1267, pp. 149–165, Springer-Verlag, 1997.

K. C. Gupta and I. G. Ray, “On Constructions of Involutory MDS Matrices”, In AFRICACRYPT 2013, pp. 43–60,

Springer 2013.

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.

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, pp. 29–43. Springer, 2013.

M. Sajadieh, M. Dakhilalian, H. Mala, B. Omoomi, “On construction of involutory MDS matrices from Vandermonde Matrices in GF(2q)”, Designs, Codes and Cryptography, 64, 287–308.

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.

R. Elumalai, Dr. A. R. Reddy, “Improving Diffusion Power of AES Rijndael with 8×8 MDS Matrix”, International Journal of Scientific & Engineering Research, Vol. 2, Issue 3, March-2011.

R. Klima, N. Sigmon, E. Stitzinger, “Applications of abstract algebra with maple”, CRC Press, Boca Raton London New York Washington, D.C, 1999.

S. Lin and D. Costello, “Error Control Coding: Fundamentals and Applications”, Prentice Hall, 2004.

T. P. Berger, A.V. Ourivski, “Construction of new MDS codes from Gabidulin codes”, LACO, University of Limoges, France, 2013.

A. Venkateswarlu, A. Kesarwani and S. Sarkar, “On the Lower Bound of Cost of MDS Matrices”, IACR Transactions on Symmetric Cryptology, pp. 266–290, 2022.

X. Zhou and T. Cong, “Construction of generalizedinvolutory MDS matrices”, Cryptology ePrint Archive, 2022.

K. C. Gupta, S. K. Pandey and Venkateswarlu, “Almost involutory recursive MDS diffusion layers”, Design, Codes and Cryptography, 87 (2018), 609–626.

S. Kolay and D. Mukhopadhyay, “Lightweight diffusion layer from the kth root of the mds matrix”, IACR Cryptology ePrint Archive, vol. 498, 2014.

T. T Luong, “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.

T. T. Luong, N. N. Cuong and B. D. Trinh, “4x4 Recursive MDS Matrices Effective for Implementation from ReedSolomon Code over GF(q) Field”, International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences – MCO 2021, pp 386–391, 2021.

K. C. Gupta, S. K. Pandey and S. Samanta, “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.

P. Freyre, N. Díaz, R. Díaz and C. Pérez, “Random generation of MDS matrices”, Proceedings of Current Trends in Cryptology CTCrypt2014, Russia, 2014. DOI:10.13140/RG.2.1.5111.2160

A. Kesarwani, S. Sarkar and A. Venkateswarlu, “Exhaustive search for various types of MDS matrices”, IACR Transactions on Symmetric Cryptology, 2019, 231–256.

M. Kurt Pehlivanoglu, M. Ali Demir, F. B ˘ uy ¨ uksarac¸o ¨ glu ˘ Sakallı, S. Akleylek and M. Tolga Sakallı, “On the Construction Structures of Involutory MDS Matrices over ”, In Nonlinear Dynamics and Applications: Proceedings of the ICNDA, Cham: Springer International Publishing, pp. 587–595, 2022.

G. Tuncay, F. B. Sakallı, M. K. Pehlivanoglu, G. G. Yıl- ˘ mazguc¸, S. Akleylek and M. T. Sakallı, “A new hybrid method combining search and direct based construction ideas to generate all involutory maximum distance separable (MDS) matrices over binary field extensions”, PeerJ Computer Science, 9, 2023, e1577.

Published
2024-01-22