Applying Metaheuristic Pseudo-Boolean Optimization Algorithms to Search for Linearizing Sets in Cryptanalysis of Cryptographic Generators

In this paper we consider a new approach to the construction of guess-and-determine attacks on keystream generators based on the concept of linearizing sets. The complexity of the attack for a particular linearizing set is estimated as a value of a specially defined pseudo-Boolean function. To solve the optimization problem for the considered pseudo-Boolean function, various metaheuristic search algorithms are implemented: tabu search, genetic algorithm, (1 + 1) evolutionary algorithm, GBFS. For stream ciphers A5/1 and ASG the complexity estimates of the attacks of considered type are given.