TY - JOUR

T1 - On constructing APN permutations using subfunctions

AU - Idrisova, V. A.

PY - 2018/9

Y1 - 2018/9

N2 - 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

AB - 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

KW - APN function

KW - Permutation

KW - Subfunction

KW - Vectorial function

KW - SEQUENCES

KW - subfunction

KW - PERFECT

KW - PROOF

KW - WELCH

KW - CROSS-CORRELATION

KW - vectorial function

KW - permutation

UR - http://www.scopus.com/inward/record.url?scp=85057981498&partnerID=8YFLogxK

U2 - 10.17223/20710410/41/2

DO - 10.17223/20710410/41/2

M3 - Article

AN - SCOPUS:85057981498

SP - 17

EP - 27

JO - Прикладная дискретная математика

JF - Прикладная дискретная математика

SN - 2071-0410

IS - 41

ER -