Nonlinearity of vectorial functions over finite fields

V. G. Ryabov

Diskretnaya Matematika, Tome 36 (2024) no. 2, pp. 50-70

Résumé

The nonlinearity of a vectorial function is defined as the Hamming distance to the set of affine mappings. A connection has been established between the parameters characterizing nonlinearity and the Fourier coefficients of the characters of the vectorial function. On its basis, the possibility of finding the nonlinearity parameters of a mapping through similar parameters of its components is shown for various types of decomposition. A universal upper bound for nonlinearity is presented, expressions for the boundaries of nonlinearity are obtained in terms of the Fourier coefficients of the characters, which make it possible to clarify previously known boundaries for some classes of mappings. The dependence of the lower bound of nonlinearity on differential uniformity is found.

Détail

Keywords: finite field, vectorial function, nonlinearity, differential uniformity
Mots-clés : Fourier coefficients.

Bibliographie

[1] Ambrosimov A. S., “Svoistva bent-funktsii $q$-znachnoi logiki nad konechnymi polyami”, Diskretnaya matematika, 6:3 (1994), 50–60 | MR | Zbl

[2] Gorshkov S. P., Dvinyaninov A. V., “Nizhnyaya i verkhnyaya otsenki poryadka affinnosti preobrazovanii prostranstv bulevykh vektorov”, Prikl. diskr. matem., 2013, no. 2(20), 14–18 | Zbl

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

[4] Ryabov V. G., “Nelineinost funktsii nad konechnymi polyami”, Diskretnaya matematika, 33:4 (2021), 110–131 | DOI | MR

[5] Ryabov V. G., “O priblizhenii vektornykh funktsii nad konechnymi polyami i ikh ogranichenii na lineinye mnogoobraziya affinnymi analogami”, Diskretnaya matematika, 34:2 (2022), 83–105 | DOI

[6] Ryabov V. G., “K voprosu o priblizhenii vektornykh funktsii nad konechnymi polyami affinnymi analogami”, Matematicheskie voprosy kriptografii, 13:4 (2022), 125–146 | DOI | MR | Zbl

[7] Ryabov V. G., “O chisle podstanovok vektornogo prostranstva nad konechnym polem, imeyuschikh affinnye priblizheniya zadannoi tochnosti”, Mater. XIV Mezhdunar. seminara «Diskretnaya matematika i ee prilozheniya» im. akademika O. B. Lupanova, IPM im. M.V. Keldysha RAN, 2022, 276–279

[8] Ryabov V. G., “Novye granitsy nelineinosti $\mathrm{PN}$-funktsii i $\mathrm{APN}$-funktsii nad konechnymi polyami”, Diskretnaya matematika, 35:3 (2023), 45–59 | DOI

[9] Ryabov V. G., “Udalennost vektornykh bulevykh funktsii ot affinnykh analogov (po sledam Vosmoi mezhdunarodnoi olimpiady po kriptografii)”, Matematicheskie voprosy kriptografii, 15:1 (2024), 127–142 | DOI

[10] Solodovnikov V. I., “Bent-funktsii iz konechnoi abelevoi gruppy v konechnuyu abelevu gruppu”, Diskretnaya matematika, 14:1 (2002), 99–113 | DOI | Zbl

[11] Fomichev V. M., Diskretnaya matematika i kriptologiya, Dialog-MIFI, M., 2003, 400 pp.

[12] Beth N., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT 1993, Lect. Notes Comput. Sci., 765, 1994, 65–76 | DOI | MR | Zbl

[13] Carlet C., Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, 2021, 574 pp. | MR | Zbl

[14] Carlet C., “Bounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions”, IEEE Trans. Inf. Theory, 67:12 (2021), 8325–8334 | DOI | MR | Zbl

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

[16] Carlet C., Ding C., Yuan J., “Linear codes from perfect nonlinear mappings and their secret sharing schemes”, IEEE Trans. Inf. Theory, 51:6 (2005), 2089–2102 | DOI | MR | Zbl

[17] Chen L., Fu F., “On the nonlinearity of multi-output Boolean functions”, Acta Sci. Nat. Univ. Nankai., 34:4 (2001), 28–33

[18] Gorodilova A. A., Tokareva N. N., Agievich S. V. et al., “An overview of the Eight International Olympiad in Cryptography “Non-Stop University CRYPTO””, Sibirskie elektronnye matematicheskie izvestiya, 19:1 (2022), A.9–A.37 | MR

[19] Liu J., Chen L., “On nonlinearity of the second type of multi-output Boolean functions”, Chin. J. Eng. Math., 31:1 (2014), 9–22 | DOI | MR | Zbl

[20] Liu J., Mesnager S., Chen L., “On the nonlinearity of $S$-boxes and linear codes”, Cryptogr. Commun., 9:1 (2017), 345–361 | DOI | MR | Zbl

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

[22] Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT 1993, Lect. Notes Comput. Sci., 765, 1994, 55–64 | DOI | MR | Zbl

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

[24] Ryabov V.G., “Characteristics of nonlinearity of vectorial functions over finite fields”, Matematicheskie voprosy kriptografii, 14:2 (2023), 123–136 | DOI | MR | Zbl

[25] Ryabov V.G., “Nonlinearity of $\mathrm{APN}$-functions: comparative analysis and estimates”, Prikl. diskr. matem., 61 (2023), 15–27 | MR

[26] Ryabov V., “Nonlinearity of vectorial functions over finite fields with given differential uniformity”, Trudy XI Mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem», MAKS Press, M., 2023, 9–12