Volume 27, No 4, 2020, P. 131-151

UDC 519.17
V. M. Fomichev
Estimating nonlinearity characteristics for iterative transformations of a vector space

Abstract:
We present theoretical foundations for the matrix-graphic approach (MGA) to the estimation of characteristics of the sets of essential and nonlinear variables of the composition of transformations of an $n$-dimensional vector space over a field. The ternary nonlinearity matrix corresponds to a transformation, where the $i$th row and the $j$th column of the matrix contain 0, 1, or 2 if and only if the $j$th coordinate function of the transformation depends on the $i$th variable fictitiously, or linearly, or nonlinearly, $0 \le i$, $j < n$. MGA is based on the inequality according to which the nonlinearity matrix of the product of transformations is at most (the inequality is elementwise) the product of the nonlinearity matrices of the transformations.
We define the multiplication for ternary matrices. The properties are studied of the multiplicative monoid of all ternary matrices of order $n$ without zero rows and columns and of the monoid $\mathbb \Gamma_n$ bijectively corresponding to it of all $n$-vertex digraphs with edges labeled with 0, 1, and 2, where each vertex has nonzero indegree and outdegree. The iteration depth (number of multipliers) for transformations is estimated with the use of MGA in which the four types of the nonlinearity of transformations can be achieved, where each or some of the coordinate functions of the product of transformations can depend nonlinearly on all or at least some variables.
We present the results of research on the nonlinearity of iterations of round substitution of the block ciphers DES and “Magma”.
Bibliogr. 18.

Keywords: nonlinearity matrix (digraph) of a transformation, $\left \langle {\alpha} \right \rangle$-primitive matrix (digraph), $\left \langle {\alpha} \right \rangle$-exponent of a matrix (of a digraph), perfective transformation.

DOI: 10.33048/daio.2020.27.686

Vladimir M. Fomichev ^1,2,3
1. Financial University under the Government of Russian Federation,
49 Leningradsky Avenue, 125993 Moscow, Russia
2. National Research Nuclear University MEPhI,
31 Kashirskoe Highway, 115409 Moscow, Russia
3. Institute of Informatics Problems of FRC CSC RAS,
44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
e-mail: fomichev.2016@yandex.ru

Received May 5, 2020
Revised May 28, 2020
Accepted June 2, 2020

References

[1] V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices (TVP, Moscow, 2000 [Russian]; AMS, Providence, 2002).

[2] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology (Dialog-MIFI, Moscow, 2010) [Russian].

[3] V. M. Fomichev and D. A. Melnikov, Cryptographic Methods of Information Security (YURAYT, Moscow, 2016) [Russian].

[4] V. M. Fomichev, Ya. Eh. 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)].

[5] G. Frobenius, Über Matrizen aus nicht negativen Elementen, Berl. Ber., 456–477 (1912) [German].

[6] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52, 642–648 (1950) [German].

[7] P. Perkins, A theorem on regular graphs, Pac. J. Math. 2, 1529–1533 (1961).

[8] A. L. Dulmage and N. S. Mendelsohn, The exponent of a primitive matrix, Canad. Math. Bull. 5, 241–244 (1962).

[9] A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Ill. J. Math. 8 (4), 642–656 (1964).

[10] R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory 14 (4), 483–499 (1990).

[11] S. W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Linear Algebra Appl. 245, 27–47 (1996).

[12] B. Liu, Generalized exponents of Boolean matrices, Linear Algebra Appl. 373, 169–182 (2003).

[13] K. Nyberg, Generalized Feistel networks, in Advances in Cryptology – ASIA-CRYPT’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).

[14] 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).

[15] T. 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).

[16] 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).

[17] V. M. Fomichev, A. M. Koreneva, A. R. Miftakhutdinova, and D. I. Zadorozhny, Evaluation of the maximum performance of block encryption algorithms, Mat. Vopr. Kriptogr. 10 (2), 181–190 (2019).

[18] V. M. Fomichev and A. M. Koreneva, Encryption performance and security of certain wide block ciphers, J. Comput. Virol. Hack. Tech. (2020). Available at https://link.springer.com/article/10.1007/s11416-020-00351-1 (accessed June 5, 2020).