Invariant subspaces in SPN block cipher

D. I. Trifonov ; D. B. Fomin

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 58-76

Résumé

Let there exist subsets of $\mathbb{F}_2^n$ that the non-linear layer of an SP-network maps to some other subset of $\mathbb{F}_2^n$. We study the possibility of existence of subsets of $\mathbb{F}_2^n$ that are invariant under the SP-layer. It is shown that subspaces invariant under nonlinear transformations from some classes are not preserved by any matrix without nonzero elements of the field extension $\mathbb{F}_2$. The paper also studies the question of the existence of invariant subsets of the form $A_{i_1} \times \ldots \times A_{i_m}$, where $n = m \cdot n’$, $A_{i_j} \subseteq \mathbb{F}_2^{n’}$, $j = 1, \ldots, m$. Some properties of such invariant sets of the round function of the SP-layer are proved on the basis of the graph-theoretic and group-theoretic approaches. We study the capacity of these sets and, using additional assumptions, show that $A_{i_j}$, $j = 1, \ldots,m$, should be cosets of some subspaces of $\left(\mathbb{F}_2^{n’}, +\right)$ of equal size. A constructive way of constructing such sets is proposed.

Détail

Keywords: SP-network, SPN, invariant subspaces.