Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions

Abstract

We say an $(n,n)$-function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ is a crooked function if for any nonzero $a\in {\mathbb{F}}_2^n$, the image of $D_{a}F(x)=F(x)+F(x+a)$ is an affine hyperplane. The only known examples of crooked functions are all quadratic almost perfect nonlinear (APN), or equivalently, for every known crooked function, $D_{a}F$ is affine for all $a\in {\mathbb{F}}_2^n$. The ortho-derivative ${\pi }_F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ of a crooked function $F$ is the function such that ${\pi }_F(0)=0$, and for any nonzero $a$, the set $\{0,{\pi }_F(a){\}}^{\perp }$ is the underlying vector space of $\mathrm{Im}(D_{a}F)$. We prove that for $n\ge 4$ and a crooked function $F$, if $k$ is a non-negative integer such that $F$ has $2^k-1$ quadratic component functions, ${\pi }_F$ has at least $2^n-2^{n-k}$ component functions of algebraic degree $n-2$. In particular, we resolve Gorodilova's conjecture that every component function of ${\pi }_F$ has algebraic degree $n-2$ when $F$ is quadratic APN. As a second main result, for $n\ge 4$, we associate to a crooked function $F$ a quadratic function ${\epsilon }_F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ that satisfies a strong geometric-combinatorial condition regarding the sums of $F$ over $2$-dimensional linear subspaces. As a corollary to both of our main results, we prove that for any even $n\ge 4$, any quadratic APN $(n,n)$-function has at least $n$ semi-bent components. Furthermore, we obtain a congruence result on a problem on $m$-sequences introduced by Johansen, Helleseth, and Kholosha, and we determine the exact algebraic degrees of some Boolean functions associated to the bent and near-bent components of particular classes of plateaued vectorial functions.

40 pages