Geodesic
The construction of circulant matrices related to MDS matrices
Prikladnaâ diskretnaâ matematika, no. 2 (2022), pp. 17-27.

Voir la notice de l'article provenant de la source Math-Net.Ru

The objective of this paper is to suggest a method of the construction of circulant matrices, which are appropriate for being MDS (Maximum Distance Separable) matrices utilising in cryptography. Thus, we focus on designing so-called bi-regular circulant matrices, and furthermore, impose additional restraints on matrices in order that they have the maximal number of some element occurrences and the minimal number of distinct elements. The reason to construct bi-regular matrices is that any MDS matrix is necessarily the bi-regular one, and two additional restraints on matrix elements grant that matrix-vector multiplication for the samples constructed may be performed efficiently. The results obtained include an upper bound on the number of some element occurrences for which the circulant matrix is bi-regular. Furthermore, necessary and sufficient conditions for the circulant matrix bi-regularity are derived. On the basis of these conditions, we developed an efficient bi-regularity verification procedure. Additionally, several bi-regular circulant matrix layouts of order up to 31 with the maximal number of some element occurrences are listed. In particular, it appeared that there are no layouts of order 32 with more than 5 occurrences of any element which yield a bi-regular matrix (and hence an MDS matrix).
Mots-clés : circulant matrix, MDS code, MDS matrix. 
@article{PDM_2022_2_a1,
     author = {S. S. Malakhov and M. I. Rozhkov},
     title = {The construction of circulant matrices related to {MDS} matrices},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {17--27},
     publisher = {mathdoc},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_2_a1/}
}
TY  - JOUR
AU  - S. S. Malakhov
AU  - M. I. Rozhkov
TI  - The construction of circulant matrices related to MDS matrices
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 17
EP  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_2_a1/
LA  - en
ID  - PDM_2022_2_a1
ER  - 
%0 Journal Article
%A S. S. Malakhov
%A M. I. Rozhkov
%T The construction of circulant matrices related to MDS matrices
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 17-27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_2_a1/
%G en
%F PDM_2022_2_a1
S. S. Malakhov; M. I. Rozhkov. The construction of circulant matrices related to MDS matrices. Prikladnaâ diskretnaâ matematika, no. 2 (2022), pp. 17-27. http://geodesic.mathdoc.fr/item/PDM_2022_2_a1/

[1] F. J. MacWilliams, N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, Elsevier, 1977 | MR

[2] B. Segre, “Curve razionali normali ek-archi negli spazi finiti”, Ann. Matem. Pura Appl., 39:1 (1955), 357–379 | DOI | MR | Zbl

[3] S. Ball, “On sets of vectors of a finite vector space in which every subset of basis size is a basis”, J. Europ. Math. Soc., 14:3 (2012), 733–748 | DOI | MR | Zbl

[4] P. Junod, S. Vaudenay, “Perfect diffusion primitives for block ciphers”, LNCS, 3357, 2004, 84–99 | MR

[5] M. I. Rozhkov, S. S. Malakhov, “Experimental methods for constructing MDS matrices of a special form”, J. Appl. Industr. Math., 13:2 (2019), 302–309 | DOI | MR | Zbl

[6] K. C. Gupta, I. G. Ray, “On constructions of circulant MDS matrices for lightweight cryptography”, LNCS, 8434, 2014, 564–576

[7] Y. Li, M. Wang, “On the construction of lightweight circulant involutory MDS matrices”, Intern. Conf. FSE, LNCS, 9783, 2016, 121–139 | Zbl

[8] V. Cauchois, P. Loidreau, “On circulant involutory MDS matrices”, Designs, Codes and Cryptography, 87 (2019), 249–260 | DOI | MR | Zbl

[9] A. Kesarwani, S. Sarkar, A. Venkateswarlu, “Exhaustive search for various types of MDS matrices”, IACR Trans. Symmetric Cryptology, 256 (2019), 231 | DOI

[10] S. S. Malakhov, M. I. Rozhkov, “On construction of bi-regular circulant matrices, relating to MDS matrices”, 2021 Intern. Conf. Engineering Technologies and Computer Science, EnT, IEEE, 2021, 56–58 | DOI

[11] K. Zarankiewicz, “Problem P 101”, Colloq. Math., 2 (1951), 131

[12] I. Reiman, “Über ein problem von K. Zarankiewicz”, Acta Mathematica Academiae Scientiarum Hungarica, 9:3–4 (1958), 269–273 | DOI | MR | Zbl