Geodesic
Generating additional constraints in algebraic cryptanalysis using SAT oracles
Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 104-110

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : algebraic cryptanalysis, SAT oracle.
Keywords: Boolean satisfiability problem (SAT), MQ systems of equations over GF(2) 
@article{PDMA_2021_14_a23,
     author = {A. A. Semenov and K. V. Antonov and I. A. Gribanova},
     title = {Generating additional constraints in algebraic cryptanalysis using {SAT} oracles},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {104--110},
     publisher = {mathdoc},
     number = {14},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2021_14_a23/}
}
TY  - JOUR
AU  - A. A. Semenov
AU  - K. V. Antonov
AU  - I. A. Gribanova
TI  - Generating additional constraints in algebraic cryptanalysis using SAT oracles
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2021
SP  - 104
EP  - 110
IS  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2021_14_a23/
LA  - ru
ID  - PDMA_2021_14_a23
ER  - 
%0 Journal Article
%A A. A. Semenov
%A K. V. Antonov
%A I. A. Gribanova
%T Generating additional constraints in algebraic cryptanalysis using SAT oracles
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2021
%P 104-110
%N 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2021_14_a23/
%G ru
%F PDMA_2021_14_a23
A. A. Semenov; K. V. Antonov; I. A. Gribanova. Generating additional constraints in algebraic cryptanalysis using SAT oracles. Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 104-110. http://geodesic.mathdoc.fr/item/PDMA_2021_14_a23/