New bounds on the nonlinearity of PN and APN functions over finite fields

V. G. Ryabov

Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 45-59.

Résumé

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.

Détail

Keywords: finite field, vectorial function, PN function, APN functions, nonlinearity, EA-equivalence.

Bibliographie

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

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

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

[4] 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 | MR

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

[6] Brinkmann M., Extended affine and CCZ equivalence up to dimension 4, Cryptology ePrint Archive, Paper 2019/316, 2019 https://eprint.iacr.org/2019/316

[7] Brinkmann M., Leander G., “On the classification of APN functions up to dimension five”, Des., Codes, Cryptogr., 49:1–3 (2008), 273–288 | DOI | MR | Zbl

[8] Carlet C., “Characterizations of the differential uniformity of vectorial functions by the Walsh transform”, IEEE Trans. Inf. Theory, 64:9 (2018), 6443–6453 | DOI | MR | Zbl

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

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

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

[12] Dembowski P., Ostrom T. G., “Planes of order $n$ with collineation group of order $n^2$”, Math. Zeitschrift, 103:3 (1968), 239–258 | DOI | MR | Zbl

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

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

[15] Nyberg K., “Constructions of bent functions and difference sets”, EUROCRYPT 1990, Lect. Notes Comput. Sci., 473, 1991, 151–160 | 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] Su M., Zha Z., Xu Z., “Another class of perfect nonlinear polynomial functions”, Math. Probl. Eng., 2013 (2013), 917507, 1–5 | MR