Estimation for The Number of MDS Matrices, Recursive MDS Matrices and Symmetric Recursive MDS Matrices from the Reed-Solomon Codes
Abstract
The diffusion layer of the SPN block ciphers is
usually built on the basis of the MDS (Maximum Distance
Separable) matrices which is the matrix of the maximum distance separable code (MDS code). MDS codes have long been studied in error correcting code theory and have applications not only in coding theory but also in the design of block ciphers and hash functions. Thanks to that important role, there have been many studies on methods of building MDS matrices. In particular, the recursive MDS matrices and the symmetric recursive MDS matrices have particularly important applications because they are very efficient for execution. In this paper, we will give an estimate of the number of MDS matrices, recursive MDS matrices and symmetric recursive MDS matrices built from ReedSolomon codes. This result is meaningful in determining the efficiency from this method of building matrices based on the Reed-Solomon codes. From there, this method can be applied to find out many MDS matrices, secure and efficient symmetric recursive MDS matrices for execution to apply in current block ciphers. Furthermore, recursive MDS matrices can be efficiently implemented using Linear Feedback Shift Registers (LFSR), making them well suited for lightweight cryptographic algorithms, so suitable for limited resources application.
References
Augot D., Finiasz M., "Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions", in 2013 IEEE International Symposium on Information Theory Proceedings (ISIT). IEEE, 2013, pp.1551-1555.
Augot D., Finiasz M., "Direct construction of recursive MDS diffusion layers using shortened BCH codes". In: FSE 2014, LNCS, vol. 8540, pp. 3–17. Springer (2015).
Berger T. P., "Construction of recursive MDS diffusion layers from Gabidulin codes". In: INDOCRYPT 2013, LNCS, vol. 8250, pp. 274–285. Springer (2013).
Berger T. P., Ourivski A. V., "Construction of new MDS codes from Gabidulin codes", LACO, University of Limoges, 2013.
Daemen J., Knudsen L., and Rijmen V., "The block cipher Square, in Fast Software Encryption" (FSE’97). Springer, 1997, pp. 149-165.
Gupta K.C., Pandey S.K., Venkateswarlu A., "On the direct construction of recursive MDS matrices". Des. Codes Cryptogr. 82(1–2), 77–94 (2017).
Gupta K.C., Pandey S.K., Venkateswarlu A., "Towards a general construction of recursive MDS diffusion layers". Des. Codes Cryptogr. 82(1–2), 179–195 (2017).
Gupta K.C., Ray I.G., "On constructions of MDS matrices from companion matrices for lightweight cryptography". In: CD-ARES Workshops 2013, LNCS, vol. 8128, pp. 29–43. Springer (2013).
Gupta K.C., Pandey S.K., Venkateswarlu, "Almost involutory recursive MDS diffusion layers", Design, Codes and Cryptography, 87 (2018), 609-626.
Kolay S., Mukhopadhyay D., “Lightweight diffusion layer from the kth root of the mds matrix”, IACR Cryptology ePrint Archive, vol. 498, 2014.
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.
Luong T. T., Cuong N. N., and Tho H. D., "Constructing Recursive MDS Matrices Effective for Implementation from Reed-Solomon Codes and Preserving the Recursive Property of MDS Matrix of Scalar Multiplication", Journal of Informatics and Mathematical Sciences, Vol. 11, No. 2, pp. 155–177, 2019.
Luong T. T., Cuong N. N., and Trinh B. D., "4×4 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.
MacWiliams F.J, Sloan N.J., "The Theory of ErrorCorrecting Codes", North-holland Publishing Company Amsterdam-New York- Oxford, Third Printing, 1981.
Rijmen V., Daemen J., Preneel B., Bosselaers A., De Win E., "The cipher Shark, in Fast Software Encryption". Springer, 1996, pp. 99-111.
Sajadieh M., Dakhilalian M., Mala H., Sepehrdad P., "Recursive diffusion layers for block ciphers and hash functions". In: FSE 2012, LNCS, vol. 7549, pp. 385–401. Springer (2012).
Shannon C. E., "Communication theory of secrecy systems", Bell System Technical Journal, vol. 28, no. 4, pp. 656-715, 1949.
Wu S., Wang M., Wu W., "Recursive diffusion layers for (lightweight) block ciphers and hash functions". In: SAC 2013, LNCS, vol. 7707, pp. 355–371. Springer (2013).
T. T. Luong, N. N. Cuong, “Direct exponent and scalar multiplication transformations of mds matrices: some good cryptographic results for dynamic diffusion”, Journal of Computer Science and Cybernetics, vol.32, no.1, pp. 1–17, 2016.
