Concave continuations of Boolean functions and some of their properties and applications

D. N. Barotov

The Bulletin of Irkutsk State University. Series Mathematics, Tome 49 (2024), pp. 105-123

Résumé

In this paper, it is proved that for any Boolean function of $n$ variables, there are infinitely many functions, each of which is its concave continuation to the $n$-dimensional unit cube. For an arbitrary Boolean function of $n$ variables, a concave function is constructed, which is the minimum among all its concave continuations to the $n$-dimensional unit cube. It is proven that this concave function on the $n$-dimensional unit cube is continuous and unique. Thanks to the results obtained, in particular, it has been constructively proved that the problem of solving a system of Boolean equations can be reduced to the problem of numerical maximization of a target function, any local maximum of which in the desired domain is a global maximum, and, thus, the problem of local maxima for such problems is completely solved.

Détail

Keywords: concave continuation of a Boolean function, Boolean function, concave function, global optimization, local extremum.

Bibliographie

[1] Barotov D.N., “Convex continuation of a Boolean function and its applications”, Journal of Applied and Industrial Mathematics, 18:1 (2024), 1–9 | MR

[2] Barotov D.N., “On the existence and properties of convex continuations of Boolean functions”, Mathematical Notes, 115:4 (2024), 489–505 | DOI | DOI | MR

[3] Barotov D.N., Barotov R.N., “Polylinear Continuations of Some Discrete Functions and an Algorithm for Finding Them”, Numerical Methods and Programming, 24 (2023), 10–23 (in Russian) | DOI

[4] Barotov D.N., Muzafarov D.Z., Barotov R.N., “On one method for solving systems of Boolean algebraic equations”, International Electronic Journal of Mathematics Education, 8:1 (2021), 17–23 (in Russian)

[5] Faizullin R.T., Dul'keit V.I., Ogorodnikov Yu.Yu., “Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem”, Trudy Inst. Mat. i Mekh. UrO RAN, 19, no. 2, 2013, 285–294 (in Russian) | MR

[6] Abdel-Gawad A. H., Atiya A. F., Darwish N. M., “Solution of systems of Boolean equations via the integer domain”, Information Sciences, 180:2 (2010), 288–300 | DOI | MR | Zbl

[7] Armknecht F., “Improving fast algebraic attacks”, Fast Software Encryption, 11th International Workshop, FSE 2004, Revised Papers 11 (Delhi, India, February 5-7, 2004), Springer, Berlin–Heidelberg, 2004, 65–82 | DOI | Zbl

[8] Bard G. V., Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis, University of Maryland, College Park, 2007 | MR

[9] Bardet M., Faugerebcd J. C., Salvye B., Spaenlehauer P. J., “On the complexity of solving quadratic Boolean systems”, Journal of Complexity, 29:1 (2013), 53–75 | DOI | MR | Zbl

[10] D. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. Barotov, D. Serdechnyy, “Transformation method for solving system of Boolean algebraic equations”, Mathematics, 9(24) (2021), 3299 | DOI

[11] Barotov D. N., “Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution”, Mathematics, 10:12 (2022), 2097 | DOI

[12] Barotov D. N., Barotov R. N., “Polylinear Transformation Method for Solving Systems of Logical Equations”, Mathematics, 10 (2022), 918 | DOI

[13] D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, K. Egamov, “The Development of Suitable Inequalities and Their Application to Systems of Logical Equations”, Mathematics, 10 (2022) | DOI

[14] Brown F. M., Boolean Reasoning: The logic of Boolean Equations, Kluwer Academic Publishers, Boston, 1990 | MR | Zbl

[15] Courtois N. T., “Fast algebraic attacks on stream ciphers with linear feedback”, Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Proceedings 23 (Santa Barbara, California, USA, August 17-21, 2003), Springer, Heidelberg–Berlin, 2003, 176–194 | DOI | MR | Zbl

[16] Faugere J. C., Joux A., “Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases”, Annual International Cryptology Conference, Springer, Heidelberg–Berlin, 2003, 44–60 | MR | Zbl

[17] Faugere J. C., “A new efficient algorithm for computing Grobner bases (F4)”, Journal of pure and applied algebra, 139:1-3 (1999), 61–88 | DOI | MR | Zbl

[18] Faugere J. C., “A new efficient algorithm for computing Grobner bases without reduction to zero (F5)”, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, 2002, 75–83 | DOI | MR | Zbl

[19] Gu J., “Global optimization for satisfiability (SAT) problem”, IEEE Transactions on Knowledge and Data Engineering, 6:3 (1994), 361–381 | DOI

[20] Gu J., How to Solve Very Large-Scale Satisfiability (VLSS) Problems, Technical Report UCECETR-90-002, University of Calgary, Calgary, 1990

[21] Gu J., “On optimizing a search problem”, Artificial Intelligence Methods and Applications, 1992, 63–105 | DOI

[22] Gu J., Gu Q., Du D., “On optimizing the satisfiability (SAT) problem”, Journal of Computer Science and Technology, 14:1 (1999), 1–17 | DOI | MR

[23] Hammer P. L., Rudeanu S., Boolean Methods in Operations Research and Related Areas, Springer Verlag, Berlin, 1968 | MR | Zbl

[24] Jensen J. L. W. V., “Sur les fonctions convexes et les inegalites entre les valeurs moyennes”, Acta mathematica, 30:1 (1906), 175–193 | DOI | MR

[25] Liu M., Lin D., Pei D., “Fast algebraic attacks and decomposition of symmetric Boolean functions”, IEEE Transactions on Information Theory, 57:7 (2011), 4817–4821 | DOI | MR | Zbl

[26] A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, G. B. Lesovik, “Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis”, Algorithms, 15 (2022), 33 | DOI