Prikl. Diskr. Mat. Suppl., 2021, Issue 14, Pages 104–110
Mathematical Methods of Cryptography
Generating additional constraints in algebraic cryptanalysis using SAT oracles
A. A. Semenova, K. V. Antonovb, I. A. Gribanovaa
a 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)
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.
algebraic cryptanalysis, Boolean satisfiability problem (SAT), MQ systems of equations over GF(2), SAT oracle.
PDF file (630 kB)
A. A. Semenov, K. V. Antonov, I. A. Gribanova, “Generating additional constraints in algebraic cryptanalysis using SAT oracles”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 104–110
Citation in format AMSBIB
\by A.~A.~Semenov, K.~V.~Antonov, I.~A.~Gribanova
\paper Generating additional constraints in algebraic cryptanalysis using SAT oracles
\jour Prikl. Diskr. Mat. Suppl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|