Цель данной работы - предложить метод построения таких циркулянтных матриц, которые могут быть MDS-матрицами, используемыми в криптографии. Мы рассматриваем так называемые би-регулярные циркулянтные матрицы и, кроме того, налагаем на них дополнительные ограничения с тем, чтобы они имели максимальное число вхождений некоторого элемента и минимальное количество различных элементов. Интерес к би-регулярным матрицам обусловлен тем, что любая MDS-матрица обязательно является би-регулярной, а дополнительные ограничения на элементы матриц позволяют эффективнее реализовывать матрично-векторные операции с использованием таких матриц. Полученные результаты включают верхнюю границу числа вхождений некоторого элемента, при котором циркулянтная матрица остаётся би-регулярной, а также необходимые и достаточные условия би-регулярности циркулянтной матрицы. Кроме того, описан эффективный алгоритм проверки би-регулярности циркулянтной матрицы. С его помощью построены шаблоны би-регулярных циркулянтных матриц порядка до 31 с максимальным числом вхождений некоторого элемента и установлено отсутствие би-регулярных циркулянтных матриц (и следовательно, MDS-матриц) порядка 32 с более чем пятью вхождениями одного элемента.
Скачать электронную версию публикации
Загружен, раз: 70
- Title О построении циркулянтных матриц, связанных с MDS-матрицами
- Headline О построении циркулянтных матриц, связанных с MDS-матрицами
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 56
- Date:
- DOI 10.17223/20710410/56/2
Ключевые слова
циркулянтная матрица, МДР-код, MDS-код, MDS-матрицаАвторы
Ссылки
MacWilliams F. J. and Sloane N. J. The Theory of Error-Correcting Codes, vol. 16. Elsevier, 1977.
Segre B. Curve razionali normali ek-archi negli spazi finiti. Ann. Matem. Pura Appl., 1955, vol. 39, no. 1, pp. 357-379.
Ball S. On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Europ. Math. Soc., 2012, vol. 14, no.3, pp. 733-748.
Junod P. and Vaudenay S. Perfect diffusion primitives for block ciphers. LNCS, 2004, vol. 3357, pp. 84-99.
Rozhkov M. I. and Malakhov S. S. Experimental methods for constructing MDS matrices of a special form. J. Appl. Industr. Math., 2019, vol. 13, no. 2, pp. 302-309.
Gupta K. C. and Ray I. G. On constructions of circulant MDS matrices for lightweight cryptography. LNCS, 2014, vol. 8434, pp. 564-576.
Li Y. and Wang M. On the construction of lightweight circulant involutory MDS matrices.Intern. Conf. FSE, LNCS, 2016, vol. 9783, pp. 121-139.
Cauchois V. and Loidreau P. On circulant involutory MDS matrices. Designs, Codes and Cryptography, 2019, vol. 87, pp. 249-260.
Kesarwani A., Sarkar S., and Venkateswarlu A. Exhaustive search for various types of MDS matrices. IACR Trans. Symmetric Cryptology, 2019, pp. 231-256.
Malakhov S. S. and Rozhkov M. I. On construction of bi-regular circulant matrices, relating to MDS matrices. 2021 Intern. Conf. Engineering Technologies and Computer Science (EnT), IEEE, 2021, pp. 56-58.
Zarankiewicz K. Problem P 101. Colloq. Math., 1951, vol. 2, p. 131.
Reiman I. Uber ein problem von K. Zarankiewicz. Acta Mathematica Academiae Scientiarum Hungarica, 1958, vol. 9, no. 3-4, pp. 269-273.

О построении циркулянтных матриц, связанных с MDS-матрицами | Прикладная дискретная математика. 2022. № 56. DOI: 10.17223/20710410/56/2
Скачать полнотекстовую версию
Загружен, раз: 113