This article is cited in 1 paper

Mathematical Methods of Cryptography

Generating additional constraints in algebraic cryptanalysis using SAT oracles

A. A. Semenov^a, K. V. Antonov^b, I. A. Gribanova<sup>a

a</sup> Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk
^b Moscow Engineering Physics Institute (National Nuclear Research University)

Abstract: We describe a new technique aimed to generate new constraints which augment with the original set of constraints for a problem of algebraic cryptanalysis. In case the original problem is reduced to a system of Multivariate Quadratic equations over GF(2), the generated constraints can be in the form of linear equations over two-element field. If the considered problem is reduced to SAT, then new constraints are in the form of logic equivalences, anti-equivalences or unit resolvents. In both cases we demonstrate that new constraints generated by the proposed technique can decrease the complexity estimation of attacks on considered functions.

Keywords: algebraic cryptanalysis, Boolean satisfiability problem (SAT), MQ systems of equations over GF(2), SAT oracle.

UDC: 519.7

DOI: 10.17223/2226308X/14/23