Geodesic
Nonlinearity of functions over finite fields
Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 110-131.

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

The nonlinearity and additive nonlinearity of a function are defined as the Hamming distances, respectively, to the set of all affine mappings and to the set of all mappings having nontrivial additive translators. On the basis of the revealed relation between the nonlinearities and the Fourier coefficients of the characters of a function, convenient formulas for nonlinearity evaluation for practically important classes of functions over an arbitrary finite field are found. In the case of a field of even characteristic, similar results were obtained for the additive nonlinearity in terms of the autocorrelation coefficients. The formulas obtained made it possible to present specific classes of functions with maximal possible and high nonlinearity and additive nonlinearity.
Keywords: nonlinearity, finite field, Fourier coefficients, autocorrelation, bent function, translator. 
@article{DM_2021_33_4_a9,
     author = {V. G. Ryabov},
     title = {Nonlinearity of functions over finite fields},
     journal = {Diskretnaya Matematika},
     pages = {110--131},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_4_a9/}
}
TY  - JOUR
AU  - V. G. Ryabov
TI  - Nonlinearity of functions over finite fields
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 110
EP  - 131
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_4_a9/
LA  - ru
ID  - DM_2021_33_4_a9
ER  - 
%0 Journal Article
%A V. G. Ryabov
%T Nonlinearity of functions over finite fields
%J Diskretnaya Matematika
%D 2021
%P 110-131
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_4_a9/
%G ru
%F DM_2021_33_4_a9
V. G. Ryabov. Nonlinearity of functions over finite fields. Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 110-131. http://geodesic.mathdoc.fr/item/DM_2021_33_4_a9/

[1] Ambrosimov A. S., “Properties of bent functions of $q$-valued logic over finite fields”, Discrete Math. Appl., 4:4 (1994), 341–350 | DOI | Zbl

[2] Ambrosimov A. S., “O priblizhenii funktsii $k$-znachnoi logiki funktsiyami iz zadannoi sistemy”, Fundamentalnaya i prikladnaya matematika, 3:3 (1997), 653–674 | Zbl

[3] Zubkov A. M., Serov A. A., “Bounds for the number of Boolean functions admitting affine approximations of a given accuracy”, Discrete Math. Appl., 20:5-6 (2010), 467–486 | DOI | Zbl

[4] Logachev O. A., Salnikov A. A., Smyshlyaev S. V., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, Lenand, Moskva, 2015, 576 pp.

[5] Ryabov V. G., “O priblizhenii ogranichenii funktsii $q$-znachnoi logiki na lineinye mnogoobraziya affinnymi analogami”, Diskretnaya matematika, 32:4 (2020), 89–102

[6] Ryabov V. G., “Maksimalno nelineinye funktsii nad konechnymi polyami”, Diskretnaya matematika, 33:1 (2021), 47–63

[7] Ryabov V. G., “Kriterii maksimalnoi nelineinosti funktsii nad konechnym polem”, Diskretnaya matematika, 33:3 (2021), 79–91

[8] Ryazanov B. V., Checheta S. I., “On the approximation of a random Boolean function by the set of quadratic forms”, Discrete Math. Appl., 5:5 (1995), 473–489 | DOI | Zbl

[9] Sachkov V. N., “Translyatory i translyatsii diskretnykh funktsii”, Trudy po diskretnoi matematike, 9 (2009), 253–268

[10] Solodovnikov V. I., “Bent functions from a finite Abelian group into a finite Abelian group”, Discrete Math. Appl., 12:2 (2002), 111–126 | DOI | Zbl

[11] Cheremushkin A. V., “Additivnyi podkhod k opredeleniyu stepeni nelineinosti diskretnoi funktsii”, Prikladnaya diskretnaya matematika, 2010, no. 2(8), 22–33 | Zbl

[12] Cheremushkin A. V., Dekompozitsiya i klassifikatsiya diskretnykh funktsii, KURS, Moskva, 2018, 288 pp.

[13] Yashchenko V. V., “On the propagation criterion for Boolean functions and on bent functions”, Problems Inform. Transmission, 33:1 (1997), 62–71 | Zbl

[14] Carlet C., “Partially-bent functions”, Designs, Codes and Cryptography, 3:2 (1993), 135–145 | DOI | Zbl

[15] Carlet C., Ding C., “Highly nonlinear mappings”, J. Complexity, 20:2-3 (2004), 205–244 | DOI | Zbl

[16] Carlet C., Mesnager S., “Four decades of research on bent functions”, Designs, Codes and Cryptography, 78:1 (2016), 5–50 | DOI | Zbl

[17] Coulter, R. S., Matthews, R. W., “Bent polynomials over finite fields”, Bull. Austral. Math. Soc., 56 (1997), 429–437 | DOI | Zbl

[18] Kumar P. V., Scholtz R. A., Welch L. R., “Generalized bent functions and their properties”, J. Comb. Theory, Ser. A, 40:1 (1985), 90–107 | DOI | Zbl

[19] Lai X., “Additive and linear structures of cryptographic functions”, Fast Software Encryption 1994, Lect. Notes Comput. Sci., 1008, 1995, 75–85 | DOI | Zbl

[20] Meier W., Staffelbach O., “Nonlinearity criteria for cryptographic functions”, EUROCRYPT' 89, Lect. Notes Comput. Sci., 434, 1990, 549–562 | DOI | Zbl

[21] Mesnager S., Özbudak F., S{\i}nak A., “Characterizations of partially bent and plateaued functions over finite fields”, Arithmetic of Finite Fields, WAIFI 2018, Lect. Notes Comput. Sci., 11321, 2018, 224–241 | DOI | Zbl

[22] Nyberg K., “Constructions of bent functions and difference sets”, EUROCRYPT' 90, Lect. Notes Comput. Sci., 473, 1991, 151–160 | DOI | Zbl

[23] Nyberg K., “On the construction of highly nonlinear permutations”, EUROCRYPT' 92, Lect. Notes Comput. Sci., 658, 1993, 92–98 | DOI | Zbl

[24] Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT' 93, Lect. Notes Comput. Sci., 1440, 1994, 55–64 | DOI

[25] Rothaus O. S., “On “bent” functions”, J. Comb. Theory, Ser. A, 20:3 (1976), 300–305 | DOI | Zbl

[26] Tokareva N. N., Bent functions: results and applications to cryptography, Academic Press, Elsevier, Amsterdam, 2015, 220 pp. | Zbl

[27] Zheng Y., Zhang X. M., “Plateaued functions”, Information and Communication Security, ICICS 1999, Lect. Notes Comput. Sci., 1726, Springer, Berlin, 1999, 284–300 | DOI | Zbl