Upper bounding the number of bent functions using 2-row bent rectangles
https://doi.org/10.29235/1561-2430-2023-59-2-130-135
Abstract
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.
About the Author
S. V. Agievich
Research Institute for Applied Problems of Mathematics and Informatics, Belarusian State University
Belarus
Belarus
Sergey V. Agievich – Ph. D. (Physics and Mathematics),
Head of a Research Laboratory
4, Nezavisimosti Ave., 220030, Minsk
References
1. Carlet C. Boolean Functions for Cryptography and Coding Theory. Cambridge, Cambridge University Press, 2021. 562 p. https://doi.org/10.1017/9781108606806
2. Mesnager S. Bent Functions: Fundamentals and Results. Cham, Springer, 2016. 544 p. https://doi.org/10.1007/978-3-319-32595-8.
3. Tokareva N. Bent Functions: Results and Applications to Cryptography. London, San Diego, Academic Press, 2015. 202 p. https://doi.org/10.1016/C2014-0-02922-X
4. 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.
5. Rothhaus 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
6. Agievich 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/4
7. Agievich 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-013
8. Agievich 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-3
9. Potapov 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.14583
10. Preneel 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_14
11. Langevin 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-z
12. Leander 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.004
13. Zheng 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
Review
Views: 403
Email this article 