On constructing APN permutations using subfunctions

V. A. Idrisova

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish
Pages (from-to)17-27
Number of pages11
JournalПрикладная дискретная математика
Issue number41
DOIs
Publication statusPublished - Sep 2018

Keywords

  • APN function
  • Permutation
  • Subfunction
  • Vectorial function
  • SEQUENCES
  • subfunction
  • PERFECT
  • PROOF
  • WELCH
  • CROSS-CORRELATION
  • vectorial function
  • permutation

Fingerprint

Dive into the research topics of 'On constructing APN permutations using subfunctions'. Together they form a unique fingerprint.

Cite this