Том 28, номер 2, 2021 г., Стр. 74-91

УДК 519.17
Фомичёв В. М.
О степени нелинейности координатных полиномов произведения преобразований двоичного векторного пространства

Аннотация:
Построена неотрицательная целочисленная матрица для оценки матрицы характеристик нелинейности координатных полиномов произведения преобразований двоичного векторного пространства. Матрица характеристик преобразования определяется степенями нелинейности производных всех координатных функций по каждой входной переменной. Элементы оценочной матрицы выражены через характеристики координатных полиномов умножаемых преобразований. Вычисление оценочной матрицы выполняется более просто по сравнению с вычислением точных значений характеристик. Метод оценивания распространён на произвольное количество умножаемых преобразований. Приведены вычислительные примеры, в частности, показывающие точность полученных оценок и область их нетривиальности.
Табл. 1, библиогр. 18.

Ключевые слова: координатный полином преобразования, максимальный моном полинома, степень полинома.

DOI: 10.33048/daio.2021.28.700

Фомичёв Владимир Михайлович ^1,2,3
1. Финансовый университет при Правительстве Российской Федерации,
Ленинградский пр-т, 49, 125993 Москва, Россия
2. ООО «Код Безопасности»,
1-й Нагатинский пр-д, 10, стр. 1, 115230 Москва, Россия
3. Институт проблем информатики ФИЦ «Информатика и управление» РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
е-mail: fomichev.2016@yandex.ru

Статья поступила 28 сентября 2020 г.
После доработки — 15 февраля 2021 г.
Принята к публикации 19 февраля 2021 г.

Литература

[1] Фомичёв В. М., Авезова Я. Э., Коренева А. М, Кяжин С. Н. Примитивность и локальная примитивность орграфов и неотрицательных матриц // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 95–125.

[2] Fomichev V. M., Koreneva A. M. Encryption performance and security of certain wide block ciphers // J. Comput. Virol. Hack. Tech. 2020. Vol. 16. P. 197–216.

[3] Фомичёв В. М., Бобров В. М. Оценка с помощью матрично-графового подхода характеристик локальной нелинейности итераций преобразований векторных пространств // Прикл. дискрет. математика. Прил. 2019. № 12. С. 32–35.

[4] Fröbenius G. Uber Matrizen aus nicht negativen Elementen // Berl. Ber. 1912. S. 456–477. [German].

[5] Wielandt H. Unzerlegbare, nicht negative Matrizen // Math. Z. 1950. Bd. 52. S. 642–648. [German].

[6] Perkins P. A theorem on regular graphs // Pac. J. Math. 1961. Vol. 2. P. 1529–1533.

[7] Dulmage A. L., Mendelsohn N. S. The exponent of a primitive matrix // Can. Math. Bull. 1962. Vol. 5, No. 3. P. 241–244.

[8] Dulmage A. L., Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Ill. J. Math. 1964. Vol. 8, No. 4. P. 642–656.

[9] Brualdi R. A., Liu B. Generalized exponents of primitive directed graphs // J. Graph Theory. 1990. Vol. 14, No. 4. P. 483–499.

[10] Neufeld S. W. A diameter bound on the exponent of a primitive directed graph // Lin. Algebra Appl. 1996. Vol. 245. P. 27–47.

[11] Liu B. Generalized exponents of Boolean matrices // Lin. Algebra Appl. 2003. Vol. 373. P. 169–182.

[12] Sachkov V. N., Tarakanov V. E. Combinatorics of nonnegative matrices. Providence, RI: Amer. Math. Soc. 2002. 269 p. (Transl. Math. Monogr.; Vol. 213)

[13] Фомичёв В. М., Кяжин С. Н. Локальная примитивность матриц и графов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 1. С. 97–119.

[14] Suzaki T., Minematsu K. Improving the generalized Feistel // Fast Software Encryption. Proc. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010). Heidelberg: Springer, 2010. P. 19–39. (Lect. Notes Comput. Sci.; Vol. 6147).

[15] Berger T., Francq J., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput // IEEE Trans. Comput. 2016. Vol. 65, No. 7. P. 2074–2089. ‘

[16] Berger T., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation // Selected Areas in Cryptography — SAC 2013. Proc. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013). Heidelberg: Springer, 2014. P. 289–305. (Lect. Notes Comput. Sci.; Vol. 8282).

[17] Nyberg K. Generalized Feistel networks // Advances in Cryptology — ASIACRYPT’96. Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (Kyongju, Korea, Nov. 3–7, 1996). Heidelberg: Springer, 1996. P. 91–104. (Lect. Notes Comput. Sci.; Vol. 1163).

[18] Логачёв О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М: МЦНМО, 1973. 470 с.