Mathematical Methods of Cryptography

On primitivity of mixing digraphs associated with $2$-feedbacks shift registers

A. M. Koreneva

National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Moscow, Russia

Abstract: Analysis of mixing properties of round transformations is an important issue in the theory of symmetric iterative block ciphers. For researching this subject, a matrix-digraph approach is widely used in cryptography. This approach allows to characterize the required properties in terms of primitivity and exponent of a matrix (or a digraph) related to the transformations concerned. This paper is devoted to such a characterization of mixing properties of transformations fulfilled by $2$-feedback shift registers. For naturals $n,m$, and $r$, let $n>1$, $r>1$, $0\leq m\leq n-2$, $V_r=(\mathrm{GF}(2))^r$; $f_m\colon V_r^n\to V_r$ and $f_{n-1}\colon V_r^n\to V_r$ are some feedback functions; $\mu\colon V_r\to V_r$ and $g\colon V_r\to V_r$ are some permutations over $V_r$ used to modify feedbacks $f_m$ and $f_{n-1}$ respectively; $x_{\delta_0},x_{\delta_1},\dots,x_{\delta_p}$ are all essential variables of the function $f_m(x_0,x_1,\dots,x_{n-1})$, $\delta_0=m+1$, $0<\delta_1<\dots<\delta_p<n$, $p>0$; $x_{d_0},x_{d_1},\dots,x_{d_q}$ are all essential variables of the function $f_{n-1}(x_0,x_1,\dots,x_{n-1})$, $d_0=0$, $d_1<\dots<d_q<n$, $q>0$; $\varphi^{g,\mu}\colon V_r^n\to V_r^n$, $\varphi^{g,\mu}(x_0,x_1,\dots,x_{n-1})=(x_1,\dots,x_{m-1},\mu(f_m(x_0,\dots,x_{n-1})),x_{m+1},\dots,x_{n-2},g(f_{n-1}(x_0,\dots,x_{n-1})))$. In fact, $\varphi^{g,\mu}$ is the transition function of a shift register of the length $n$ over $V_r$ with two feedback functions $\mu(f_m(x))$ and $g(f_{n-1}(x))$, $x=x_0x_1\dots x_{n-1}$. Let $M(\varphi^{g,\mu})=M$ be a Boolean matrix $(m_{ij})$ (called the mixing matrix of the map $\varphi^{g,\mu})$, where $m_{ij}=1$ iff the $j$-th coordinate function of the map $\varphi^{g,\mu}$ essentially depends on the variable $x_i$ $(i,j\in\{0,1,\dots,n-1\})$. The matrix $M$ is said to be primitive if there is a power $M^e=\left(m_{ij}^{(e)}\right)$ of its mixing matrix $M$ such that $m_{ij}^{(e)}>0$ for all $i$ and $j$; in this case, the least power $e$ is called an exponent of $M$ and is denoted by $\exp M$. The conceptions of the primitiveness and exponent of the matrix $M(\varphi^{g,\mu})$ expend to the digraph $\Gamma(\varphi^{g,\mu})$ with the adjacency matrix $M$ – the mixing graph associated with $\varphi^{g,\mu}$. The main results of the paper are the following: 1) it is proved that the strongly connected digraph $\Gamma(\varphi^{g,\mu})$ is primitive iff $\delta_1>m$ and the numbers in the set $L'=\{n-d_i,\ n+m+1-d_j-\delta_k\colon i=0,\dots,q,\ j=0,\dots,t,\ k=1,\dots,p\}$ are relatively prime or $\delta_1\leq m$ and the numbers in the set $L=\{n-d_i,\ n+m+1-d_j-\delta_k,\ m+1-\delta_l\colon i=0,\dots,q,\ j=0,\dots,t,\ k=\tau+1,\dots,p,\ l=1,\dots,\tau\}$ are relatively prime, where $t$ and $\tau$ are determined by the conditions: $d_t$ and $\delta_\tau$ are the largest numbers in $D=\{d_0,\dots,d_q\}$ and $\Delta=\{\delta_0,\dots,\delta_p\}$ with the properties $d_t\leq m$ and $\delta_\tau\leq m$ respectively; 2) for $\exp\Gamma(\varphi^{g,\mu})$, some attainable upper bounds depending on $m$ and other parameters in $D$ and $\Delta$ are obtained, improving all the known exponent estimates for the same digraphs. Particularly, if $(n-1)\in D$ and $m\in\Delta$, then $\exp\Gamma(\varphi^{g,\mu})\le\min\{\rho(D)+\varepsilon,\rho(\Delta)+\varepsilon'\}$, where $\rho(D)=\max\{n-d_q,d_q-d_{q-1},\dots,d_1-d_0\}$, $\rho(\Delta)=\max\{\delta_1+n-\delta_p,\delta_p-\delta_{p-1},\dots,\delta_0-\delta_r,\dots,\delta_2-\delta_1\}$, $\varepsilon=\max\{2n-m-2-d_q,n+m-\max\{\delta_0,\delta_p\}\}$, and $\varepsilon'=\max\{2m+1-\delta_\tau,n-1-d_t\}$. These results can be successfully used in construction of iterative cryptographic algorithms based on $\varphi^{g,\mu}$ with the rapid input data mixing.

Keywords: primitive digraph, exponent, mixing digraph, multi-feedback shift register, modified additive generator.

UDC: 519.17

DOI: 10.17223/20710410/37/3

Bibliographic databases:

•