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

Bibliographie

[1] Gorodilova A. A., “From cryptanalysis to cryptographic property of a Boolean function”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 16–44 (in Russian) | MR | Zbl

[2] Hou X.-D., “Affinity of permutations of $F^n_2$”, Discr. Appl. Math., 154, Special Issue: Coding and Cryptography Archive (2006), 313–325 | DOI | Zbl

[3] McQuistan M. T., Wolfe A. J., Browning K. A., and Dillon J. F., “An apn permutation in dimension six”, Amer. Math. Soc., 2010, no. 518, 33–42 | MR | Zbl

[4] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, Uchebnik, 2-e izd., ispr. i dop., Lan, SPb., 2015, 608 pp.

[5] Fontet M., “Calcul de Centralisateur d'un Grupe de Permutatations”, Bull. Soc. Math. France Mem., 1977, no. 49–50, 53–63 | MR | Zbl

[6] Sridhar M. A., “A fast algorithm for testing isomorphism of permutation networks”, IEEE Trans. Computers, 38:6 (1989), 903–909 | DOI | MR | Zbl

[7] Brodnik A., Malnic̆ A., and Poz̆ar R., The Simultaneous Conjugacy Problem in the Symmetric Group, 2020, arXiv: 1907.07889 | MR

[8] Tsukiyama S., Ide M., Ariyoshi H., and Shirakawa I., “A new algorithm for generating all the maximal independent sets”, SIAM J. Comput., 1977, no. 6, 505–517 | DOI | MR | Zbl

[9] Zhao Y., “The number of independent sets in a regular graph”, Combinatorics, Probability and Computing, 19 (2010), 315–320 | DOI | MR | Zbl