Efficient methods of algebraic cryptanalysis and protection against them

V. A. Roman'kov

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 117-125.

Résumé

The paper contains the basic information about methods of cryptanalysis used in algebraic cryptography. Main elements of linear and non-linear decomposition attacks by the author and so-called span-method by B. Tsaban are described as well as the examples of using them. To protect existing cryptographic algorithms against the cryptanalytic attacks, some improvements of this algorithms are proposed. For this purpose, the author has introduced the concept of a marginal set and with the use of it has protected the widely known key distibution protocol AAG against the attack by the span-method.

Détail

Keywords: algebraic cryptography
Mots-clés : algebraic cryptanalysis.

Bibliographie

[1] Romankov V. A., “Kriptograficheskii analiz nekotorykh skhem shifrovaniya, ispolzuyuschikh avtomorfizmy”, Prikladnaya diskretnaya matematika, 2013, no. 3(21), 35–51

[2] Romankov V. A., Algebraicheskaya kriptografiya, OmGU, Omsk, 2013

[3] Myasnikov A., Roman'kov V., “A linear decomposition attack”, Groups, Complexity, Cryptology, 7 (2015), 81–94 | DOI | MR | Zbl

[4] Romankov V. A., Obzor A. A., “Obschaya algebraicheskaya skhema raspredeleniya kriptograficheskikh klyuchei i ee kriptoanaliz”, Prikladnaya diskretnaya matematika, 2017, no. 37, 52–61

[5] Romankov V. A., Obzor A. A., “Metod nelineinogo razlozheniya dlya analiza kriptograficheskikh skhem, ispolzuyuschikh avtomorfizmy grupp”, Prikladnaya diskretnaya matematika, 2018, no. 41, 38–45

[6] Roman'kov V. A., Essays in Algebra and Cryptology. Algebraic Cryptanalysis, OmSU, Omsk, 2018 | MR

[7] Tsaban B., “Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography”, J. Cryptology, 28 (2015), 601–622 | DOI | MR | Zbl

[8] Ben-Zvi A., Kalka A., Tsaban B., “Cryptanalysis via algebraic spans”, CRYPTO 2018, LNCS, 10991, 2018, 1–20 | MR

[9] Cheon J. H., Jun B., “A polynomial time algorithm for the braid Diffie — Hellman Conjugacy Problem”, CRYPTO-2003, LNCS, 2729, 2003, 212–225 | DOI | MR | Zbl

[10] Tsaban B., “The Conjugacy Problem: Cryptoanalytic Approaches to a Problem of Dehn”, Minicourse (Dusseldorf University, Germany, July–August 2012) http://reh.math.uni-duesseldorf.de/g̃agta/slides/Tsaban_minicourses.pdf | MR

[11] Roman'kov V., “A non-linear decomposition attack”, Groups, Complexity, Cryptology, 8 (2015), 197–207 | MR

[12] Romankov V. A., “Kriptograficheskii analiz modifitsirovannoi matrichnoi modulyarnoi kriptosistemy”, Vestnik Omskogo un-ta, 23 (2018), 44–50

[13] Roman'kov V., “Two general schemes of algebraic cryptography”, Groups, Complexity, Cryptology, 10 (2018), 83–98 | MR | Zbl

[14] Roman'kov V. A., “A Polynomial Time Algorithm for the Braid Double Shielded Public Key Cryptosystems”, Bulletin of the Karaganda University. Mathematics Ser., 2016, no. 4(84), 110–115 ; 17 Dec. 2014, 7 pp., arXiv: 1412.5277v1 [math.GR] | DOI

[15] Gornova M. N., Kukina E. G., Romankov V. A., “Kriptograficheskii analiz protokola autentifikatsii Ushakova — Shpilraina, osnovannogo na probleme binarno skruchennoi sopryazhennosti”, Prikladnaya diskretnaya matematika, 2015, no. 2(28), 46–53

[16] Romankov V. A., “Metod lineinogo razlozheniya analiza protokolov skrytoi informatsii na algebraicheskikh platformakh”, Algebra i logika, 54:1 (2015), 119–128 | MR | Zbl

[17] Roman'kov V. A., Menshov A. V., Cryptanalysis of Andrecut's Public Key Cryptosystem, 6 Jul. 2015, 5 pp., arXiv: 1507.01496v1 [math.GR] | MR

[18] Andrecut M., A Matrix Public Key Cryptosystem., 31 May 2015, 11 pp., arXiv: 1506.00277v1 [cs.CR]

[19] Gu L., Wang L., Ota K., et al., “New public key cryptosystems based on non-abelian factorization problems”, Security and Communication Networks, 6 (2013), 912–922 | DOI

[20] Gu L., Zheng S., “Conjugacy systems based on nonabelian factorization problems and their applications in cryptography”, J. Appl. Math., 2014, 630607, 10 pp. | MR

[21] Hurley B., Hurley T., Group Ring Cryptography, 9 Apr 2011, 20 pp., arXiv: 1104.1724v1 [math.GR] | MR

[22] Hurley T., Cryptographic schemes, key exchange, public key, May 2013, 19 pp., arXiv: 1305.4063v1 [cs.CR]

[23] Shpilrain V., Ushakov A., “A new key exchange protocol based on the decomposition problem”, Algebraic Methods in Cryptography, Contemp. Math., 418, 2006, 161–167 | DOI | MR | Zbl

[24] Stickel E., “A new method for exchanging secret keys”, Proc. Third Intern. Conf. ICITA 05, Contemp. Math., 2, 2005, 426–430

[25] Wang X., Xu C., Li G., et al., Double shielded public key cryptosystems, Cryptology ePrint Archive. Report 2014/558. Version 20140718:185200, 2014, 14 pp.

[26] Myasnikov A., Shpilrain V., Ushakov A., Group-Based Cryptography, Advances Courses in Math., CRM, Barselona–Basel, 2008 | MR | Zbl

[27] Myasnikov A., Shpilrain V., Ushakov A., Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Math. Surveys and Monographs, 177, AMS, Providence, RI, 2011 | DOI | MR | Zbl

[28] Ko K. H., Lee S. J., Cheon J. H., et al., “New public-key cryptosystem using braid groups”, CRYPTO 2000, LNCS, 1880, 2000, 166–183 | MR | Zbl

[29] Romankov V. A., Vvedenie v kriptografiyu, Forum, M., 2012

[30] Bigelow S., “Braid groups are linear”, J. Amer. Math. Soc., 14 (2001), 471–486 | DOI | MR | Zbl

[31] Krammer D., “Braid groups are linear”, Ann. Math., 155 (2002), 131–156 | DOI | MR | Zbl

[32] Mahalanobis A., “The Diffie — Hellman key exchange protocol and non-abelian nilpotent groups”, Israel J. Math., 165 (2008), 161–187 | DOI | MR | Zbl

[33] Roman'kov V. A., “An improved version of the AAG cryptographic protocol”, Groups, Complexity, Cryptology, 11 (2019) | MR

[34] Anshel I., Anshel M., Goldfeld D., “An algebraic method for public-key cryptography”, Math. Res. Lett., 6 (1999), 287–291 | DOI | MR | Zbl