Локальная нелинейность степеней преобразования

Локальная нелинейность степеней преобразования

Фомичёв В. М.
Дискретный анализ и исследование операций, 33, 2, 136-157 (2026)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2026.33.856

Аннотация:

В соответствии с шенноновской концепцией о перемешивающих свойствах преобразований информации развивается ранее предложенный автором матрично-графовый подход к оценке характеристик нелинейности произведения преобразований векторного пространства. Подход позволяет оценить локальные нелинейные свойства произведения преобразований с помощью троичных матриц и помеченных орграфов, однозначно соответствующих преобразованиям. Для троичных матриц и для помеченных орграфов с использованием длин путей определены свойство локальной 2-примитивности, оценки локальных 2-экспонентов и, в частности, точные значения. Получены критерии локальной 2-примитивности. Результаты для матриц и помеченных орграфов применяются для оценки характеристик произведения преобразований векторного пространства. Рассмотрены примеры. 

Библиогр. 18.

Литература:
  1. Fomichev V. M., Koreneva A. M. Encryption performance and security of certain wide block ciphers // J. Comput. Virol. Hacking Tech. 2020. V. 16. P. 197–216.
     
  2. Фомичёв В. М., Авезова Я. А., Коренева А. М., Кяжин С. Н. Примитивность и локальная примитивность орграфов и неотрицательных матриц // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 95–125. 
     
  3. Фомичёв В. М. Оценка характеристик нелинейности итеративных преобразований векторного пространства // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 4. С. 131–151.
     
  4. Frobenius G. Über Matrizen aus nicht negativen Elementen // Berl. Ber. 1912. S. 456–477. [German].
     
  5. Dulmage A. L., Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Ill. J. Math. 1964. V. 8, No. 4. P. 642–656.
     
  6. Berger T. P., 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. V. 65, No. 7. P. 2074–2089.
     
  7. 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.; V. 8282).
     
  8. Brualdi R. A., Liu B. Generalized exponents of primitive directed graphs // J. Graph Theory. 1990. V. 14, No. 4. P. 483–499.
     
  9. Huang Y., Liu B. Generalized $r$-exponents of primitive digraphs // Taiwan. J. Math. 2011. V. 15, No. 5. P. 1999–2012.
     
  10. Liu B. Generalized exponents of Boolean matrices // Lin. Algebra Appl. 2003. V. 373. P. 169–182.
     
  11. Miao Z., Zhang K. The local exponent sets of primitive digraphs // Lin. Algebra Appl. 2000. V. 307. P. 15–33.
     
  12. Shen J., Neufeld S. Local exponents of primitive digraphs // Lin. Algebra Appl. 1998. V. 268. P. 117–129.
     
  13. 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.; V. 6147).
     
  14. Wielandt H. Unzerlegbare, nicht negative Matrizen // Math. Z. 1950. Bd. 52. S. 642–648. [German].
     
  15. Perkins P. A theorem on regular graphs // Pac. J. Math. 1961. V. 2. P. 1529–1533.
     
  16. Dulmage A. L., Mendelsohn N. S. The exponent of a primitive matrix // Can. Math. Bull. 1962. V. 5, No. 3 P. 241–244.
     
  17. Neufeld S. W. A diameter bound on the exponent of a primitive directed graph // Lin. Algebra Appl. 1996. V. 245. P. 27–47.
     
  18. 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.; V. 1163).

Исследование выполнено за счёт бюджетов организаций, указанных автором на первой странице статьи. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Владимир Михайлович Фомичёв
  1. Российский университет дружбы народов им. Патриса Лумумбы, 
    ул. Миклухо-Маклая, 6, 117198 Москва, Россия
  2. Институт проблем информатики ФИЦ «Информатика и управление», 
    ул. Вавилова, 44, корп. 2, 119333 Москва, Россия

E-mail: fomichev.2016@yandex.ru 

Статья поступила 4 марта 2026 г.
После доработки — 10 марта 2026 г.
Принята к публикации 23 марта 2026 г.

Abstract:

In accordance with Shannon’s concept of the mixing properties of information transformations, a previously proposed matrixgraph approach is developed for assessing the characteristics of nonlinearity in the product of transformations in vector spaces. This approach makes it possible to evaluate local nonlinear properties of the product of transformations using ternary matrices and labeled digraphs that correspond unambiguously to the transformations. For ternary matrices and labeled digraphs, the property of local 2-primitivity and assessments of local 2-exponents, including exact values, is defined using path lengths. Criteria for local 2-primitivity is established. The results for matrices and labeled digraphs are applied to evaluate the characteristics of the product of transformations in vector spaces. Examples are considered. 

Bibliogr. 18.

References:
  1. V. M. Fomichev and A. M. Koreneva, Encryption performance and security of certain wide block ciphers, J. Comput. Virol. Hacking Tech. 16, 197–216 (2020).
     
  2. V. M. Fomichev, Ya. A. Avezova, A. M. Koreneva, and S. N. Kyazhin, Primitivity and local primitivity of digraphs and nonnegative matrices, Diskretn. Anal. Issled. Oper. 25 (3), 95–125 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 453–469 (2018)].
     
  3. V. M. Fomichev, Estimating nonlinearity characteristics for iterative transformations of a vector space, Diskretn. Anal. Issled. Oper. 27 (4), 131–151 (2020) [Russian] [J. Appl. Ind. Math. 14 (4), 610–622 (2020)].
     
  4. G. Frobenius, Über Matrizen aus nicht negativen Elementen, Berl. Ber., 456–477 (1912) [German].
     
  5. A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Ill. J. Math. 8 (4), 642–656 (1964).
     
  6. T. P. Berger, J. Francq, M. Minier, and G. Thomas, Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput, IEEE Trans. Comput. 65 (7), 2074–2089 (2016).
     
  7. T. Berger, M. Minier, and G. Thomas, Extended generalized Feistel networks using matrix representation, in Selected Areas in Cryptography — SAC 2013, Proc. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013) (Springer, Heidelberg, 2014), pp. 289–305 (Lect. Notes Comput. Sci., Vol. 8282).
     
  8. R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory 14 (4), 483–499 (1990).
     
  9. Y. Huang and B. Liu, Generalized r-exponents of primitive digraphs, Taiwan. J. Math. 15 (5), 1999–2012 (2011). 
     
  10. B. Liu, Generalized exponents of Boolean matrices, Lin. Algebra Appl. 373, 169–182 (2003).
     
  11. Z. Miao and K. Zhang, The local exponent sets of primitive digraphs, Lin. Algebra Appl. 307, 15–33 (2000).
     
  12. J. Shen and S. Neufeld, Local exponents of primitive digraphs, Lin. Algebra Appl. 268, 117–129 (1998).
     
  13. T. Suzaki and K. Minematsu, Improving the generalized Feistel, in Fast Software Encryption, Proc. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010) (Springer, Heidelberg, 2010), pp. 19–39 (Lect. Notes Comput. Sci., Vol. 6147).
     
  14. H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52, 642–648 (1950). [German].
     
  15. P. Perkins, A theorem on regular graphs, Pac. J. Math. 2, 1529–1533 (1961).
     
  16. A. L. Dulmage and N. S. Mendelsohn, The exponent of a primitive matrix, Can. Math. Bull. 5 (3), 241–244 (1962).
     
  17. S. W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Lin. Algebra Appl. 245, 27–47 (1996).
     
  18. K. Nyberg, Generalized Feistel networks, in Advances in Cryptology — ASIACRYPT’96, Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (Kyongju, Korea, Nov. 3–7, 1996) (Springer, Heidelberg, 1996), pp. 91–104 (Lect. Notes Comput. Sci., Vol. 1163).