On a lower bound for the number of~bent~functions at the minimum distance from a~bent~function in the Maiorana--McfFrland class

D. A. Bykov ; N. A. Kolomeec

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 57-80.

Résumé

Bent functions at the minimum distance $2^n$ from a given bent function in $2n$ variables belonging to the Maiorana–McFarland class $\mathcal{M}_{2n}$ are investigated. We provide a criterion for a function obtained using the addition of the indicator of an $n$-dimensional affine subspace to a given bent function from $\mathcal{M}_{2n}$ to be a bent function as well. In other words, all bent functions at the minimum distance from a Maiorana–McFarland bent function are characterized. It is shown that the lower bound $2^{2n+1}-2^n$ for the number of bent functions at the minimum distance from $f \in \mathcal{M}_{2n}$ is not attained if the permutation used for constructing $f$ is not an APN function. It is proven that for any prime $n\geq 5$ there are functions from $\mathcal{M}_{2n}$ for which this lower bound is accurate. Examples of such bent functions are found. It is also established that the permutations of EA-equivalent functions from $\mathcal{M}_{2n}$ are affinely equivalent if the second derivatives of at least one of the permutations are not identically zero. Bibliogr. 31.

Détail

Keywords: bent function, Boolean function, Maiorana–McFarland class, lower bound
Mots-clés : minimum distance, affine equivalence.

Bibliographie

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

[2] Tokareva N. N., Bent functions: Results and applications to cryptography, Acad. Press, London, 2015, 220 pp. | MR | Zbl

[3] Adams C., The CAST-128 encryption algorithm, RFC 2144, IETF, Wilmington, DE, 1997 (accessed Mar. 4, 2023) | DOI

[4] N. N. Tokareva, “Generalizations of bent functions. A survey”, J. Appl. Ind. Math., 5:1 (2011), 110–129 | DOI | MR | Zbl

[5] Agievich S. V., Gorodilova A. A., Idrisova V. A., Kolomeec N. A., Shushuev G. I., Tokareva N. N., “Mathematical problems of the Second International Students' Olympiad in Cryptography”, Cryptologia, 41:6 (2017), 534–565 | DOI

[6] N. N. Tokareva, A. A. Gorodilova, S. V. Agievich et al., “Mathematical methods in solutions of the problems presented at the Third International Students' Olympiad in Cryptography”, Prikl. Diskretn. Mat., 2018, no. 40, 34–58 | MR | Zbl

[7] N. N. Tokareva, “Bent Functions: Results and Applications. A survey”, Prikl. Diskretn. Mat., 2009, no. 1, 15–37 (Russian)

[8] Carlet C., “Boolean functions for cryptography and error-correcting codes”, Boolean models and methods in mathematics, computer science, and engineering, Encycl. Math. Appl., 134, Camb. Univ. Press, New York, 2010, 257–397 | MR | Zbl

[9] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean models and methods in mathematics, computer science, and engineering, Encycl. Math. Appl., 134, Camb. Univ. Press, New York, 2010, 398–472 | MR

[10] Cusick T. W., Stănică P., Cryptographic Boolean functions and applications, Acad. Press, London, 2017, 275 pp. | MR | Zbl

[11] O. A. Logachyov, A. A. Sal'nikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology, MTsNMO, M., 2012 (Russian)

[12] Potapov V. N., Taranenko A. A., Tarannikov Yu. V., Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces, Cornell Univ, Ithaca, NY, 2021, arXiv: 2108.00232

[13] Shaporenko A. S., “Derivatives of bent functions in connection with the bent sum decomposition problem”, Des. Codes Cryptogr., 91:5 (2023), 1607–1625 | DOI | MR | Zbl

[14] Tokareva N. N., “On the number of bent functions from iterative constructions: lower bounds and hypothesis”, Adv. Math. Commun., 5:4 (2011), 609–621 | DOI | MR | Zbl

[15] Carlet C., “Two new classes of bent functions”, Advances in cryptology — EUROCRYPT'93, Proc. Workshop Theory and Applications of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993), Lect. Notes Comput. Sci., 765, Springer, Heidelberg, 1994, 77–101 | DOI | MR | Zbl

[16] Zhang F., Cepak N., Pasalic E., Wei Y., “Further analysis of bent functions from $\mathcal{C}$ and $\mathcal{D}$ which are provably outside or inside $\mathcal{M}^\#$”, Discrete Appl. Math., 285 (2020), 458–472 | DOI | MR | Zbl

[17] N. A. Kolomeec and A. V. Pavlov, “Properties of bent functions at the minimal distance from each other”, Prikl. Diskretn. Mat., 2009, no. 4, 5–20 (Russian)

[18] N. A. Kolomeec, “Enumeration of the bent functions of least deviation from a quadratic bent function”, J. Appl. Ind. Math., 6:3 (2012), 306–317 | DOI | MR | Zbl

[19] N. A. Kolomeec, “An upper bound for the number of bent functions at the distance $2^k$ from an arbitrary bent function in $2k$ variables”, Prikl. Diskretn. Mat., 2014, no. 3, 28–39 (Russian)

[20] Kolomeec N. A., “The graph of minimal distances of bent functions and its properties”, Des. Codes Cryptogr., 85:3 (2017), 395–410 | DOI | MR | Zbl

[21] Canteaut A., Daum M., Dobbertin H., Leander G., “Finding nonnormal bent functions”, Discrete Appl. Math., 154:2 (2006), 202–218 | DOI | MR | Zbl

[22] Leander G., McGuire G., “Construction of bent functions from near-bent functions”, J. Comb. Theory. Ser. A, 116:4 (2009), 960–970 | DOI | MR | Zbl

[23] Kutsenko A. V., “Metrical properties of self-dual bent functions”, Des. Codes Cryptogr., 88:1 (2020), 201–222 | DOI | MR | Zbl

[24] Kolomeec N. A., “Some general properties of modified bent functions through addition of indicator functions”, Cryptogr. Commun., 13:6 (2021), 909–926 | DOI | MR | Zbl

[25] Nyberg K., “Differentially uniform mappings for cryptography”, Advances in cryptology — EUROCRYPT'93, Proc. Workshop Theory and Applications of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993), Lect. Notes Comput. Sci., 765, Springer, Heidelberg, 1994, 55–64 | DOI | MR | Zbl

[26] Carlet C., “Open questions on nonlinearity and on APN functions”, Arithmetic of finite fields, Rev. Sel. Pap. 5th Int. Workshop (Gebze, Turkey, Sept. 27–28, 2014), Lect. Notes Comput. Sci., 9061, Springer, Cham, 2015, 83–107 | DOI | MR | Zbl

[27] Browning K. A., Dillon J. F., McQuistan M. T., Wolfe A. J., “An APN permutation in dimension six”, Finite fields: Theory and applications, Proc. 9th Int. Conf. Finite Fields and Applications (Dublin, Ireland, July 13-17, 2009), Contemp. Math., 518, AMS, Providence, RI, 2010, 33–42 | DOI | MR | Zbl

[28] Kalgin K. V., Idrisova V. A., “The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions”, Cryptogr. Commun., 15:2 (2023), 239–256 | DOI | MR | Zbl

[29] Kolomeec N. A., Bykov D. A., On the image of an affine subspace under the inverse function within a finite field, Cornell Univ, Ithaca, NY, 2022, arXiv: 2206.14980

[30] N. A. Kolomeec and D. A. Bykov, “Invariant subspaces of functions affine equivalent to the finite field inversion”, Prikl. Diskretn. Mat., Prilozh., 2022, no. 15, 5–8 (Russian)

[31] N. N. Tokareva, “The group of automorphisms of the set of bent functions”, Discrete Math. Appl., 20:5–6 (2010), 655–664 | DOI | MR | Zbl