Experimental methods for constructing MDS~matrices of a special form

M. I. Rozhkov ; S. S. Malakhov

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 115-128.

Résumé

MDS matrices are widely used as a diffusion primitive in the construction of block type encryption algorithms and hash functions (such as AES and GOST 34.12–2015). The matrices with the maximum number of units and minimum number of different elements are important for more efficient realizations of the matrix-vector multiplication. The article presents a new method for the MDS testing of matrices over finite fields and shows its application to the ($8 \times 8$)-matrices of a special form with many units and few different elements; these matrices were introduced by Junod and Vaudenay. For the proposed method we obtain some theoretical and experimental estimates of effectiveness. Moreover, the article comprises a list of some MDS matrices of the above-indicated type. Tab. 7, bibliogr. 15.

Détail

Mots-clés : MDS matrix, MDS code.

Bibliographie

[1] A. V. Anashkin, “Complete description of a class of MDS-matrices over finite field of characteristic $2$”, Mat. Vopr. Kriptogr., 8:4 (2017), 5–28 (in Russian) | DOI | MR

[2] R. Lidl, H. Niederreiter, Finite Fields, Camb. Univ. Press, Cambridge, 1985 | MR | MR

[3] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Math. Libr., 16, North-Holland, Amsterdam, 1977 | MR | Zbl

[4] F. M. Malyshev, “The duality of differential and linear methods in cryptography”, Mat. Vopr. Kriptogr., 5:3 (2014), 35–47 (in Russian) | DOI

[5] F. M. Malyshev, D. I. Trifonov, “Diffusion properties of XSLP-ciphers”, Mat. Vopr. Kriptogr., 7:3 (2016), 47–60 (in Russian) | DOI | MR

[6] M. Hall, Jr., Combinatorial Theory, Blaisdell, Waltham, MA, 1967 | MR | MR | Zbl

[7] Augot D., Finiasz M., “Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions”, Proc. IEEE Int. Symp. Information Theory (Istanbul, Turkey, July 7–12, 2013), IEEE, Piscataway, 2013, 1551–1555

[8] Belov A. V., Los A. B., Rozhkov M. I., “Some approaches to construct MDS matrices over a finite field”, Commun. Appl. Math. Comput., 31:2 (2017), 143–152 | MR | Zbl

[9] Belov A. V., Los A. B., Rozhkov M. I., “Some classes of the MDS matrices over a finite field”, Lobachevskii J. Math., 38:5 (2017), 880–883 | DOI | MR | Zbl

[10] Couselo E., González S., Markov V., Nechaev A., “Recursive MDS-codes and recursive differentiable quasigroups”, Discrete Math. Appl., 8:3 (1998), 217–245 | DOI | MR | Zbl

[11] Couselo E., González S., Markov V., Nechaev A., “Parameters of recursive MDS-codes”, Discrete Math. Appl., 10:5 (2000), 433–453 | DOI | MR | Zbl

[12] Gupta K. C., Ray I. G., “On constructions of MDS matrices from companion matrices for lightweight cryptography”, Security Engineering and Intelligence Informatics, Proc. CD-ARES Workshops (Regensburg, Germany, Sept. 2–6, 2013), Lect. Notes Comp. Sci., 8128, Springer, Heidelberg, 2013, 29–43 | DOI

[13] Gupta K. C., Ray I. G., “On constructions of circulant MDS matrices for lightweight cryptography”, Information Security Practice and Experience, Proc. 10th Int. Conf. (Fuzhou, China, May 5–8, 2014), Lect. Notes Comput. Sci., 8434, Springer, Cham, 2014, 564–576 | DOI

[14] Junod P., Vaudenay S., “Perfect diffusion primitives for block ciphers: building efficient MDS matrices”, Rev. Sel. Pap. 11th Int. Conf. Sel. Areas Cryptogr. (Waterloo, Canada, Aug. 9–10, 2004), Lect. Notes Comput. Sci., 3357, Springer, Heidelberg, 2005, 84–99 | DOI | MR | Zbl

[15] Matsui M., “On correlation between the order of S-boxes and the strength of DES”, Advances in Cryptology – EUROCRYPT'94: Proc. Workshop Theory Appl. Cryptogr. Tech. (Perugia, Italy, May 9–12, 1994), Lect. Notes Comput. Sci., 950, Springer, Heidelberg, 1995, 366–375 | DOI | MR | Zbl