Welcome to the resource topic for 2023/928
Title:
Restricting vectorial functions to affine spaces and deducing infinite families of 4-uniform permutations, in relation to the strong D-property
Authors: Claude Carlet, Enrico Piccione
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 to a subset of an affine subspace of dimension n, or at least of a dimension less than M. 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 that if it is zero, there automatically exists a strict affine subspace of its domain that is mapped by \mathcal{F} into a subset of 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} equal to \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 will build upon the follow fact: the restriction of \mathcal{G} over 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)) over 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. The fact of not satisfying this nice property is also positive in a way since it allows to construct a number of APN (N-1,N-1)-functions from \mathcal{G}. We give a characterization of the strong D-property for crooked 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. Completing a result from Taniguchi for N\geq 6 even, we can prove that the strong D-property of the Gold APN function in dimension N 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. We then move our focus to infinite families of (N-1,N-1)-permutations constructed as the restriction 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 but with the extra hypothesis that \mathcal{G} is an APN permutation. There are in the literature two families of differentially 4-uniform permutations corresponding to this framework, but no proof was given that they are not APN. We investigate these constructions deeply and prove that they do not produce APN permutations in dimension n=N-1 even. We present our own construction and we show a relation between infinite families of APN (N,N)-permutations and infinite families of 4-uniform (N-1,N-1)-permutations. This gives a deeper understanding on the problem of constructing infinite families of APN permutations in even dimension (for trying to solve the so-called big APN problem) with the method explored in this paper. This problem is also related to the strong D-property and we conjecture that some classes of APN power permutations have such property in dimension large enough. We show that only few APN permutations do not have the strong D-property (and this happens only for small dimension). Our construction gives many families of 4-uniform (N-1,N-1)-permutations with high nonlinearity that are additionally, under some conditions, complete permutations.
ePrint: https://eprint.iacr.org/2023/928
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .