## 2 Methods
### Comparison of Two Ways of Reducing Boolean Expressions to MILP Problem  
So, we have two approaches of reducing the cryptography problem to the MILP problem:  
1. By equations with binary ancillaries, see Section 2.1--Boolean expressions of cryptography algorithms are reduced to equations with binary ancillaries; CPLEX-solver is used to obtain coefficients of the desired equation for a given Boolean expression;
2. By inequalities without binary ancillaries, see Section 2.2--Boolean expressions are replaced with systems of linear inequalities without any extra binary variables; polyhedra-handling application LRS [13] is used to generate these inequalities in explicit form.  
The first approach is suited mainly to quantum annealers (such as D-Wave) because all equations may be directly converted to summands of the QUBO criterion (just by squaring). At the same time, both MILP and QUBO problems may be (theoretically) solved by classical, generic solvers (CPLEX, Gurobi, SCIP, CBC, etc.). However, extra binary ancillaries may increase the computing complexity of the problem for classical solvers.  
It is important to mention that in the context of the transformation of the equation with a Boolean function to a summand of QUBO objective function (as a penalty for violating that equation), another approach exists. For example, it is known [14] that equation \(x_{1}\wedge x_{2}=y\) is equivalent to bi-linear penalty \(P(x_{1},x_{2},y)=x_{1}x_{2}-2x_{1}y-2x_{2}y+3y\) (without any binary ancilla, which appears in the equation for XOR in (12)) in the following sense:  
\[\begin{array}{l}(x_{1}\wedge x_{2}=y)\Leftrightarrow(P(x_{1},x_{2},y)=0),\\ (x_{1}\wedge x_{2}\
eq y)\Leftrightarrow(P(x_{1},x_{2},y)\geqslant 1).\end{array} \tag{23}\]  
The second approach is suited to classical MILP solvers only. Theoretically, the absence of binary ancillaries may give an easier MILP problem than that obtained by the first approach. The number of binary variables of the resulting MILP problem will be equal to the number of unknown bits in the hash pre-image problems. However, it is still impossible to evaluate the number of linear inequalities. Comparison of the first and second approaches requires intensive computing experiments. For some Boolean function, there is another, hybrid, method based on the equation with binary ancillas and on a couple of inequalities. This method enables replacing one binary variable with a continuous one.  
Assume that we have representation of the Boolean function \(f\): \(\mathbb{B}^{n}{\rightarrow}\{0,1\}\) as a linear equation defined in (1) and (2). Let us rewrite linear Equation (1) to pick out the summand with the \(y\) variable, keeping the value of the function  
\[c_{y}y+\vec{c_{x}}^{T}\vec{x}+\vec{c_{a}}^{T}\vec{a}=b \tag{24}\]  
The method is based on the following simple statement.  
**Theorem 2**.: _Let, in (24), \(\left|c_{y}\right|=1\); all components of vectors \(\vec{c_{x}}\), \(\vec{c_{a}}\) and scalar \(b\) are all integers. Let the following inequalities hold also_  
\[0\leqslant y\leqslant 1. \tag{25}\]  
_Then Equation (24) and inequalities (25) imply that \(y\) is binary \"automatically\". In other words, in (2), we can drop the constraint that \(y\) must be binary variable._  
Proof.: The proof is very simple. The assumption that \(\vec{c_{x}}\), \(\vec{c_{a}}\) and \(b\) are all integers means that if (24) holds, then \(y\) is an integer. From inequality (25), we obtain that \(y\) can be either \(0\) or \(1\).  
Theorem 2 enables us to reduce the complexity of the corresponding MILP by replacing one binary variable with a continuous one at the extent of two additional inequalities.  
Unfortunately, of the elementary Boolean function, only the \(\oplus\) satisfies this statement. Another example is the round function \(\mathrm{H}(\mathrm{B},\mathrm{C},\mathrm{D})\), presented further in Table 2.