Using Linearizing Sets to Solve Multivariate Quadratic Equations in Algebraic Cryptanalysis

Abstract

In this paper we describe a class of cryptographic guess-and-determine attacks which is based on the notion of a linearizing set. A linearizing set-based attack is applied to a system of Multivariate Quadratic equations (MQ) over $GF(2)$ field, which encodes how a considered cryptographic function works. By substituting into such MQ system a random (in some strict sense) assignment of variables from a linearizing set we aim to transform the system into a linear one. We introduce a probability of such an event and call it a probability of linearization. Then we describe a guess-and-determine attack, the hardness of which can be expressed via a probability of linearization. To estimate the latter it is possible to use a simple Monte Carlo algorithm. Also we describe a technique that allows to augment a considered MQ system by new linear equations and to construct a new MQ system, for which the probability of linearization is usually larger than that for an original one. For this purpose we apply a SAT oracle to a Boolean formula that is naturally associated with a considered MQ system. Finally, we reduce the problem of searching for a linearizing set that yields the best effectiveness of a constructed guess-and-determine attack to a pseudo-Boolean optimization problem, which can be solved using metaheuristic optimization algorithms. The important consequence of this is that this way we can construct guess-and-determine attacks automatically by solving the corresponding optimization problem. In the computational experiments we used the proposed methodology to construct attacks on several well-known stream ciphers. The runtime estimations of some of the attacks make it possible to implement them in reasonable time.

Keywords

• Algebraic cryptanalysis
• guess-and-determine attack
• system of multivariate quadratic equations
• Boolean satisfiability
• pseudo-Boolean optimization
• evolutionary algorithm