Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This work establishes tightened theoretical upper bounds on the linearity and ranked Walsh spectrum of Almost Perfect Nonlinear (APN) functions over $\mathbb{F}_2^n$. The authors prove that maximum linearity cannot exceed $N-10$ in even dimensions (and $N-6$ in odd), establish an asymptotic $N/\sqrt{k}$ decay rate for the $k$-th largest Walsh coefficient, and relate linearity directly to the count of nonplateaued components. These findings significantly restrict the admissible spectral distributions of APN functions, directly impacting the classification and construction of highly secure cryptographic primitives.
APN functions cannot hide near-maximal linear correlations: their worst-case Walsh coefficients are strictly bounded below $N-10$, with higher-order spectral peaks decaying at a sharp $O(N/\sqrt{k})$ rate.
For $n\ge5$, let $F\colon\mathbb{F}_2^n\to \mathbb{F}_2^n$ be almost perfect nonlinear and write $N=2^n$. It is proven that the linearity $\mathcal{L}(F)$ of $F$, i.e., the largest absolute Walsh coefficient of a nonzero component, is at most $N-10$ in even dimension and at most $N-6$ in odd dimension. This improves the general upper bound of $N-6$ in even dimension and $N-4$ in odd dimension. It is further proven that, for each fixed $k$, the $k$-th largest absolute Walsh coefficient among nonzero components, counted with multiplicity, is at most $(1+O_k(2^{-n}))N/\sqrt{k}$ as $n\to\infty$. The second and fourth largest coefficients are at most $2\lfloor N/3\rfloor$ and $N/2$, respectively. Finally, a bound on the linearity in terms of the number $q$ of nonplateaued nonzero components is derived. In odd dimension, for $q>0$, we have $\mathcal{L}(F)^2\le N(1+\sqrt{q(N-1)})$, so that $\mathcal{L}(F)/N\to1$ implies $q/N\to1$. In even dimension, for every $1/2\le C<1$, the condition $q\le(4C-C^2-1)N/4+1$ implies $\mathcal{L}(F)\le CN$. In particular, $q\le3N/16+2$ implies $\mathcal{L}(F)\le N/2$.