On constructing APN permutations using subfunctions

V. A. Idrisova

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование


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 2 into two disjoint subsets F1 and F2, fix integer k, indices i1, . . ., ik, and index j 6∈ {i1, . . ., ik}. Then the value F?(x) is equal to F(x) if F(x) ∈ F1 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) > 2n

Язык оригиналаанглийский
Страницы (с-по)17-27
Число страниц11
ЖурналПрикладная дискретная математика
Номер выпуска41
СостояниеОпубликовано - сен 2018

Fingerprint Подробные сведения о темах исследования «On constructing APN permutations using subfunctions». Вместе они формируют уникальный семантический отпечаток (fingerprint).