Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:2, 302-309
Volume 26, No 2, 2019, P. 115-128
UDC 519.688
M. I. Rozhkov and S. S. Malakhov
Experimental methods for constructing MDS matrices of a special form
Abstract:
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 impotant 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.
Keywords: MDS matrix, MDS code.
DOI: 10.33048/daio.2019.26.621
Mikhail I. Rozhkov 1
Stanislav S. Malakhov 1
1. National Research University “Higher School of Economics”,
20 Myasnitskaya Street, 101000 Moscow, Russia
e-mail: mirozhkov@hse.ru, ssmalakhov@edu.hse.ru
Received May 22, 2018
Revised January 28, 2019
Accepted January 29, 2019
References
[1] A. V. Anashkin, Complete description of a class of MDS-matrices over finite field of characteristic 2, Mat. Vopr. Kriptogr., 8, No. 4, 5–28, 2017 [Russian].[2] R. Lidl and H. Niederreiter, Finite Fields, Camb. Univ. Press, Cambridge, 1985. Translated under the title Konechnye polya, Mir, Moscow, 1988 [Russian].
[3] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977 (North-Holland Math. Libr., Vol. 16). Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Svyaz’, Moscow, 1979 [Russian].
[4] F. M. Malyshev, The duality of differential and linear methods in cryptography, Mat. Vopr. Kriptogr., 5, No. 3, 35–47, 2014 [Russian].
[5] F. M. Malyshev and D. I. Trifonov, Diffusion properties of XSLP-ciphers, Mat. Vopr. Kriptogr., 7, No. 3, 47–60, 2016 [Russian].
[6] M. Hall, Jr., Combinatorial Theory, Blaisdell, Waltham, MA, 1967. Translated under the title Kombinatorika, Mir, Moscow, 1970 [Russian].
[7] D. Augot and M. Finiasz, Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions, Proc. 2013 IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, July 7–12, 2013,
[8] A. V. Belov, A. B. Los, and M. I. Rozhkov, Some approaches to construct MDS matrices over a finite field, Commun. Appl. Math. Comp., 31, No. 2, 143–152, 2017.
[9] A. V. Belov, A. B. Los, and M. I. Rozhkov, Some classes of the MDS matrices over a finite field, Lobachevskii J. Math., 38, No. 5, 880–883, 2017.
[10] E. Couselo, S. González, V. Markov, and A. Nechaev, Recursive MDS-codes and recursive differentiable quasigroups, Discrete Math. Appl., 8, No. 3, 217–245, 1998.
[11] E. Couselo, S. González, V. Markov, and A. Nechaev, Parameters of recursive MDS-codes, Discrete Math. Appl., 10, No. 5, 433–453, 2000.
[12] K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, in Security Engineering and Intelligence Informatics (Proc. CD-ARES 2013 Workshops: MoCrySEn SeCIHD, Regensburg, Germany, Sept. 2–6, 2013), pp. 29–43, Springer, Heidelberg, 2013
(Lect. Notes Comput. Sci., Vol. 8128).
[13] K. C. Gupta and I. G. Ray, On constructions of circulant MDS matrices for lightweight cryptography, in Information Security Practice and Experience, (Proc. 10th Int. Conf., Fuzhou, China, May 5–8, 2014),
[14] P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers: Building efficient MDS matrices, Selected Areas in Cryptography (Rev. Sel. Pap. 11th Int. Conf., Waterloo, Canada, Aug. 9–10, 2004),
[15] M. Matsui, 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), pp. 366–375, Springer, Heidelberg, 1995 (Lect. Notes Comput. Sci., Vol. 950).
