Characteristics of nonlinearity of vectorial functions over finite fields

V. G. Ryabov

Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 123-136

Résumé

Characteristics of the nonlinearity of a vectorial function defined on the vector space over a finite field are considered, namely, nonlinearity (the Hamming distance between the set of nontrivial linear combinations of its coordinate functions and the set of affine functions), differential uniformity, and another notion of nonlinearity (the Hamming distance from a vectorial function to a set of affine mappings). A method for constructing vectorial functions with high values of all these nonlinearities is demonstrated. Values of nonlinearities are found for permutations given by power functions and permutations defined by GOST R 34.11-94.

Bibliographie

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

[2] Beth T., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT 1993, LNCS, 765, ed. Helleseth T., Springer, Berlin–Heidelberg, 1994, 65–76 | MR | Zbl

[3] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Crytology, 4:1 (1991), 3–72 | DOI | MR | Zbl

[4] Budaghyan L., Construction and analysis of cryptographic functions, Springer Int. Publ. AG, Cham, 2014, 168 pp. | MR | Zbl

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

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

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

[8] Fomichev V.M., Discrete mathematics and cryptology, Lecture course, Dialog-MIFI, M., 2003, 397 pp., In Russian

[9] Gorshkov S.P., Dvinyaninov A.V., “Lower and upper bounds for the order of affinity of transformations of spaces of Boolean vectors”, Prikladnaya diskretnaya matematika, 2(20) (2013), 14–18, In Russian | Zbl

[10] Kuz'min A.S., Nechaev A.A., Shishkin V.A., “Bent and hyper-bent functions over the finite field”, Trudy po diskretnoi matematike, 10, Fizmatlit, M., 2007, 97–122, In Russian

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

[12] Matsui M., “Linear cryptanalysis method for DES cipher”, EUROCRYPT 1993, Lect. Notes Comput. Sci., 765, 1994, 386–397 | DOI | Zbl

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

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

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

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

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

[18] Nyberg K., Knudsen L.R., “Provable security against a differential attack”, CRYPTO 1992, Lect. Notes Comput. Sci., 740, 1993, 566–574 | DOI | MR | Zbl

[19] Pieprzyk J., “Non-linearity of exponent permutations”, EUROCRYPT 1989, Lect. Notes Comput. Sci., 434, 1990, 80–92 | DOI | MR | Zbl

[20] Pieprzyk J., Finkelstein G., “Towards effective nonlinear cryptosystem design”, IEE Proc. E, 135:6 (1988), 325–335

[21] Rueppel R.A., Analysis and design of stream ciphers, Springer, Berlin–Heidelberg, 1986, 244 pp. | MR | Zbl

[22] Ryabov V.G., “Approximation of restrictions of $q$-valued logic functions to linear manifolds by affine analogues”, Discrete Mathematics and Applications, 31:6 (2021), 409–419 | DOI | MR | Zbl

[23] Ryabov V.G., “Maximally nonlinear functions over finite fields”, Diskretnaya matematika, 33:1 (2021), 47–63, In Russian | DOI | MR

[24] Ryabov V.G., “Criteria for the maximal nonlinearity of a function over a finite field”, Diskretnaya matematika, 33:3 (2021), 79–91, In Russian | DOI | MR

[25] Ryabov V.G., “Nonlinearity of bent functions over finite fields”, Matematicheskie voprosy kriptografii, 12:4 (2021), 87–98, In Russian | DOI | MR | Zbl

[26] Ryabov V.G., “Approximation of vectorial functions over finite fields and their restrictions to linear manifolds by affine analogues”, Diskretnaya matematika, 34:2 (2022), 83–105 | DOI | MR

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

[28] Sidelnikov V.M., “On the mutual correlation of sequences”, Problemy kibernetikii, 24, Nauka, M., 1971, 15–42, In Russian | MR

[29] Solodovnikov V. I., “Bent functions from a finite abelian group into a finite Abelian group”, Discrete Mathematics and Applications, 12:2 (2002), 111–126 | DOI | MR | Zbl

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