RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2016 Number 4(34), Pages 5–16 (Mi pdm561)

This article is cited in 4 papers

Theoretical Backgrounds of Applied Discrete Mathematics

The linear spectrum of quadratic APN functions

A. A. Gorodilova

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: 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.

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

UDC: 519.7

DOI: 10.17223/20710410/34/1



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024