On constructing APN permutations using subfunctions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/2

Our subject for investigation is the problem of APN permutation existence for even number of variables. In this work, we consider 2-to-1 functions that are isomorphic to (n - 1)-subfunctions of APN permutations. These 2-to-1 functions can be obtained with a special algorithm which searches for 2-to-1 APN functions that are potentially EA-equivalent to permutations. The algorithm is based on constructing special symbol sequences that are called admissible. It is known that (n - 1)-subfunction of an APN permutation can be represented as a differentially 4-uniform 2-to-1 function that takes values from the half of the Boolean cube. Therefore, the following algorithm can be used to search for APN permutations. On the first step all the possible admissible sequences are constructed and we assign obtained sequences in order to find a differentially 4-uniform 2-to-1 function. Therefore, obtained function can be isomorphic to a (n - 1)-subfunction of an APN permutation, so, this (n - 1)-subfunction can be expanded to bijective APN function. In order to construct an APN permutation, we need to find all possible coordinate Boolean functions f such that the bijective function constructed from the given (n - 1)-subfunction S and function f is APN. Unfortunately, the exhaustive search through the set of potential coordinate functions is computationally hard when n ^ 7, so, we need to estimate the number n(S) of such coordinate Boolean functions. For a given bijective vectorial function F, we introduce an associated permutation F* as follows. We split the set Fn into two disjoint subsets F₁ and F₂, fix integer k, indices i₁,..., i_k, and index j £ {i₁,..., i_k}. Then the value F*(x) is equal to F(x) if F(x) £ F₁ and F*(x) is equal to F(x) + ej otherwise. We prove that F^* is an APN permutation if and only if F is an APN permutation. This fact allows us to obtain the necessary bound. We prove that if n(S) is not equal to zero, then n(S) ^ 2ⁿ.