On local affinity based method of solving systems of quadratic Boolean equations

Solving nonlinear systems of Boolean equations is NP-hard. Nevertheless, certain classes of such systems can be solved by efficient algorithms. There are theoretical and applied reasons for studying these classes and designing corresponding efficient algorithms. The paper proposes an approach to solving the systems of quadratic equations over two-element field. The method makes use of the quadratic functions' representation by their affine normal forms, i. e., in a sense, of their piecewise affine approximation. So, the initial nonlinear instance comes to a number of linear equations systems of the same variables. The paper also discusses possible ways to reduce the complexity of the proposed method.