Characterization of APN-permutations in terms of~Hamming distance between subgroups of~symmetric~group

A. R. Belov

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 5-12

Résumé

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.

Détail

Keywords: APN mapping, symmetric group, Hamming distance, simultaneous conjugacy.
Mots-clés : permutation