The linear spectrum of quadratic APN functions

A. A. Gorodilova

Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 5-16

Résumé

Almost perfect nonlinear (APN) functions are studied. We introduce the linear spectrum $\Lambda^F = (\lambda_0^F, \ldots, \lambda_{2^n-1}^F)$ of a quadratic APN function $F$, where $\lambda_k^F$ equals the number of linear functions $L$ such that $|\{a\in\mathbb{F}_2^n\setminus\{\mathbf{0}\}: B_a(F) = B_a(F+L)\}| = k$ and $B_a(F) = \{F(x)+F(x+a): x\in\mathbb{F}_2^n\}$. We prove that $\lambda_k^F=0$ for all even $k \leqslant 2^n-2$ and for all $k(2^n-1)/3$, where $F$ is a quadratic APN function in even number of variables $n$. Linear spectra for APN functions in small number of variables $n=3,4,5,6$ are computed and presented. We consider APN Gold functions $F(x)=x^{2^k+1}$ for $(k,n)=1$ and prove that $\lambda^F_{2^n-1}=2^{n+n/2}$ if $n=4t$ for some $t$ and $k = n/2 \pm 1$, and $\lambda^F_{2^n-1} = 2^{n}$ otherwise.

Détail

Keywords: APN function, associated Boolean function, linear spectrum, Gold function.