Algorithms for Solving Systems of Boolean Equations Based on the Transformation of Logical Expressions

Abstract

This manuscript proves specific theorems for transforming Boolean expressions of logical formulas when moving from one basis to another, simplifying the solution of complex equations, especially for cryptographic applications. The paper develops methods for solving specific nonlinear systems of Boolean equations used in cryptographic S-boxes using transformations to simpler forms, such as disjunctive normal forms (DNFs) and Zhegalkin polynomials. The main contributions include a mathematical basis for transforming formulas, a complexity-reducing grouping method, and the RLSY program for practical implementation. A rigorous theory, cryptographic relevance, and a detailed description of the algorithm are proposed. The grouping method reduces the system complexity by a factor of 2¹¹, as shown in a test example, improving computational efficiency. A solution to a special class of systems of nonlinear Boolean equations of the second degree, which are a logical model of algebraic cryptanalysis, is also proposed. Test examples of logical formula transformations are given.