Geodesic
New bounds on the nonlinearity of PN and APN functions over finite fields
Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 45-59

Voir la notice de l'article provenant de la source Math-Net.Ru

The nonlinearity of a vectorial function over a finite field is defined here as the Hamming distance from it to the set of affine mappings in the space of values of all vectorial functions. For an arbitrary field of $q$ elements, lower bounds on the nonlinearity of PN and APN functions of $n$ variables are obtained, equal to $q^n - \sqrt { q^n - 3 \cdot 2^{-2}} - 2^{-1}$ and $q^n - \sqrt { 2q^n - 7 \cdot 2^{-2}} - 2^{-1}$ respectively, and improving the previously known bounds for the Boolean case. It is shown that the quantity $q^n - n - 1$ can be used as an upper bound on the nonlinearity of such functions. For $q = 2,3,4$, the exact values of the nonlinearity PN and APN of functions in small dimension are obtained.
Keywords: finite field, vectorial function, PN function, APN functions, nonlinearity, EA-equivalence. 
@article{DM_2023_35_3_a4,
     author = {V. G. Ryabov},
     title = {New bounds on the nonlinearity of {PN} and {APN} functions over finite fields},
     journal = {Diskretnaya Matematika},
     pages = {45--59},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_3_a4/}
}
TY  - JOUR
AU  - V. G. Ryabov
TI  - New bounds on the nonlinearity of PN and APN functions over finite fields
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 45
EP  - 59
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_3_a4/
LA  - ru
ID  - DM_2023_35_3_a4
ER  - 
%0 Journal Article
%A V. G. Ryabov
%T New bounds on the nonlinearity of PN and APN functions over finite fields
%J Diskretnaya Matematika
%D 2023
%P 45-59
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_3_a4/
%G ru
%F DM_2023_35_3_a4
V. G. Ryabov. New bounds on the nonlinearity of PN and APN functions over finite fields. Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 45-59. http://geodesic.mathdoc.fr/item/DM_2023_35_3_a4/