Trims and Extensions of Quadratic APN Functions

Abstract

In this work, we study functions that can be obtained by restricting a vectorial Boolean function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ to an affine hyperplane of dimension $n-1$ and then projecting the output to an $n-1$-dimensional space. We show that a multiset of $2\cdot (2^n-1{)}^2$ EA-equivalence classes of such restrictions defines an EA-invariant for vectorial Boolean functions on ${\mathbb{F}}_2^n$. Further, for all of the known quadratic APN functions in dimension $n<10$, we determine the restrictions that are also APN. Moreover, we construct 6,368 new quadratic APN functions in dimension eight up to EA-equivalence by extending a quadratic APN function in dimension seven. A special focus of this work is on quadratic APN functions with maximum linearity. In particular, we characterize a quadratic APN function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ with linearity of $2^{n-1}$ by a property of the ortho-derivative of its restriction to a linear hyperplane. Using the fact that all quadratic APN functions in dimension seven are classified, we are able to obtain a classification of all quadratic 8-bit APN functions with linearity $2^7$ up to EA-equivalence.

References in corpus (2)

• New Instances of Quadratic APN Functions
• Linearly Self-Equivalent APN Permutations in Small Dimension

Cited by in corpus (1)

• Gold Functions and Switched Cube Functions Are Not 0-Extendable in Dimension $n>5$