рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2024. Vol 49

Concave Continuations of Boolean Functions and Some of Their Properties and Applications

Author(s)
Dostonjon N. Barotov1

1Financial University under the Government of the Russian Federation, Moscow, Russian Federation

Abstract
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.
About the Authors
Dostonjon N. Barotov, Senior Lecturer, Financial University under the Government of the Russian Federation, Moscow, 109456, Russian Federation, DNBarotov@fa.ru
For citation

Barotov D. N. Concave Continuations of Boolean Functions and Some of Their Properties and Applications. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 49, pp. 105–123. (in Russian)

https://doi.org/10.26516/1997-7670.2024.49.105

Keywords
concave continuation of a Boolean function, Boolean function, concave function, global optimization, local extremum.
UDC
512.563+519.853.3
MSC
06E30, 90C25, 46N10
DOI
https://doi.org/10.26516/1997-7670.2024.49.105
References
  1. Barotov D.N. Convex continuation of a Boolean function and its applications. Journal of Applied and Industrial Mathematics, 2024, vol. 18, no. 1, pp. 1–9. (Accepted for publication)
  2. Barotov D.N. On the existence and properties of convex continuations of Boolean functions. Mathematical Notes, 2024, vol. 115, no. 4, pp. 489–505. (Accepted for publication)
  3. Barotov D.N., Barotov R.N. Polylinear Continuations of Some Discrete Functions and an Algorithm for Finding Them. Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie), 2023, vol. 24, pp. 10–23. https://doi.org/10.26089/NumMet.v24r102 (in Russian)
  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, 2021, vol. 8, no. 1, pp. 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., 2013, vol. 19, no. 2. pp. 285—294. (in Russian)
  6. Abdel-Gawad A.H., Atiya A.F., Darwish N.M. Solution of systems of Boolean equations via the integer domain.Information Sciences, 2010, vol. 180, no. 2, pp. 288–300. https://doi.org/10.1016/j.ins.2009.09.010
  7. Armknecht F. Improving fast algebraic attacks.Fast Software Encryption: 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004. Revised Papers 11, Springer Berlin, Heidelberg, 2004, pp. 65–82.
  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.
  9. Bardet M., Faugerebcd J.C., Salvye B., Spaenlehauer P.J. On the complexity of solving quadratic Boolean systems. Journal of Complexity, 2013, vol. 29, no. 1, pp. 53–75. https://doi.org/10.1016/j.jco.2012.07.001
  10.  Barotov D., Osipov A., Korchagin S., Pleshakova E., Muzafarov D., Barotov R., Serdechnyy D. Transformation method for solving system of Boolean algebraic equations. Mathematics, 2021, vol. 9, 3299. https://doi.org/10.3390/math9243299
  11. Barotov D.N. Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution. Mathematics, 2022, vol. 10, 2097. https://doi.org/10.3390/math10122097
  12.  Barotov D.N., Barotov R.N. Polylinear Transformation Method for Solving Systems of Logical Equations. Mathematics, 2022, vol. 10, 918. https://doi.org/10.3390/math10060918
  13. Barotov D.N., Barotov R.N., Soloviev V., Feklin V., Muzafarov D., Ergashboev T., Egamov K. The Development of Suitable Inequalities and Their Application to Systems of Logical Equations. Mathematics, 2022, vol. 10, 1851. https://doi.org/10.3390/math10111851
  14. Brown F.M. Boolean Reasoning: The logic of Boolean Equations. Kluwer Academic Publishers, Boston, 1990.
  15. Courtois N.T. Fast algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23, Springer Berlin, Heidelberg, 2003, pp. 176–194.
  16. Faugere J.C., Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases. Annual International Cryptology Conference, Springer Berlin, Heidelberg, 2003, pp. 44–60.
  17. Faugere J.C. A new efficient algorithm for computing Grobner bases (F4). Journal of pure and applied algebra, 1999, vol. 139, no. 1-3, pp. 61–88. https://doi.org/10.1016/S0022-4049(99)00005-5
  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, pp. 75–83.
  19. Gu J. Global optimization for satisfiability (SAT) problem. IEEE Transactions on Knowledge and Data Engineering, 1994, vol. 6, no. 3, pp. 361–381. https://doi.org/10.1109/69.334864
  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, pp. 63–105. https://doi.org/10.1142/9789814354707_0002
  22. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem. Journal of Computer Science and Technology, 1999, vol. 14, no. 1, pp. 1–17. https://doi.org/10.1007/BF02952482
  23. Hammer P. L., Rudeanu S. Boolean Methods in Operations Research and Related Areas. Springer Verlag, Berlin, 1968.
  24. Jensen J.L.W.V. Sur les fonctions convexes et les inegalites entre les valeurs moyennes. Acta mathematica, 1906, vol. 30, no. 1, pp. 175–193. https://doi.org/10.1007/BF02418571
  25. Liu M., Lin D., Pei D. Fast algebraic attacks and decomposition of symmetric Boolean functions. IEEE Transactions on Information Theory, 2011, vol. 57, no. 7, pp. 4817–4821. https://doi.org/10.1109/TIT.2011.2145690
  26. Pakhomchik A.I., Voloshinov V.V., Vinokur V.M., Lesovik G.B. Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis. Algorithms, 2022, vol. 15, 33. https://doi.org/10.3390/a15020033

Full text (russian)