On lower bounds for the distances between APN functions

Abstract

Whether two distinct APN functions can have a Hamming distance of $1$ remains an open problem. In 2020, L. Budaghyan et al. introduced a new CCZ-invariant ${\hat{I}}_F$ which can be used to provide lower bounds on the Hamming distance between a given APN function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ and other APN functions. Lower bounds on the distance from an APN function $F$ to any other APN function $G$ are known when $F$ is an almost bent (AB) function or when $F$ is a $3$-to-$1$ quadratic function with $n$ even. In this paper, we reinterpret ${\hat{I}}_F$ in terms of the multiplicities of the 3-sums of the graph ${\mathcal{G}}_F=\{(x,F(x)):x\in {\mathbb{F}}_2^n\}$ of $F$ as a Sidon set, which we call exclude multiplicities. For even $n$, we establish lower bounds on the distance between $F$ and any other APN function $G$ when $F$ is plateaued APN, and we generalize a previously known lower bound for quadratic $3$-to-$1$ functions to the case where $F$ is plateaued $3$-to-$1$ (e.g., when $F$ is a Kasami function). For odd $n$, we derive new lower bounds when $F$ is the APN inverse function over ${\mathbb{F}}_{2^n}$. We also study how the exclude multiplicities of ${\mathcal{G}}_F$ are directly connected to the existence of linear structures of ${\hat{I}}_F^3$ when $F$ is plateaued APN and to the ortho-derivative when $F$ is a quadratic APN function. In particular, we prove that ${\hat{I}}_F^3$ has no nontrivial linear structures when $F$ is plateaued APN. We also use the CCZ-invariance of exclude multiplicities to prove that the Brinkmann-Leander-Edel-Pott function is not CCZ-equivalent to a plateaued function.

30 pages