On the question on the approximation of vectorial functions over finite fields by affine analogues

V. G. Ryabov

Matematičeskie voprosy kriptografii, Tome 13 (2022), pp. 125-146.

Résumé

The measure of closeness of vectorial functions is defined by the Hamming distance in the space of their values, and the nonlinearity of a vector function is defined as the Hamming distance to the set of affine mappings. Bounds and estimates for the distribution of nonlinearity of balanced mappings and substitutions are obtained. Classes of vector functions with high nonlinearity are constructed. The nonlinearity introduced in this way is compared with the nonlinearity defined as the minimal nonlinearity over all nontrivial linear combinations of coordinate functions.

Bibliographie

[1] GOST R 34.11-94. Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Funktsiya kheshirovaniya, Izd-vo standartov, M., 1994

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

[3] Ambrosimov A. S., “O priblizhenii funktsii k-znachnoi logiki funktsiyami iz zadannoi sistemy”, Fund. i prikl. matem., 3:3 (1997), 653–674 | MR

[4] Glukhov M. M., “O priblizhenii diskretnykh funktsii lineinymi funktsiyami”, Matematicheskie voprosy kriptografii, 7:4 (2016), 29–50 | MR

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

[6] Zubkov A. M., Serov A. A., “Otsenka chisla bulevykh funktsii, imeyuschikh affinnye priblizheniya zadannoi tochnosti”, Diskretnaya matematika, 22:4 (2010), 3–19

[7] Kuzmin A. S., Nechaev A. A., Shishkin V. A., “Bent- i giperbent-funktsii nad konechnym polem”, Trudy po diskretnoi matematike, 10, Fizmatlit, M., 2007, 97–122

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

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

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

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

[12] Ryabov V. G., “Nelineinost bent-funktsii nad konechnymi polyami”, Matematicheskie voprosy kriptografii, 12:4 (2021), 87–98 | MR

[13] 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

[14] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982, 384 pp. | MR

[15] Sachkov V. N., “Translyatory i translyatsii diskretnykh funktsii”, Trudy po diskretnoi matematike, 9, Gelios ARV, M., 2006, 253–268

[16] Sidelnikov V. M., “O vzaimnoi korrelyatsii posledovatelnostei”, Problemy kibernetiki, 24, Nauka, M., 1971, 15–42 | MR

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

[18] Fomichev V. M., Diskretnaya matematika i kriptologiya, Kurs lektsii, DIALOG-MIFI, M., 2003, 400 pp.

[19] Yaschenko V. V., “O dvukh kharakteristikakh nelineinosti bulevykh otobrazhenii”, Diskretnyi analiz i issledovanie operatsii, ser. 1, 5:2 (1998), 90–96 | MR

[20] Adams C., Tavares S., “Good S-boxes are easy to find”, CRYPTO 1989, Lect. Notes Comput. Sci., 435, 1990, 612–615 | DOI

[21] Carlet C., “Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions”, Des. Codes and Cryptogr., 59:1 (2011), 89–109 | DOI | MR

[22] Carlet C., Ding C., “Nonlinearities of S-boxes”, Finite Fields and Their Appl., 13:1 (2007), 121–135 | DOI | MR

[23] Chabaud F., Vaudenay S., “Links between differential and linear cryptanalysis”, EUROCRYPT 1994, Lect. Notes Comput. Sci., 950, 1995, 356–365 | DOI | MR

[24] Golomb S. W., “On the classification of Boolean functions”, IRE Trans. Circuit Theory, 6:5 (1959), 176–186 | DOI

[25] Meier W., Staffelbach O., “Nonlinearity criteria for cryptographic functions”, EUROCRYPT 1989, Lect. Notes Comput. Sci., 434, 1990, 549–562 | DOI | MR

[26] Mesnager S., Bent functions: fundamentals and results, Springer Int. Publ. AG, Cham, 2016, 544 pp. | MR

[27] Niederreiter H., “Orthogonal systems of polynomials in finite fields”, Proc. Amer. Math. Soc., 28:2 (1971), 415–422 | DOI | MR

[28] Nyberg K., “Constructions of bent functions and difference sets”, EUROCRYPT 1990, Lect. Notes Comput. Sci., 473, 1991, 151–160 | DOI | MR

[29] Nyberg K., “Perfect nonlinear S-boxes”, EUROCRYPT 1991, Lect. Notes Comput. Sci., 547, 1991, 378–386 | DOI | MR

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

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

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

[33] Seberry J., Zhang X.-M., Zheng Y., “Nonlinearity and propagation characteristics of balanced Boolean functions”, Inf. and Comput., 119:1 (1995), 1–13 | DOI | MR

[34] Tokareva N., Bent functions: results and applications to cryptography, Academic Press, 2015, 220 pp. | MR