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

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

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

УДК 519.7 
DOI: 10.33048/daio.2023.30.764

Аннотация:

Рассматриваются бент-функции, находящиеся на  минимальном расстоянии $2^n$ от функции из класса Мэйорана — МакФарланда $\mathcal{M}_{2n}$, содержащего бент-функции от $2n$ переменных. Для функции, полученной из бент-функции класса $\mathcal{M}_{2n}$ прибавлением индикатора аффинного подпространства размерности $n$, доказан критерий того, что она также является бент-функцией. Другими словами, охарактеризованы все бент-функции на минимальном расстоянии от функции из $\mathcal{M}_{2n}$. Показано, что не достигается нижняя оценка $2^{2n+1} − 2^n$ на число бент-функций на минимальном расстоянии от функции из $\mathcal{M}_{2n}$, если перестановка, по которой построена исходная бент-функция, не является APN-функцией. Доказано, что при простых $n > 5$ существуют функции из $\mathcal{M}_{2n}$, для которых данная нижняя оценка точна, приведены примеры таких бент-функций. Также установлено, что перестановки EA-эквивалентных функций из $\mathcal{M}_{2n}$ аффинно эквивалентны, если вторые производные хотя бы одной из перестановок не тождественно нулевые. 
Библиогр. 31.

Литература:
  1. Rothaus O. On «bent» functions // J. Comb. Theory. Ser. A. 1976. V. 20, No. 3. P. 300–305.    
     
  2. Tokareva N. N. Bent functions: Results and applications to cryptography. London: Acad. Press, 2015. 220 p.    
     
  3. Adams C. The CAST-128 encryption algorithm. RFC 2144. Wilmington, DE: IETF, 1997. Available at doi.org/10.17487/RFC2144 (accessed Mar. 4, 2023).    
     
  4. Токарева Н. Н. Обобщения бент-функций. Обзор работ // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 1. С. 34–64.    
     
  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. 2017. V. 41, No. 6. P. 534–565.    
     
  6. Tokareva N. N., Gorodilova A. A., Agievich S. V. [et al.]. Mathematical methods in solutions of the problems presented at the Third International Students’ Olympiad in Cryptography // Прикл. дискрет. математика. 2018. № 40. С. 34–58.    
     
  7. Токарева Н. Н. Бент-функции: результаты и приложения. Обзор работ // Прикл. дискрет. математика. 2009. № 1. С. 15–37.    
     
  8. Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean models and methods in mathematics, computer science, and engineering. New York: Camb. Univ. Press, 2010. P. 257–397. (Encycl. Math. Appl.; V. 134).    
     
  9. Carlet C. Vectorial Boolean functions for cryptography // Boolean models and methods in mathematics, computer science, and engineering. New York: Camb. Univ. Press, 2010. P. 398–472. (Encycl. Math. Appl.; V. 134).    
     
  10. Cusick T. W., Stănică P. Cryptographic Boolean functions and applications. London: Acad. Press, 2017. 275 p.     
     
  11. Логачёв О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012. 584 с. 
     
  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. Ithaca, NY: Cornell Univ., 2021. (Cornell Univ. Libr. e-Print Archive; arXiv:2108.00232). 
     
  13. Shaporenko A. S. Derivatives of bent functions in connection with the bent sum decomposition problem // Des. Codes Cryptogr. 2023. V. 91, No. 5. P. 1607–1625. 
     
  14. Tokareva N. N. On the number of bent functions from iterative constructions: lower bounds and hypothesis // Adv. Math. Commun. 2011. V. 5, No. 4. P. 609–621. 
     
  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). Heidelberg: Springer, 1994. P. 77–101. (Lect. Notes Comput. Sci.; V. 765). 
     
  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. 2020. V. 285. P. 458–472.   
     
  17.  Коломеец Н. А., Павлов А. В. Свойства бент-функций, находящихся на минимальном расстоянии друг от друга // Прикл. дискрет. математика. 2009. № 4. С. 5–20.   
     
  18. Коломеец Н. А. Перечисление бент-функций на минимальном расстоянии от квадратичной бент-функции // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 1. С. 41–58.    
     
  19. Коломеец Н. А. Верхняя оценка числа бент-функций на расстоянии $2^k$ от произвольной бент-функции от $2k$ переменных // Прикл. дискрет. математика. 2014. № 3. С. 28–39.   
     
  20. Kolomeec N. A. The graph of minimal distances of bent functions and its properties // Des. Codes Cryptogr. 2017. V. 85, No. 3. P. 395–410.   
     
  21. Canteaut A., Daum M., Dobbertin H., Leander G. Finding nonnormal bent functions // Discrete Appl. Math. 2006. V. 154, No. 2. P. 202–218.   
     
  22. Leander G., McGuire G. Construction of bent functions from near-bent functions // J. Comb. Theory. Ser. A. 2009. V. 116, No. 4. P. 960–970.   
     
  23. Kutsenko A. V. Metrical properties of self-dual bent functions // Des. Codes Cryptogr. 2020. V. 88, No. 1. P. 201–222.   
     
  24. Kolomeec N. A. Some general properties of modified bent functions through addition of indicator functions // Cryptogr. Commun. 2021. V. 13, No. 6. P. 909–926.   
     
  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). Heidelberg: Springer, 1994. P. 55–64. (Lect. Notes Comput. Sci.; V. 765).   
     
  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). Cham: Springer, 2015. P. 83–107. (Lect. Notes Comput. Sci.; V. 9061).   
     
  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). Providence, RI: AMS, 2010. P. 33–42. (Contemp. Math.; V. 518).   
     
  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. 2023. V. 15, No. 2. P. 239–256.   
     
  29. Kolomeec N. A., Bykov D. A. On the image of an affine subspace under the inverse function within a finite field. Ithaca, NY: Cornell Univ., 2022. (Cornell Univ. Libr. e-Print Archive; arXiv:2206.14980).   
     
  30. Коломеец Н. А., Быков Д. А. Об инвариантных подпространствах функций, аффинно эквивалентных обращению элементов конечного поля // Прикл. дискрет. математика. Прил. 2022. № 15. С. 5–8.   
     
  31. Токарева Н. Н. Группа автоморфизмов множества бент-функций // Дискрет. математика. 2010. Т. 22, № 4. С. 34–42.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0018).

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

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

Коломеец Николай Александрович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: kolomeec@math.nsc.ru

Статья поступила 6 марта 2023 г. 
После доработки — 2 мая 2023 г. 
Принята к публикации 5 мая 2023 г.

Abstract:

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 > 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.

References:
  1. O. Rothaus, On «bent» functions, J. Comb. Theory, Ser. A, 20 (3), 300–305 (1976).  
     
  2. N. N. Tokareva, Bent Functions: Results and Applications to Cryptography (Acad. Press, London, 2015).  
     
  3. C. Adams, The CAST-128 encryption algorithm, RFC 2144 (IETF, Wilmington, DE, 1997). Available at doi.org/10.17487/RFC2144 (accessed Mar. 4, 2023).  
     
  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)].  
     
  5. S. V. Agievich, A. A. Gorodilova, V. A. Idrisova, N. A. Kolomeec, G. I. Shushuev, and N. N. Tokareva, Mathematical problems of the Second International Students’ Olympiad in Cryptography, Cryptologia 41 (6), 534–565 (2017).  
     
  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., No. 40, 34–58 (2018).  
     
  7. N. N. Tokareva, Bent Functions: Results and Applications. A survey, Prikl. Diskretn. Mat., No. 1, 15–37 (2009) [Russian].  
     
  8. C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Camb. Univ. Press, New York, 2010), pp. 257–397. (Encycl. Math. Appl., Vol. 134).  
     
  9. C. Carlet, Vectorial Boolean functions for cryptography, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Camb. Univ. Press, New York, 2010), pp. 398–472. (Encycl. Math. Appl., Vol. 134).  
     
  10. T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications (Acad. Press, London, 2017).  
     
  11. O. A. Logachyov, A. A. Sal’nikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology (MTsNMO, Moscow, 2012) [Russian].  
     
  12. V. N. Potapov, A. A. Taranenko, and Yu. V. Tarannikov, Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces (Cornell Univ., Ithaca, NY, 2021) (Cornell Univ. Libr. e-Print Archive; arXiv:2108.00232).  
     
  13. A. S. Shaporenko, Derivatives of bent functions in connection with the bent sum decomposition problem, Des. Codes Cryptogr. 91 (5), 1607–1625 (2023).  
     
  14. N. N. Tokareva, On the number of bent functions from iterative constructions: lower bounds and hypothesis, Adv. Math. Commun. 5 (4), 609–621 (2011).  
     
  15. C. Carlet, Two new classes of bent functions, in Advances in Cryptology — EUROCRYPT’93 (Proc. Workshop Theory and Applications of Cryptographic Techniques, Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 77–101 (Lect. Notes Comput. Sci., Vol. 765).  
     
  16. 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). 
     
  17. N. A. Kolomeec and A. V. Pavlov, Properties of bent functions at the minimal distance from each other, Prikl. Diskretn. Mat., No. 4, 5–20 (2009) [Russian]. 
     
  18. 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)]. 
     
  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., No. 3, 28–39 (2014) [Russian]. 
     
  20. N. A. Kolomeec, The graph of minimal distances of bent functions and its properties, Des. Codes Cryptogr. 85 (3), 395–410 (2017). 
     
  21. A. Canteaut, M. Daum, H. Dobbertin, and G. Leander, Finding non-normal bent functions, Discrete Appl. Math. 154 (2), 202–218 (2006). 
     
  22. G. Leander and G. McGuire, Construction of bent functions from near-bent functions, J. Comb. Theory. Ser. A. 116 (4), 960–970 (2009). 
     
  23. A. V. Kutsenko, Metrical properties of self-dual bent functions, Des. Codes Cryptogr. 88 (1), 201–222 (2020). 
     
  24. N. A. Kolomeec, Some general properties of modified bent functions through addition of indicator functions, Cryptogr. Commun. 13 (6), 909–926 (2021). 
     
  25. K. Nyberg, Differentially uniform mappings for cryptography, in Advances in Cryptology — EUROCRYPT’93 (Proc. Workshop Theory and Applications of Cryptographic Techniques, Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 55–64 (Lect. Notes Comput. Sci., Vol. 765). 
     
  26. 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). 
     
  27. 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. Finite Fields and Applications, Dublin, Ireland, July 13–17, 2009) (AMS, Providence, RI, 2010), pp. 33–42 (Contemp. Math., Vol. 518). 
     
  28. K. V. Kalgin and V. A. Idrisova, The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions, Cryptogr. Commun. 15 (2), 239–256 (2023). 
     
  29. N. A. Kolomeec and D. A. Bykov, On the image of an affine subspace under the inverse function within a finite field (Cornell Univ., Ithaca, NY, 2022) (Cornell Univ. Libr. e-Print Archive; 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., No. 15, 5–8 (2022) [Russian].  
     
  31. N. N. Tokareva, The group of automorphisms of the set of bent functions, Diskretn. Mat. 22 (4), 34–42 (2010) [Russian] [Discrete Math. Appl. 20 (5–6), 655–664 (2010)].