New bounds for the nonlinearity of PN functions 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 in the paper as the Hamming distance from the function to the set of affine mappings in the space of values of all vectorial functions. For an arbitrary field of $q$ elements we derive lower bounds for the nonlinearity of PN and APN functions in $n$ variables in the form $q^n - \sqrt { q^n - 3 \cdot 2^{-2}} - 2^{-1}$ and $q^n - \sqrt { 2q^n - 7 \cdot 2^{-2}} - 2^{-1}$, respectively. These bounds improve the estimates obtained earlier in the Boolean case. It is shown that the nonlinearity of such functions can be estimated from above by $q^n - n - 1$. For $q = 2,3,4$ the exact values of the nonlinearity of PN and APN functions of low dimension are obtained.

Détail

Keywords: finite field, vectorial function, PN function, APN function, 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