vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2023-59-2-130-135vestifm-712Research ArticleМАТЕМАТИКАMATHEMATICSОценка сверху числа бент-функций с помощью 2-строчных бент-прямоугольниковUpper bounding the number of bent functions using 2-row bent rectanglesАгиевичC. В.AgievichS. V.

Агиевич Сергей Валерьевич – кандидат физико-математических наук, заведующий научно-исследовательской лабораторией

пр. Независимости, 4-802, 220030, Минск

Sergey V. Agievich – Ph. D. (Physics and Mathematics),Head of a Research Laboratory

4, Nezavisimosti Ave., 220030, Minsk

agievich@bsu.byНИИ прикладных проблем математики и информатики, Белорусский государственный университетБеларусьResearch Institute for Applied Problems of Mathematics and Informatics, Belarusian State UniversityBelarus202306072023592130135Copyright © Агиевич C.В., 20232023Агиевич C.В.Agievich S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/712

С помощью представления бент-функций (максимально нелинейных функций) бент-прямоугольниками (специальными матрицами с ограничениями на строки и столбцы) получена оценка сверху для числа бент-функций, которая улучшает ранее известные оценки в практическом диапазоне размерностей. Используется следующий факт, основанный на недавнем наблюдении В. Потапова (arXiv:2107.14583): 2-строчный бент-прямоугольник полностью определяется одной из своих строк и оставшимися значениями в немногим более половине столбцов. 

Using the representation of bent functions (maximum nonlinear functions) by bent rectangles, that is, special matrices with restrictions on columns and rows, we obtain herein an upper bound on the number of bent functions that improves the previously known bounds in a practical range of dimensions. The core of our method is the following fact based on the recent observation by V. Potapov (arXiv:2107.14583): a 2-row bent rectangle is completely determined by one of its rows and the remaining values in slightly more than half of the columns. 

бент-функциябент-прямоугольникпочти-бент-функциячисло бент-функцийспектр Уолша – Адамараbent functionbent rectanglenear-bent functionnumber of bent functionsWalsh – Hadamard spectrumReferencesCarlet, C. Boolean Functions for Cryptography and Coding Theory / C. Carlet. – Cambridge: Cambridge University Press, 2021. – 562 p. https://doi.org/10.1017/9781108606806Carlet C. Boolean Functions for Cryptography and Coding Theory. Cambridge, Cambridge University Press, 2021. 562 p. https://doi.org/10.1017/9781108606806Mesnager, S. Bent Functions: Fundamentals and Results / S. Mesnager. – Cham: Springer, 2016. – 544 p. https://doi.org/10.1007/978-3-319-32595-8Mesnager S. Bent Functions: Fundamentals and Results. Cham, Springer, 2016. 544 p. https://doi.org/10.1007/978-3-319-32595-8.Tokareva, N. Bent Functions: Results and Applications to Cryptography / N. Tokareva. – London; San Diego: Academic Press, 2015. – 202 p. https://doi.org/10.1016/C2014-0-02922-XTokareva N. Bent Functions: Results and Applications to Cryptography. London, San Diego, Academic Press, 2015. 202 p. https://doi.org/10.1016/C2014-0-02922-XCarlet, C. Upper bounds on the numbers of resilient functions and of bent functions / C. Carlet, A. Klapper // Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium, 2002. – [S. l.], 2002. – P. 307–314.Carlet C., Klapper A. Upper bounds on the numbers of resilient functions and of bent functions. Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium, 2002, pp. 307–314.Rothhaus, O. On “bent” functions / O. Rothhaus // J. Comb. Theory, Ser. A. – 1976. – Vol. 20, № 3. – P. 300–305. https://doi.org/10.1016/0097-3165(76)90024-8Rothhaus O. On “bent” functions. Journal of Combinatorial Theory, Series A, 1976, vol. 20, no. 3, pp. 300–305. https://doi.org/10.1016/0097-3165(76)90024-8Агиевич, C. О продолжении до бент-функций и оценке сверху их числа / C. Агиевич // Прикладная дискретная математика. Приложение. – 2020. – Вып. 13. – C. 18–21. https://doi.org/10.17223/2226308X/13/4Agievich S. On the continuation to bent functions and upper bounds on their number. Prikladnaya Diskretnaya Matematika. Supplement, 2020, iss. 13, pp. 18–21 (in Russian). https://doi.org/10.17223/2226308X/13/4Agievich, S. On the representation of bent functions by bent rectangles / S. Agievich // Probabilistic Methods in Discrete Mathematics: Fifth International Conference (Petrozavodsk, Russia, June 1–6, 2000). – Utrecht; Boston, 2002. – P. 121–135. https://doi.org/10.1515/9783112314104-013Agievich S. On the representation of bent functions by bent rectangles. Probabilistic Methods in Discrete Mathematics: Fifth International Conference (Petrozavodsk, Russia, June 1–6, 2000). Utrecht, Boston, 2002, pp. 121–135. https://doi.org/10.1515/9783112314104-013Agievich, S. Bent rectangles / S. Agievich // Proceedings of the NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security (Moscow, September 8–18, 2007). – Amsterdam, 2008. – P. 3–22. https://doi.org/10.3233/978-1-58603-878-6-3Agievich S. Bent rectangles. Proceedings of the NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security (Moscow, September 8–18, 2007). Amsterdam, 2008, pp. 3–22. https://doi.org/10.3233/978-1-58603-878-6-3Potapov, V. An upper bound on the number of bent functions / V. Potapov // Arxiv [Preprint]. – 2021. – Mode of access: https://arxiv.org/abs/2107.14583. https://doi.org/10.48550/arxiv.2107.14583Potapov V. An upper bound on the number of bent functions. Arxiv [Preprint], 2021. Available at: https://arxiv.org/abs/2107.14583. https://doi.org/10.48550/arxiv.2107.14583Propagation characteristics of Boolean functions / B. Preneel [et al.] // Advances in Cryptology: Proceedings of EUROCRYPT’90. – Berlin; Heidelberg: Springer, 1991. – P. 161–173. – (Lecture Notes in Computer Science. Vol. 473). https://doi.org/10.1007/3-540-46877-3_14Preneel B., Van Leekwijck W., Van Linden L., Goevarts R., Vanderwalle J. Propagation characteristics of Boolean functions. Advances in Cryptology: Proceedings of EUROCRYPT’90. Lecture Notes in Computer Science, vol. 473. Berlin, Heidelberg, 1991, pp. 161–173. https://doi.org/10.1007/3-540-46877-3_14Langevin, P. Counting all bent functions in dimension eight 99270589265934370305785861242880 / P. Langevin, G. Leander // Des. Codes Cryptogr. – 2011. – Vol. 59, № 1–3. – P. 193–205. https://doi.org/10.1007/s10623-010-9455-zLangevin P., Leander G. Counting all bent functions in dimension eight 99270589265934370305785861242880. Designs, Codes and Cryptography, 2011, vol. 59, no. 1–3, pp. 193–205. https://doi.org/10.1007/s10623-010-9455-zLeander, G. Construction of bent functions from near-bent functions / G. Leander, G. McGuire // J. Comb. Theory, Ser. A. – 2009. – Vol. 116, № 4. – P. 960–970. https://doi.org/10.1016/j.jcta.2008.12.004Leander G., McGuire G. Construction of bent functions from near-bent functions. Journal of Combinatorial Theory, Series A, 2009, vol. 116, no. 4, pp. 960–970. https://doi.org/10.1016/j.jcta.2008.12.004Zheng, Y. Plateaued Functions / Y, Zheng, X.-M. Zhang // Information and Communication Security. ICICS 1999. – Berlin, Heidelberg: Springer, 1999. – P. 284–300. – (Lecture Notes in Computer Science. Vol. 1726). –https://doi.org/10.1007/978-3-540-47942-0_24Zheng Y., Zhang X.-M. Plateaued Functions. Information and Communication Security. ICICS 1999. Lecture Notes in Computer Science, vol. 1726. Berlin, Heidelberg, 1999, pp. 284–300. https://doi.org/10.1007/978-3-540-47942-0_24

The authors declare that there are no conflicts of interest present.