$\langle 2\rangle$-exponents of shift register transformations nonlinearity dipgraphs

V. M. Fomichev ; V. M. Bobrov

Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 77-87.

Résumé

The matrix-graph approach is used to estimate sets of essential and non-linear variables of coordinate functions of the vector space transformations product. Estimates are obtained by multiplying binary mixing matrices or digraphs of multiplied transformations in the case of the set of essential variables, or by multiplying ternary nonlinearity matrices or corresponding nonlinearity digraphs with the arcs marked by numbers from the set $\{0, 1, 2\}$. For powers of a given transformation the non-trivial estimates domain is limited by the mixing matrix (digraph) exponent in the case of the essential variables and by the nonlinearity matrix (digraph) $\langle 2\rangle$-exponent in the case of the nonlinear variables. Let $f(x_0,\dots,x_{n-1})$ be the feedback function of shift register, $D=\{d_0,\dots,d_m\}$ be the set of its essential variables (registers extraction points), $1$, $0=d_0$, $E=\{e_0,\dots,e_l\}$ be the set of its nonlinear variables (registers nonlinear extraction points), $1$, $e_0$, and shift register transformation nonlinearity digraph $G$ be $\langle 2\rangle$-primitive. Then $\langle 2\rangle$-exponent of $G$ is not greater than $F(L)+1+n+\Delta_f$, where $F(L)$ is a Frobenius number of the set $L$ of the lengths of all digraph simple circuits, $\Delta_f=\max_{i\in D^0\cup D^1}\mu(i-1)$, \begin{gather*} \mu(u)= \begin{cases} \min\{u-e(u),u-d(u)+n-e_l\}, e_0\leq u; \\ u-d(u)+n-e_l, 0\leq u, \\ \end{cases}\\ D^0=\{d_s\in D, 1\leq s\leq m: d_{s-1}-e(d_{s-1})\leq\lambda, e_0\leq d_{s-1}\}\cup S_0(n), \\ D^1=\{d_s\in D, 1\leq s\leq m: 0\leq d_{s-1}\text{or} d_{s-1}-e(d_{s-1})>\lambda\}\cup S_1(n), \end{gather*} where $d(u)$ is the greatest number of $D$ such that $d(u)\leq u$, $0\leq u$; $e(u)$ is the greatest number of $E$ such that $e(u)\leq u$, $e_0\leq u$; $S_0(n)=S_1(n)=\emptyset$, if $d_m=n-1$; $S_0(n)=\{n\}$, if $d_m$ and $d_m\in E$; and $S_1(n)=\{n\}$, if $d_m$ and $d_m\in E$. In the case of the variable $x_{n–1}$ being essential for the function $f(x_0,\ldots,x_{n–1})$, the exact formula for the $\langle 2\rangle$-exponent of the nonlinearity digraph has been derived. Calculation examples are presented. The results can be used to estimate the nonlinearity characteristics of cryptographic functions constructed from iterated register transformations.

Détail

Keywords: shift register transformation, nonlinearity digraph, $\langle2\rangle$-primitivity, local $\langle2\rangle$-primitivity, $\langle2\rangle$-exponent of digraph, local $\langle2\rangle$-exponent of digraph.

Bibliographie

[1] V. M. Fomichev, E. Avezova Ya, A. M. Koreneva, S. N. Kyazhin, “Primitivnost i lokalnaya primitivnost orgrafov i neotritsatelnykh matrits”, Diskretnyi analiz i issledovanie operatsii, 25:3 (2018), 95–125 | MR | Zbl

[2] G. Frobenius, “Uber Matrizen aus nicht negativen Elementen”, Sitzungsber K. Preuss. Akad. Wiss. Berlin, 1912, 456–477 | Zbl

[3] A. L. Dulmage, N. S. Mendelsohn, “The exponent of a primitive matrix”, Canadian Math. Bull., 1962, no. 5, 241–244 | DOI | MR | Zbl

[4] P. Perkins, “A theorem on regular graphs”, Pacific J. Math., 2 (1961), 1529–1533 | DOI | MR

[5] V. M. Fomichev, “Otsenka kharakteristik nelineinosti iterativnykh preobrazovanii vektornogo prostranstva”, Diskretnyi analiz i issledovanie operatsii, 27:4 (2020), 131–151 | MR

[6] V. M. Fomichev, A. M. Koreneva, “Encryption performance and security of certain wide block ciphers”, J. Computer Virology Hacking Tech., 16:1 (2020), 197–216 | DOI

[7] V. M. Fomichev, Ya. E. Avezova, “Tochnaya formula eksponentov peremeshivayuschikh orgrafov registrovykh preobrazovanii”, Diskretnyi analiz i issledovanie operatsii, 27:2 (2020), 117–135 | MR

[8] V. M. Fomichev, V. M. Bobrov, “Otsenka s pomoschyu matrichno-grafovogo podkhoda kharakteristik lokalnoi nelineinosti iteratsii preobrazovanii vektornykh prostranstv”, Prikladnaya diksretnaya matematika. Prilozhenie, 2019, no. 12, 32–35