Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat. Suppl., 2021, Issue 14, Pages 104–110 (Mi pdma542)  

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)

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.

Funding Agency Grant Number
Ministry of Science and Higher Education of the Russian Federation СП-3545.2019.5


DOI: https://doi.org/10.17223/2226308X/14/23

Full text: PDF file (630 kB)
References: PDF file   HTML file

UDC: 519.7

Citation: 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
\Bibitem{SemAntGri21}
\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.
\yr 2021
\issue 14
\pages 104--110
\mathnet{http://mi.mathnet.ru/pdma542}
\crossref{https://doi.org/10.17223/2226308X/14/23}


Linking options:
  • http://mi.mathnet.ru/eng/pdma542
  • http://mi.mathnet.ru/eng/pdma/y2021/i14/p104

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Prikladnaya Diskretnaya Matematika. Supplement
    Number of views:
    This page:10
    Full text:7
    References:1

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021