Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-Boolean optimization

The paper introduces the concept of linearizing sets that can be considered as a generalization of known linearization sets. Linearization sets are used in algebraic attacks related to the class of guess-and-determine attacks. The idea of such attacks is to guess values of variables from a certain set and then to substitute them into a system of algebraic equations that connects the input and output data of the cipher under consideration. In some cases, the result of such procedure is a linear system that can be solved effectively. In the present paper, we consider algebraic equations over the field GF(2). The values of variables from the linearizing set (as opposed to the linearization set) linearize the system of equations with a certain probability, which, generally speaking, can be substantially less than 1. The complexity estimation for guess-and-determine attack based on a particular linearizing set is constructed using a specially defined pseudo-Boolean function. The minimum value of this function gives a complexity estimation for the attack with best efficiency. To minimize such functions, a metaheuristic algorithm from the class of tabu search algorithms is used. At the current stage, attacks of the described type are built for some cryptographic generators. In particular, for the well-known A5/1 generator, the presented method allows to construct a guess-and-determine attack which complexity is 4.5 times lower than the complexity of Anderson's attack.