Comparative analysis of the complexity of the linearization and enumeration methods for solving systems of nonlinear boolean equations

Abstract

The problem of finding solutions to systems of multivariate nonlinear equations over finite algebraic structures and constructing efficient algorithms for their search is important for many applied problems in various fields, and the relevance of this problem increases over time. The security of many existing cryptosystems is based on the complexity of the problem of solving systems of multivariable nonlinear equations over finite fields. In general, this task is an -complete problem. But there are many cases where such systems can be solved by methods faster than the brute-force methods. Since choosing a method can significantly reduce the time and resources required to find system solutions, the questions of assessing the complexity of different methods of solutions for systems with different sets of parameters, as well as finding the special best performing methods for a particular classes of systems, naturally arise. The paper deals with the most important for cryptography and cryptanalysis systems of multivariate nonlinear equations over the finite field . The subject of the study is a comparative analysis of the complexity of the method of linearization with the introduction of new variables for solving systems of nonlinear equations over the field  with many unknowns, and the method of complete enumeration, depending on the system parameters. The purpose of the work is obtaining average estimates of the complexity of the methods, and determining the boundary in the parameter space of the overdefined consistent system of equations, which makes it possible to choose the faster and more efficient method of the two considered. Probabilistic models for obtaining theoretical, asymptotic estimates of the average complexity of the methods, and for conducting a number of statistical experiments with obtaining the average estimates by the Monte Carlo method, are proposed. It is shown that there exists a boundary in the parameter space, depending on, first of all, the relation between the maximum degree of equations of the system and the number of unknowns, which determines when the linearization method works better than the complete enumeration. Theoretical and experimental data have been used to construct this boundary. The analytical expression for the separation line in the parameter space of the system was obtained by the least squares method.