О ближайших бент-функциях к заданной бент-функции МэйоранаМакФарланда

О ближайших бент-функциях к заданной бент-функции Мэйорана—МакФарланда

Быков Д. А., Коломеец Н. А.
Дискретный анализ и исследование операций, 32, 3, 5-42 (2025)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2025.32.811

Аннотация:

Исследуются бент-функции от $2n$ переменных, ближайшие к заданной функции из класса Мэйорана — МакФарланда. Переформулирован критерий расположения таких бент-функций, и уточнён метод подсчёта их числа. Исследованы функции с числом ближайших бент-функций, близким к его нижней и точной верхней оценкам. Доказано существование бент-функций, у которых число ближайших бент-функций имеет ту же асимптотику, что и нижняя оценка. Приведены примеры функций из класса Мэйорана — МакФарланда, для которых рассчитанное число ближайших бентфункций близко к верхней оценке. Рассматривается также достижимость нижней оценки, а именно, усилены известные необходимые и достаточные условия. Показано, что нижняя оценка достигается при $n$, равном степени простого числа $p \ge 5$, а также при некоторых других $n$. Приведена полная классификация функций от 6 переменных из класса Мэйорана — МакФарланда по числу ближайших бент-функций. 
Табл. 1, библиогр. 40.

Литература:
  1. Rothaus O. On “bent” functions // J. Comb. Theory. Ser. A. 1976. V. 20, No. 3. P. 300–305. DOI: 10.1016/0097-3165(76)90024-8.
     
  2. Tokareva N. N. Bent functions: Results and applications to cryptography. Amsterdam: Acad. Press, 2015. 220 p. DOI: 10.1016/c2014-0-02922-x.
     
  3. Токарева Н. Н. Бент-функции: результаты и приложения. Обзор работ // Прикл. дискрет. математика. 2009. № 1. С. 15–37. DOI: 10.17223/20710410/ 3/2.
     
  4. Токарева Н. Н. Обобщения бент-функций. Обзор работ // Дискрет. анализ и исслед. операций. 2010. T. 17, № 1. С. 34–64.
     
  5. Helleseth T., Kholosha A. Bent functions and their connections to combinatorics // Surveys in combinatorics 2013. Cambridge: Camb. Univ. Press, 2013. P. 91–126. (Lond. Math. Soc. Lect. Notes Ser.; V. 409). DOI: 10.1017/ CBO9781139506748.004.
     
  6. Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and their applications — SETA 2004. Proc. Int. Conf. (Seoul, Korea, Oct. 24–28, 2005). Heidelberg: Springer, 2005. P. 1–29. (Lect. Notes Comput. Sci.; V. 3486). DOI: 10.1007/11423461_1.
     
  7. Mesnager S. Bent functions: Fundamentals and results. Cham: Springer, 2018. 570 p. DOI: 10.1007/978-3-319-32595-8.
     
  8. Логачёв О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012. 584 с.
     
  9. Logachev O. A., Salnikov A. A., Yashchenko V. V. Boolean functions in coding theory and cryptography. Providence, RI: AMS, 2012. 334 p.
     
  10. Агибалов Г. П. Избранные теоремы начального курса криптографии. Томск: Изд. дом ТГУ, 2005. 112 с.
     
  11. Панкратова И. А. Булевы функции в криптографии. Томск: Изд. дом ТГУ, 2014. 88 с.
     
  12. Токарева Н. Н. Симметричная криптография: Краткий курс. Новосибирск: НГУ, 2012. 234 с.
     
  13. Cusick T. W., Stanica P. Cryptographic Boolean functions and applications. Amsterdam: Acad. Press, 2017. 275 p. DOI: 10.1016/c2016-0-00852-5.
     
  14. Carlet C. Boolean functions for cryptography and coding theory. Cambridge: Camb. Univ. Press, 2020. 562 p. DOI: 10.1017/9781108606806.
     
  15. McFarland R. L. A family of difference sets in non-cyclic groups // J. Comb. Theory. Ser. A. 1973. V. 15, No. 1. P. 1–10. DOI: 10.1016/0097-3165(73) 90031-9.
     
  16. Dillon J. F. Elementary Hadamard difference sets: PhD thesis. College Park, 1974.
     
  17. Коломеец Н. А., Павлов А. В. Свойства бент-функций, находящихся на минимальном расстоянии друг от друга // Прикл. дискрет. математика. 2009. № 4. С. 5–20.
     
  18. Carlet C. Two new classes of bent functions // Advances in cryptology — EUROCRYPT’93. Proc. Workshop on the Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 77–101. (Lect. Notes Comput. Sci.; V. 765). DOI: 10.1007/3-540-48285-7_8.
     
  19. Zhang F., Pasalic E., Cepak N., Wei Y. Bent functions in $\mathcal C$ and $\mathcal D$ outside the completed Maiorana–McFarland class // Codes, cryptology and information security. Proc. 2nd Int. Conf. (Rabat, Morocco, Apr. 10–12, 2017). Cham: Springer, 2017. P. 298–313. (Lect. Notes Comput. Sci.; V. 10194). DOI: 10.1007/978-3-319-55589-8_20.
     
  20. 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. 2020. V. 285. P. 458–472. DOI: 10.1016/j.dam.2020.06.012.
     
  21. Kudin S., Pasalic E. A complete characterization of $\mathcal{D}_0 \cap \mathcal{M}^{\#}$ and a general framework for specifying bent functions in $\mathcal C$ outside $\mathcal{M}^{\#}$ // Des. Codes Cryptogr. 2022. V. 90, No. 8. P. 1783–1796. DOI: 10.1007/s10623-022-01079-3.
     
  22. Kudin S., Pasalic E., Cepak N., Zhang F. Permutations without linear structures inducing bent functions outside the completed Maiorana–McFarland class // Cryptogr. Commun. 2022. V. 14, No. 1. P. 101–116. DOI: 10.1007/ s12095-021-00523-w.
     
  23. Bapić A, Pasalic E., Zhang F., Hodžić S. Constructing new superclasses of bent functions from known ones // Cryptogr. Commun. 2022. V. 14, No. 6. P. 1229–1256. DOI: 10.1007/s12095-022-00566-7.
     
  24. Pasalic E., Bapić A., Zhang F., Wei Y. Explicit infinite families of bent functions outside the completed Maiorana–McFarland class // Des. Codes Cryptogr. 2023. V. 91, No. 7. P. 2365–2393. DOI: 10.1007/ s10623-023-01204-w. 
     
  25. Pasalic E., Polujan A., Kudin S., Zhang F. Design and analysis of bent functions using $\mathcal M$-subspaces // IEEE Trans. Inf. Theory. 2024. V. 70, No. 6. P. 4464–4477. DOI: 10.1109/TIT.2024.3352824.
     
  26. Kudin S., Pasalic E., Polujan A., Zhang F. The algebraic characterization of $\mathcal M$-subspaces of bent concatenations and its application // IEEE Trans. Inf. Theory. 2025. V. 71, No. 5. P. 3999–4011. DOI: 10.1109/TIT.2025.3547533.
     
  27. Polujan A. A., Pott A. Cubic bent functions outside the completed Maiorana–McFarland class // Des. Codes Cryptogr. 2020. V. 88, No. 9. P. 1701–1722. DOI: 10.1007/s10623-019-00712-y.
     
  28. Коломеец Н. А. Перечисление бент-функций на минимальном расстоянии от квадратичной бент-функции // Дискрет. анализ и исслед. операций. 2012. T. 19, № 1. С. 41–58.
     
  29. Kolomeec N. The graph of minimal distances of bent functions and its properties // Des. Codes Cryptogr. 2017. V. 85, No. 3. P. 395–410. DOI: 10.1007/s10623-016-0306-4.
     
  30. Быков Д. А., Коломеец Н. А. О нижней оценке числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана — МакФарланда // Дискрет. анализ и исслед. операций. 2023. Т. 30, № 3. C. 57–80.
     
  31. Nyberg K. Differentily uniform mappings for cryptography // Advances in cryptology — EUROCRYPT’93. Proc. Workshop Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 55–64. (Lect. Notes Comput. Sci.; V. 765). DOI: 10.1007/ 3-540-48285-7_6.
     
  32. 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). Cham: Springer, 2015. P. 83–107. (Lect. Notes Comput. Sci.; V. 9061). DOI: 10.1007/978-3-319-16277-5_5.
     
  33. Jacobson N. Basic algebra. V. I. Mineola, NY: Dover Publ., 2009. 528 p.
     
  34. Kolomeec N. A., Bykov D. A. On the image of an affine subspace under the inverse function within a finite field // Des. Codes Cryptogr. 2024. V. 92, No. 2. P. 467–476. DOI: 10.1007/s10623-023-01316-3.
     
  35. Kolomeec N. A., Bykov D. A. On the Maiorana–McFarland class extensions. Ithaca, NY, 2025. 29 p. (e-Print Archive / Cornell Univ.; arXiv:2503.21440). DOI: 10.48550/arXiv.2503.21440.
     
  36. Clark W. E., Hou X., Mihailovs A. The affinity of a permutation of a finite vector space // Finite Fields Appl. 2007. V. 13. P. 80–112. DOI: 10.1016/j. ffa.2005.07.004.
     
  37. Li S., Meidl W., Polujan A., Pott A., Riera C., Stănică P. Vanishing flats: A combinatorial viewpoint on the planarity of functions and their application // IEEE Trans. Inf. Theory. 2020. V. 66, No. 11. P. 7101–7112. DOI: 10.1109/TIT.2020.3002993.
     
  38. Коломеец Н. А. О подстановках, разрушающих структуру подпространств определённых размерностей // Прикл. дискрет. математика. 2024. № 65. C. 5–20. DOI: 10.17223/20710410/65/1.
     
  39. 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. (Dublin, Ireland, July 13–17, 2009). Providence, RI: AMS, 2010. P. 33–42. (Contemp. Math.; V. 518). DOI: 10.1090/conm/518/10194.
     
  40. Черёмушкин А. В. Методы аффинной и линейной классификации двоичных функций // Труды по дискретной математике. Т. 4. М.: Физматлит, 2001. C. 273–314.

Исследование выполнено при поддержке Математического центра в Академгородке (соглашение № 075–15–2025–349 с Министерством науки и высшего образования Российской Федерации). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Быков Денис Александрович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: den.bykov.2000i@gmail.com

Коломеец Николай Александрович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: nkolomeec@gmail.com

Статья поступила 27 августа 2024 г.
После доработки — 26 марта 2025 г.
Принята к публикации 22 июня 2025 г.

Abstract:

Bent functions of $2n$ variables closest to a given bent function in the Maiorana–McFarland class are considered. The known criterion for their construction is revised and the method of calculating their number is refined. We investigate functions such that the number of closest bent functions is approximate to its lower and sharp upper bounds. The existence of bent functions whose number of closest bent functions has the same asymptotics as the lower bound is proven. Examples of functions in the Maiorana–McFarland class are given for which the calculated number of closest bent functions is close to the upper bound. Attainability of the lower bound is considered, and known necessary and sufficient conditions are refined. We show that the lower bound is attained for $n$ equaled to a power of a prime $p \ge 5$, as well as for some other $n$. A complete classification of functions of 6 variables in the Maiorana–McFarland class using the number of closest bent functions is obtained. 
Tab. 1, bibliogr. 40.

References:
  1. O. Rothaus, On “bent” functions, J. Comb. Theory, Ser. A, 20 (3), 300–305 (1976), DOI: 10.1016/0097-3165(76)90024-8.
     
  2. N. N. Tokareva, Bent Functions: Results and Applications to Cryptography (Acad. Press, Amsterdam, 2015), DOI: 10.1016/c2014-0-02922-x.
     
  3. N. N. Tokareva, Bent functions: Results and applications. A survey, Prikl. Diskretn. Mat., No. 1, 15–37 (2009) [Russian], DOI: 10.17223/20710410/3/2.
     
  4. N. N. Tokareva, Generalizations of bent functions. A survey, Diskretn. Anal. Issled. Oper. 17 (1), 34–64 (2010) [Russian] [J. Appl. Ind. Math. 5 (1), 110–129 (2011), DOI: 10.1134/S1990478911010133].
     
  5. T. Helleseth and A. Kholosha, Bent functions and their connections to combinatorics, in Surveys in Combinatorics 2013 (Camb. Univ. Press, Cambridge, 2013), pp. 91–126 (Lond. Math. Soc. Lect. Notes Ser., Vol. 409), DOI: 10.1017/CBO9781139506748.004.
     
  6. H. Dobbertin and G. Leander, A survey of some recent results on bent functions, in Sequences and Their Applications — SETA 2004, Proc. Int. Conf. (Seoul, Korea, Oct. 24–28, 2005) (Springer, Heidelberg, 2005), pp. 1–29 (Lect. Notes Comput. Sci., Vol. 3486), DOI: 10.1007/11423461_1.
     
  7. S. Mesnager, Bent Functions: Fundamentals and Results (Springer, Cham, 2018), DOI: 10.1007/978-3-319-32595-8.
     
  8. O. A. Logachev, A. A. Salnikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptography (MTsNMO, Moscow, 2012) [Russian].
     
  9. O. A. Logachev, A. A. Salnikov, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptography (AMS, Providence, RI, 2012).
     
  10. G. P. Agibalov, Selected Theorems of an Introductory Cryptography Course (Izd. Dom TGU, Tomsk, 2005) [Russian].
     
  11. I. A. Pankratova, Boolean Functions in Cryptography (Izd. Dom TGU, Tomsk, 2014) [Russian].
     
  12. N. N. Tokareva, Symmetric Cryptography: A Brief Course (NGU, Novosibirsk, 2012) [Russian].
     
  13. T. W. Cusick and P. Stanica, Cryptographic Boolean Functions and Applications (Acad. Press, Amsterdam, 2017), DOI: 10.1016/c2016-0-00852-5.
     
  14. C. Carlet, Boolean Functions for Cryptography and Coding Theory (Camb. Univ. Press, Cambridge, 2020), DOI: 10.1017/9781108606806.
     
  15. R. L. McFarland, A family of difference sets in non-cyclic groups, J. Comb. Theory, Ser. A, 15 (1), 1–10 (1973), DOI: 10.1016/0097-3165(73)90031-9.
     
  16. J. F. Dillon, Elementary Hadamard difference sets, PhD Thesis (College Park, 1974).
     
  17. N. A. Kolomeec and A. V. Pavlov, Properties of bent functions with minimal distance, Prikl. Diskretn. Mat., No. 4, 5–20 (2009) [Russian].
     
  18. C. Carlet, Two new classes of bent functions, in Advances in Cryptology — EUROCRYPT’93, Proc. Workshop on the Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 77–101 (Lect. Notes Comput. Sci., Vol. 765), DOI: 10.1007/ 3-540-48285-7_8.
     
  19. F. Zhang, E. Pasalic, N. Cepak, and Y. Wei, Bent functions in $\mathcal{C}$ and $\mathcal{D}$ outside the completed Maiorana–McFarland class, in Codes, Cryptology and Information Security, Proc. 2nd Int. Conf. (Rabat, Morocco, Apr. 10–12, 2017) (Springer, Cham, 2017), pp. 298–313 (Lect. Notes Comput. Sci., Vol. 10194), DOI: 10.1007/978-3-319-55589-8_20.
     
  20. F. Zhang, N. Cepak, E. Pasalic, and Y. Wei, Further analysis of bent functions from $\mathcal{C}$ and $\mathcal{D}$ which are provably outside or inside $\mathcal{M}^{\#}$, Discrete Appl. Math. 285, 458–472 (2020), DOI: 10.1016/j.dam.2020.06.012.
     
  21. S. Kudin and E. Pasalic, A complete characterization of $\mathcal{D}_0 \cap \mathcal{M}^{\#}$ and a general framework for specifying bent functions in C outside $\mathcal{M}^{\#}$, Des. Codes Cryptogr. 90 (8), 1783–1796 (2022), DOI: 10.1007/s10623-022-01079-3.
     
  22. S. Kudin, E. Pasalic, N. Cepak, and F. Zhang, Permutations without linear structures inducing bent functions outside the completed Maiorana– McFarland class, Cryptogr. Commun. 14 (1), 101–116 (2022), DOI: 10.1007/ s12095-021-00523-w.
     
  23. A Bapić, E. Pasalic, F. Zhang, S. Hodžić Constructing new superclasses of bent functions from known ones, Cryptogr. Commun. 14 (6), 1229–1256 (2022), DOI: 10.1007/s12095-022-00566-7.
     
  24. E. Pasalic and A. Bapić, F. Zhang, Y. Wei Explicit infinite families of bent functions outside the completed Maiorana–McFarland class, Des. Codes Cryptogr. 91 (7), 2365–2393 (2023), DOI: 10.1007/s10623-023-01204-w. 
     
  25. E. Pasalic, A. Polujan, S. Kudin, and F. Zhang, Design and analysis of bent functions using $\mathcal{M}$-subspaces, IEEE Trans. Inf. Theory 70 (6), 4464–4477 (2024), DOI: 10.1109/TIT.2024.3352824.
     
  26. S. Kudin, E. Pasalic, A. Polujan, and F. Zhang, The algebraic characterization of $\mathcal{M}$-subspaces of bent concatenations and its application, IEEE Trans. Inf. Theory 71 (5), 3999–4011 (2025), DOI: 10.1109/TIT.2025.3547533.
     
  27. A. A. Polujan and A. Pott, Cubic bent functions outside the completed Maiorana–McFarland class, Des. Codes Cryptogr. 88 (9), 1701–1722 (2020), DOI: 10.1007/s10623-019-00712-y.
     
  28. N. A. Kolomeec, Enumeration of the bent functions of least deviation from a quadratic bent function, Diskretn. Anal. Issled. Oper. 19 (1), 41–58 (2012) [Russian] [J. Appl. Ind. Math. 6 (3), 306–317 (2012), DOI: 10.1134/ S1990478912030052].
     
  29. N. Kolomeec, The graph of minimal distances of bent functions and its properties, Des. Codes Cryptogr. 85 (3), 395–410 (2017), DOI: 10.1007/ s10623-016-0306-4.
     
  30. D. A. Bykov and N. A. Kolomeec, On a lower bound for the number of bent functions at the minimum distance from a bent function in the Maiorana–McFarland class, Diskretn. Anal. Issled. Oper. 30 (3), 57–80 (2023) [Russian] [J. Appl. Ind. Math. 17 (3) 507–520 (2023)].
     
  31. K. Nyberg, Differentily uniform mappings for cryptography, in Advances in Cryptology — EUROCRYPT’93, Proc. Workshop Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 55–64 (Lect. Notes Comput. Sci., Vol. 765), DOI: 10.1007/3-540-48285-7_6.
     
  32. C. Carlet, Open questions on nonlinearity and on APN functions, in Arithmetic of Finite Fields, Rev. Sel. Pap. 5th Int. Workshop (Gebze, Turkey, Sept. 27–28, 2014) (Springer, Cham, 2015), pp. 83–107 (Lect. Notes Comput. Sci., Vol. 9061), DOI: 10.1007/978-3-319-16277-5_5.
     
  33. N. Jacobson, Basic Algebra, V. I (Dover Publ., Mineola, NY, 2009).
     
  34. N. A. Kolomeec and D. A. Bykov, On the image of an affine subspace under the inverse function within a finite field, Des. Codes Cryptogr. 92 (2), 467–476 (2024), DOI: 10.1007/s10623-023-01316-3.
     
  35. N. A. Kolomeec and D. A. Bykov, On the Maiorana–McFarland class extensions (Ithaca, NY, 2025) (e-Print Archive / Cornell Univ., arXiv:2503.21440), DOI: 10.48550/arXiv.2503.21440.
     
  36. W. E. Clark, X. Hou, and A. Mihailovs, The affinity of a permutation of a finite vector space, Finite Fields Appl. 13, 80–112 (2007), DOI: 10.1016/j. ffa.2005.07.004.
     
  37. S. Li, W. Meidl, A. Polujan, A. Pott, C. Riera, and P. Stănică, Vanishing flats: A combinatorial viewpoint on the planarity of functions and their application, IEEE Trans. Inf. Theory 66 (11), 7101–7112 (2020), DOI: 10.1109/TIT.2020.3002993.
     
  38. N. A. Kolomeec, On permutations that break subspaces of specified dimensions, Prikl. Diskretn. Mat., No. 65, 5–20 (2024) [Russian], DOI: 10.17223/ 20710410/65/1.
     
  39. K. A. Browning, J. F. Dillon, M. T. McQuistan, and A. J. Wolfe, An APN permutation in dimension six, in Finite Fields: Theory and Applications, Proc. 9th Int. Conf. (Dublin, Ireland, July 13–17, 2009) (AMS, Providence, RI, 2010), pp. 33–42 (Contemp. Math., Vol. 518), DOI: 10.1090/conm/ 518/10194.
     
  40. A. V. Cheryomushkin, Methods for affine and linear classification of Boolean functions, in Transactions on Discrete Mathematics, Vol. 4 (Fizmatlit, Moscow, 2001) [Russian], pp. 273–314.