Paper 2023/928

On vectorial functions mapping strict affine subspaces of their domain into strict affine subspaces of their co-domain, and the strong D-property

Abstract

Given three positive integers $n<N$ and $M$, we study those functions $\mathcal{F}$ from the vector space $\mathbb{F}_2^N$ (possibly endowed with the field structure) to $\mathbb{F}_2^M$, which map at least one $n$-dimensional affine subspace of $\mathbb{F}_2^N$ into an affine subspace whose dimension is less than $M$, possibly equal to $n$. This provides functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$ for some $m$ (and in some cases, permutations) that have a simple representation over $\mathbb{F}_2^N$ or over $\mathbb{F}_{2^N}$. We show that the nonlinearity of $\mathcal{F}$ must not be too large for allowing this and we observe that if it is zero, there automatically exists a strict affine subspace of its domain that is mapped by $\mathcal{F}$ into a strict affine subspace of its co-domain. In this case, we show that the nonlinearity of the restriction may be large. We study the other cryptographic properties of such restriction, viewed as an $(n,m)$-function (resp. an $(n,n)$-permutation). We then focus on the case of an $(N,N)$-function $\mathcal{F}$ of the form $\psi(\mathcal{G}(x))$ where $\mathcal{G}$ is almost perfect nonlinear (APN) and $\psi$ is a linear function with a kernel of dimension $1.$ We observe that the restriction of $\mathcal{G}$ to an affine hyperplane $A$ has the D-property (introduced by Taniguchi after a result from Dillon) as an $(N-1,N)$-function, if and only if, for every such $\psi$, the restriction of $\mathcal{F}(x)=\psi(\mathcal{G}(x))$ to $A$ is not an APN $(N-1,N-1)$-function. If this holds for all affine hyperplanes $A,$ we say that $\mathcal{G}$ has the strong D-property. We note that not satisfying this cryptographically interesting property also has a positive aspect, since it allows to construct APN $(N-1,N-1)$-functions from $\mathcal{G}$. We give a characterization of the strong D-property for crooked functions (a particular case of APN functions) by means of their ortho-derivatives and we prove that the Gold APN function in dimension $N\geq 9$ odd does have the strong D-property (we also give a simpler proof that the strong D-property of the Gold APN function in even dimension $N\geq 6$ holds if and only if $N=6$ or $N\geq 8$). Then we give a partial result on the Dobbertin APN power function, and on this basis, we conjecture that it has the strong D-property as well. We then move our focus to two known infinite families of differentially 4-uniform $(N-1,N-1)$-permuta\-tions constructed as the restrictions of $(N,N)$-functions $\mathcal{F}(x)=\psi(\mathcal{G}(x))$ or $\mathcal{F}(x)=\psi(\mathcal{G}(x))+x$ where $\psi$ and $\mathcal{G}$ are as before, with the extra hypothesis that $\mathcal{G}$ is an APN permutation. After a deeper investigation on these classes, we provide proofs (which were missing) that they are not APN in dimension $n=N-1$ even.