Geodesic
Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-Boolean optimization
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 130-134.

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

The paper introduces the concept of linearizing sets that can be considered as a generalization of known linearization sets. Linearization sets are used in algebraic attacks related to the class of guess-and-determine attacks. The idea of such attacks is to guess values of variables from a certain set and then to substitute them into a system of algebraic equations that connects the input and output data of the cipher under consideration. In some cases, the result of such procedure is a linear system that can be solved effectively. In the present paper, we consider algebraic equations over the field GF(2). The values of variables from the linearizing set (as opposed to the linearization set) linearize the system of equations with a certain probability, which, generally speaking, can be substantially less than 1. The complexity estimation for guess-and-determine attack based on a particular linearizing set is constructed using a specially defined pseudo-Boolean function. The minimum value of this function gives a complexity estimation for the attack with best efficiency. To minimize such functions, a metaheuristic algorithm from the class of tabu search algorithms is used. At the current stage, attacks of the described type are built for some cryptographic generators. In particular, for the well-known A5/1 generator, the presented method allows to construct a guess-and-determine attack which complexity is 4.5 times lower than the complexity of Anderson's attack.
Keywords: guess-and-determine attacks, linearizing sets, pseudo-Boolean optimization. 
@article{PDMA_2019_12_a37,
     author = {A. A. Semenov and K. V. Antonov and I. V. Otpushchennikov},
     title = {Search for linearizing sets in algebraic cryptanalysis as a problem of {pseudo-Boolean} optimization},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {130--134},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a37/}
}
TY  - JOUR
AU  - A. A. Semenov
AU  - K. V. Antonov
AU  - I. V. Otpushchennikov
TI  - Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-Boolean optimization
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 130
EP  - 134
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a37/
LA  - ru
ID  - PDMA_2019_12_a37
ER  - 
%0 Journal Article
%A A. A. Semenov
%A K. V. Antonov
%A I. V. Otpushchennikov
%T Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-Boolean optimization
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 130-134
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a37/
%G ru
%F PDMA_2019_12_a37
A. A. Semenov; K. V. Antonov; I. V. Otpushchennikov. Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-Boolean optimization. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 130-134. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a37/

[1] Agibalov G. P., “Logicheskie uravneniya v kriptoanalize generatorov klyuchevogo potoka”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2003, no. 6, 31–41

[2] Bard G., Algebraic Cryptanalysis., Springer Publishing Company, Inc., 2009 | MR | Zbl

[3] Goldreich O., Computational Complexity: A Conceptual Perspective, Cambridge University Press, Cambridge, 2008 | MR | Zbl

[4] Chen Ch., Li R., Matematicheskaya logika i avtomaticheskoe dokazatelstvo teorem, Nauka, M., 1983

[5] Semenov A., Zaikin O., Otpuschennikov I., et al., “On cryptographic attacks using backdoors for SAT”, Thirty-Second AAAI Conf. (2018), 6641–6648, arXiv: 1803.04646

[6] Metropolis N., Ulam S., “The Monte Carlo method”, J. Amer. Statistical Association, 44:247 (1949), 335–341 | DOI | MR | Zbl

[7] Boros E., Hammer P., “Pseudo-Boolean optimization”, Discr. Appl. Math., 123:1–3 (2002), 155–225 | DOI | MR | Zbl

[8] Glover F., Laguna M., Tabu Search, Kluwer Academic Publishers, Norwell, 1997

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

[10] Otpuschennikov I. V., Semenov A. A., “Tekhnologiya translyatsii kombinatornykh problem v bulevy uravneniya”, Prikladnaya diskretnaya matematika, 2011, no. 1(11), 96–115

[11] Otpuschennikov I., Semenov A., Gribanova I., et al., “Encoding cryptographic functions to SAT using TRANSALG system”, Frontiers in Artificial Intelligence and Applications, 285 (2016), 1594–1595

[12] Anderson R., A5 (Was: Hacking digital phones), Newsgroup Communication, , 1994 http://yarchive.net/phone/gsmcipher.html