Nonlinearity of APN functions: comparative analysis and estimates

V. G. Ryabov

Prikladnaâ diskretnaâ matematika, no. 3 (2023), pp. 15-27.

Résumé

The main results of the paper relate to the nonlinearity of APN functions defined for a vectorial Boolean function as the Hamming distance from it to the set of affine mappings in the space of images of all vectorial Boolean functions in fixed dimension. For APN functions in dimension $n$, the lower nonlinearity bound of the form $2^n - \sqrt {2^{n+1} - 7\cdot2^{-2}} - 2^{-1}$ and the corresponding lower bound on the affinity order are obtained. The exact values of the nonlinearity of all APN functions up to dimension $5$ are found, and also for one known APN $6$-dimensional permutation and for all differentially $4$-uniform permutations in dimension $4$.

Détail

Keywords: vectorial Boolean function, APN function, EA-equivalence, nonlinearity, differentially uniform.
Mots-clés : permutation

Bibliographie

[1] Glukhov M. M., “On the approximation of discrete functions by linear functions”, Matematicheskiye Voprosy Kriptografii, 7:4 (2016), 29–50 (in Russian) | DOI | MR | Zbl

[2] Nyberg K., “On the construction of highly nonlinear permutations”, LNCS, 658, 1993, 92–98 | MR | Zbl

[3] Nyberg K., “Differentially uniform mappings for cryptography”, LNCS, 765, 1994, 55–64 | MR | Zbl

[4] Nyberg K. and Knudsen L. R., “Provable security against a differential attack”, LNCS, 740, 1993, 566–574 | MR | Zbl

[5] Chen L. and Fu F., “On the nonlinearity of multi-output Boolean functions”, Acta Scientiarum Naturalium Universitatis Nankaiensis, 34:4 (2001), 28–33 (in Chinese)

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

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

[8] Nagy G. P., Thin Sidon sets and the nonlinearity of vectorial Boolean functions, 2022, arXiv: 2212.05887

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

[10] Ryabov V. G., “On the question of approximation of vectorial functions over finite fields by affine analogues”, Matematicheskiye Voprosy Kriptografii, 13:4 (2022), 125–146 (in Russian) | DOI | MR | Zbl

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

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

[13] Carlet C., “Open questions on nonlinearity and on APN functions”, LNCS, 9061, 2015, 83–107 | MR | Zbl

[14] Carlet C., “On the properties of the Boolean functions associated to the differential spectrum of general APN functions and their consequences”, IEEE Trans. Inform. Theory, 67:10 (2021), 6926–6939 | DOI | MR | Zbl

[15] 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. Inform. Theory, 67:12 (2021), 8325–8334 | DOI | MR | Zbl

[16] Carlet C., Heuser A., and Picek S., “Trade-offs for S-Boxes: cryptographic properties and side-channel resilience”, LNSC, 10355, 2017, 393–414 | MR

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

[18] Hou X., “Affinity of permutations of $F_2^n$”, Discrete Appl. Math., 154:2 (2006), 313–325 | DOI | MR | Zbl

[19] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and its Applications, eds. Y. Crama, P. Hammer, Cambridge University Press, Cambridge, 2010, 398–470 | MR

[20] Gorshkov S. P. and Dvinyaninov A. V., “Lower and upper bounds on the affinity order of transformations of spaces of Boolean vectors”, Prikladnaya Diskretnaya Matematika, 2013, no. 2(20), 14–18 (in Russian) | Zbl

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

[22] Brinkmann M., Extended Affine and CCZ Equivalence up to Dimension $4$, , 2019 https://eprint.iacr.org/2019/316.pdf

[23] Budaghyan L., Carlet C., and Pott A., “New classes of almost bent and almost perfect nonlinear polynomials”, IEEE Trans. Inform. Theory, 52:3 (2006), 1141–1152 | DOI | MR | Zbl

[24] Dobbertin H., “Almost perfect nonlinear power functions on GF($2^n$): the Niho case”, Information and Computation, 151:1–2 (1999), 57–72 | DOI | MR | Zbl

[25] Yoshiara S., “Equivalences of power APN functions with power or quadratic APN functions”, J. Algebraic Combinatorics, 44:3 (2016), 561–585 | DOI | MR | Zbl

[26] Dempwolff U., “CCZ equivalence of power functions”, Designs Codes Cryptography, 86:3 (2018), 665–692 | DOI | MR | Zbl

[27] Dempwolff U., “Correction to: CCZ equivalence of power functions”, Designs Codes Cryptography, 90:2 (2022), 473–475 | DOI | MR | Zbl

[28] Calderini M., On the EA-classes of known APN functions in small dimensions, , 2019 https://eprint.iacr.org/2019/369.pdf

[29] Calderini M., “On the EA-classes of known APN functions in small dimensions”, Cryptography and Communications, 12:5 (2020), 821–840 | DOI | MR | Zbl

[30] Browning K. A., Dillon J. F., McQuistan M. T., and Wolfe A. J., “An APN permutation in dimension six”, Finite Fields: Theory and Appl., 2010, 33–42 | DOI | MR | Zbl

[31] Leander G. and Poschmann A., “On the classification of $4$ bit S-boxes”, LNCS, 4547, 2007, 156–176 | MR