Cryptanalysis of Ushakov--Shpilrain's authentication protocol based on the twisted conjugacy problem

M. N. Gornova ; E. G. Kukina ; V. A. Romankov

Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 46-53.

Résumé

We give a cryptanalysis of Ushakov–Shpilrain's authentication protocol based on the twisted conjugacy problem for a pair of endomorphisms on the semigroup of all $2\times2$ matrices over the ring of truncated one-variable polynomials over the field $\mathbb F_2$. It is shown that the private key of the protocol can be computed by solving the system of linear equations over $\mathbb F_2$. We present a theoretical estimation for the complexity of this cryptanalysis and describe practical results obtained in a computer experiment. It is shown that the protocol is theoretically and practically vulnerable.

Détail

Keywords: cryptography, authentication, twisted conjugacy, truncated polynomials.
Mots-clés : endomorphism

Bibliographie

[1] Myasnikov A., Shpilrain V., Ushakov A., Group-Based Cryptography, Advances courses in Math., CRM, Birkhäuser Verlag, Barselona–Basel–Berlin–New York, 2008, 183 pp. | MR | Zbl

[2] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative Cryptography and Complexity of Group-Theoretic Problems, Amer. Math. Soc. Surveys and Monographs, 177, Amer. Math. Soc., Providence, R.I., 2011, 385 pp. | MR | Zbl

[3] Roman'kov V A., “Diophantine cryptography over infinite groups”, Prikladnaya Diskretnaya Matematika, 2012, no. 2(16), 15–42 (in Russian)

[4] Roman'kov V. A., Algebraic Cryptography, OmSU Publ., Omsk, 2013, 135 pp. (in Russian)

[5] Shpilrain V., Ushakov A., “An authentication scheme based on the twisted conjugacy problem”, ACNS'2008, LNCS, 5037, 2008, 366–372

[6] Fel'shtyn A., Troitsky E., “Twisted Burnside–Frobenius theory for discrete groups”, J. Reine Angew. Math., 613 (2007), 193–210 | MR | Zbl

[7] Goncalves D., Wong P., “Twisted conjugacy classes in nilpotent groups”, J. Reine Angew. Math., 633 (2009), 11–27 | MR | Zbl

[8] Roman'kov V., “The twisted conjugacy problem in polycyclic groups”, J. Group Theory, 13:3 (2010), 353–364 | MR

[9] Ventura E., Roman'kov V. A., “The twisted conjugacy problem for endomorphisms of metabelian groups”, Algebra and Logic, 48:2 (2009), 89–98 | MR | Zbl

[10] Roman'kov V., “Twisted conjugacy classes in nilpotent groups”, J. Pure Appl. Algebra, 215:4 (2011), 664–671 | MR | Zbl

[11] Fel'shtyn A., Goncalves D. L., “Reidemeister spectrum for metabelian groups”, Int. J. Algebra Comput., 21:3 (2011), 1–16 | MR

[12] Remeslennikov V N., Roman'kov V. A., “Model-theoretic and algorithmic problems in group theory”, Itogi Nauki i Tekhn. Ser. Algebra. Geometriya. Topologiya, 21, VINITI Publ., Moscow, 1983, 3–79 (in Russian) | MR | Zbl

[13] Miller C. F., “Decision problems for groups: survey and reflections”, Algorithms and Classification in Combinatorial Group Theory, MSRI Publications, 23, eds. G. Baumslag, C. F. Miller III, 1992, 1–59 | MR | Zbl

[14] Roman'kov V A., “Cryptanalysis of some schemes applying automorphisms”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 36–51 (in Russian)

[15] Roman'kov V., Myasnikov A., A linear decomposition attack, 19 Dec. 2014, arXiv: 1412.6401v1[math.GR]

[16] Roman'kov V., A polynomial time algorithm for the braid double shielded public key cryptosystem, 17 Dec. 2014, arXiv: 1412.5277v1[math.GR]

[17] Roman'kov V., Linear decomposition attack on public key exchange protocols using semidirect products of (semi)groups, 15 Jan. 2015, arXiv: 1501.01152v1[cs.CR]

[18] Bürgisser P., Clausen M., Shokrollalu M. A., Algebraic Complexity Theory, Springer, Berlin, 1997 | MR | Zbl