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/

[1] Bard G., Algebraic Cryptanalysis, Springer, 2009 | MR | Zbl

[2] Cook S. A., “The complexity of theorem-proving procedures”, Proc. 3rd Ann. ACM Symp. Theory Comput., 1971, 151–158 | Zbl

[3] Levin L. A., “Universalnye zadachi perebora”, Problemy peredachi informatsii, 9:3 (1973), 115–116 | MR | Zbl

[4] Clarke E., Kroening D., Lerda F., “A tool for checking ANSI-C programs”, LNCS, 2988, 2004, 168–176 | Zbl

[5] Erkok L., Carlsson M., Wick A., “Hardware/software co-verification of cryptographic algorithms using Cryptol”, Proc. 9th Intern. Conf. FMCAD, IEEE, 2009, 188–191

[6] Otpuschennikov I., Semenov A., Gribanova I., et al., “Encoding cryptographic functions to SAT using Transalg system”, Frontiers Artificial Intell. Appl., 285 (2016), 1594–1595

[7] Kalgin K. V., Sofronova D. A., “Kompaktnyi translyator algoritmov v bulevy formuly dlya primeneniya v kriptoanalize”, Prikladnaya diskretnaya matematika. Prilozhenie, 2020, no. 13, 135–136

[8] Semenov A., Otpuschennikov I., Gribanova I., et al., “Translation of algorithmic descriptions of discrete functions to SAT with application to cryptanalysis problems”, Log. Methods Comput. Sci., 16:1 (2020), 29:1–29:42 | MR | Zbl

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986 | MR

[10] Dowling W. F., Gallier J. H., “Linear-time algorithms for testing the satisfiability of propositional horn formulae”, J. Log. Program., 1:3 (1984), 267–284 | DOI | MR | Zbl

[11] Biere A., The AIGER And-Inverter Graph (AIG) format version 20071012, Tech. Report 07/1, Institute for Formal Models and Verification, Johannes Kepler University, 2007

[12] Kipnis A., Shamir A., “Cryptanalysis of the HFE public key cryptosystem by relinearization”, LNCS, 1666, 1999, 19–30 | MR | Zbl

[13] Semenov A. A., Antonov K. V., Otpuschennikov I. V., “Poisk linearizuyuschikh mnozhestv v algebraicheskom kriptoanalize kak zadacha psevdobulevoi optimizatsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2019, no. 12, 130–134

[14] Antonov K.V., Semenov A.A., “Primenenie SAT-orakulov dlya generatsii dopolnitelnykh lineinykh ogranichenii v zadachakh kriptoanaliza nekotorykh legkovesnykh shifrov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2020, no. 13, 114–119 | MR

[15] Gribanova I. A., Semenov A. A., “Ob argumentatsii otsutstviya svoistv sluchainogo orakula u nekotorykh kriptograficheskikh khesh-funktsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2019, no. 12, 95–98

[16] TsKP Irkutskii superkompyuternyi tsentr SO RAN, http://hpc.icc.ru

[17] Beaulieu R., Shors D., Smith J., et al., “The Simon and Speck lightweight block ciphers”, Proc. 52nd Ann. Design Automation Conf. (New York, USA, 2015), 175:1–175:6

[18] Antonov K. V., Semenov A. A., “Primenenie metaevristicheskikh algoritmov psevdobulevoi optimizatsii k poisku linearizuyuschikh mnozhestv v kriptoanalize kriptograficheskikh generatorov”, Materialy 6-i Mezhdunar. shkoly-seminara «Sintaksis i semantika logicheskikh sistem», IGU, Irkutsk, 2019, 13–18

[19] Gribanova I., Semenov A., “Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4”, Proc. 41st Intern. Convention Inform. Commun. Technol. Electr. Microelectr., MIPRO, IEEE, 2018, 1174–1179

[20] Gribanova I., Semenov A., “Parallel guess-and-determine preimage attack with realistic complexity estimation for MD4-40 cryptographic hash function”, Materialy konf. «Parallelnye vychislitelnye tekhnologii (PaVT) 2019» (Kaliningrad, 2–4 aprelya 2019), 8–18