Paper 2023/928 Original: eprint.iacr.org/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 vectorial Boolean $(N,M)$-functions $\mathcal{F}$ which map an $n$-dimensional affine space $A$ into an $m$-dimensional affine space where $m<M$ and possibly $m=n$. This provides $(n,m)$-functions $\mathcal{F}_A$ as restrictions of $\mathcal{F}$. We show that the nonlinearity of $\mathcal{F}$ must not be too large for allowing this, and we observe that if it is zero, then it is always possible. In this case, we show that the nonlinearity of the restriction may be large. We then focus on the case $M=N$ and $\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 problem of determining the D-property of APN $(N-1,N)$-functions $\mathcal{G}_A$, where $A$ is a hyperplane, is related to the problem of constructing APN $(N-1,N-1)$-functions $\mathcal{F}_A$. For this reason, we introduce the strong D-property defined for $(N,N)$-functions $\mathcal{G}$. We give a characterization of this property for crooked functions and their compositional inverse (if it exists) by means of their ortho-derivatives, and we prove that the Gold APN function in dimension $N$ odd big enough has the strong D-property. We also prove in simpler a way than Taniguchi in 2023 that the strong D-property of the Gold APN function holds for $N$ even big enough. Then we give a partial result on the Dobbertin APN power function, and on the basis of this result, 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)$-permutations 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$ is linear with a kernel of dimension $1$ and $\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. Then we present our own construction by relaxing some hypothesis on $\psi$ and $\mathcal{G}$.