Theoretical Backgrounds of Applied Discrete Mathematics
Characterization of APN-permutations in terms of Hamming distance between subgroups of symmetric group
A. R. Belov P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
Abstract:
In the paper, we give a characterization of APN-permutations in terms of the Hamming distance between subgroups of the symmetric group. Let
$$T = \{ \tau_\alpha \in S(\mathbb{F}_{2^n}): \alpha \in \mathbb{F}_{2^n} \& \forall x \in \mathbb{F}_{2^n} (\tau_\alpha(x) = x + \alpha)\}.$$
Then permutation
$\pi \in S(\mathbb{F}_{2^n})$ is APN if and only if
$\text{d}(T, T') = 2^n-2$, where
$T' = \pi^{-1} \cdot T \cdot \pi$ and
$\text{d}(T, T')$ is the Hamming distance between subgroups
$T, T' \leq S(\mathbb{F}_{2^n})$. Using this characterization, a new approach to the construction of APN-permutations is proposed: the problem of constructing an APN-permutation is reduced to finding a suitable group
$T'$ and solving the simultaneous conjugation problem
$T = x^{-1} \cdot T' \cdot x$. To find suitable groups
$T'$, a combinatorial approach is used, which consists in constructing some graph
$G(T)$ associated with the group
$T$ and searching in that graph for a maximum independent sets. Let $T' = \langle\tau_1, \tau_2, \ldots, \tau_n\rangle$. Then
$\text{d}(\langle\tau_i\rangle, T) = 2^n-2$ if and only if a set of transpositions in decomposition of
$\tau_i$ is a maximum independent set in
$G(T)$. We have listed all maximum independent sets in the graph
$G(T)$ associated with the translation group
$T$ of the field
$\mathbb{F}_{2^4}$. In this case the group
$T'$ cannot be constructed. Thus we have obtained the well-known result about the non-existence of APN permutations in
$\mathbb{F}_{2^4}$. APN-permutations in the field
$\mathbb{F}_{2^3}$ are classified by listing all possible candidates for the group
$T'$: there are 8 possible groups.
Keywords:
APN mapping, permutation, symmetric group, Hamming distance, simultaneous conjugacy.
UDC:
519.7
DOI:
10.17223/20710410/60/1