On permutations that break subspaces of~specified~dimensions

N. A. Kolomeec

Prikladnaâ diskretnaâ matematika, no. 3 (2024), pp. 5-20

Résumé

We consider the sets $\mathcal{P}_{n}^{k}$ consisting of invertible functions $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ such that any $U \subseteq \mathbb{F}_2^n$ and its image $F(U)$ are not simultaneously $k$-dimensional affine subspaces of $\mathbb{F}_2^n$, where $3 \leq k \leq n - 1$. We present lower bounds for the cardinalities of all such $\mathcal{P}_{n}^{k}$ and $\mathcal{P}_{n}^{k} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that improve the result of W. E. Clark, X. Hou, and A. Mihailovs, 2007, providing that these sets are not empty. We prove that almost all permutations of $\mathbb{F}_2^n$ belong to $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$. Asymptotic lower and upper bounds of $|\mathcal{P}_{n}^{3}|$ up to $o(2^n!)$ are obtained: $o(1) \leq |\mathcal{P}_{n}^{3}|/2^n! - (1 - \rho) \leq \rho^2/2 + o(1)$, where $\rho = 5/224$. They are correct for $|\mathcal{P}_{n}^{3} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}|$ as well. The number of functions from $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that map exactly one $3$-dimensional affine subspace of $\mathbb{F}_2^n$ to an affine subspace is estimated. The connection between the restrictions of component functions of $F$ and the case when both $U$ and $F(U)$ are affine subspaces of $\mathbb{F}_2^n$ is obtained. The characterization of differentially 4-uniform permutations in the mentioned terms is provided.

Détail

Keywords: affine subspaces, asymptotic bounds, nonlinearity, differential uniformity, APN functions.