On the security of the STR key exchange protocol

Aleksejus Mihalkovich; Aleksejus Mihalkovich

doi:10.3934/math.2025092

AIMS Mathematics

2025, Volume 10, Issue 2: 1967-1980. doi: 10.3934/math.2025092

Previous Article Next Article

Research article

On the security of the STR key exchange protocol

Aleksejus Mihalkovich ^,

Department of Applied Mathematics, Kaunas University of Technology, Studentu Str. 50, Kaunas, LT-51368, Lithuania

Received: 11 October 2024 Revised: 05 December 2024 Accepted: 16 December 2024 Published: 07 February 2025
MSC : 15A16, 15A18, 15A20, 94A60

In this paper, we consider the security of the Sakalauskas-Tvarijonas-Raulynaitis (STR) key exchange protocol. We perform an analysis by exploring various cases of the canonical form of the publicly known matrix using elements of linear algebra and number theory. Additionally, we consider the multiplicative order of matrices and show how these two factors affect the security of the considered protocol. We show that regardless of the choice of publicly known matrix, the considered protocol is secure under the discrete logarithm assumption. In other words, if at least one of the secret exponents is found, then the STR protocol can be broken in polynomial time.
- security analysis,
- noncommutative cryptography,
- key exchange protocol,
- linear algebra,
- canonical forms
Citation: Aleksejus Mihalkovich. On the security of the STR key exchange protocol[J]. AIMS Mathematics, 2025, 10(2): 1967-1980. doi: 10.3934/math.2025092

Related Papers:

Abstract

In this paper, we consider the security of the Sakalauskas-Tvarijonas-Raulynaitis (STR) key exchange protocol. We perform an analysis by exploring various cases of the canonical form of the publicly known matrix using elements of linear algebra and number theory. Additionally, we consider the multiplicative order of matrices and show how these two factors affect the security of the considered protocol. We show that regardless of the choice of publicly known matrix, the considered protocol is secure under the discrete logarithm assumption. In other words, if at least one of the secret exponents is found, then the STR protocol can be broken in polynomial time.

References

[1]	I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287–291, https://doi.org/10.4310/MRL.1999.v6.n3.a3 doi: 10.4310/MRL.1999.v6.n3.a3
[2]	K. Ko, S. Lee, J. Cheon, J. W. Han, J. S. Kang, C. Park, New public-key cryptosystem using braid groups, In: M. Bellare, Advances in cryptology-CRYPTO 2000, Springer, 2000,166–183. https://doi.org/10.1007/3-540-44598-6_10
[3]	V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography: unnecessary and insufficient, Appl. Algebra Eng. Commun. Comput., 17 (2006), 285–289, http://doi.org/10.1007/s00200-006-0009-6 doi: 10.1007/s00200-006-0009-6
[4]	E. Sakalauskas, P. Tvarijonas, A. Raulynaitis, Key agreement protocol (KAP) using conjugacy and discrete logarithm problems in group representation level, Informatica, 18 (2007), 115–124. http://doi.org/10.15388/Informatica.2007.167 doi: 10.15388/Informatica.2007.167
[5]	M. Eftekhari, A Diffie-Hellman key exchange using matrices over non-commutative rings, Groups Complexity Cryptology, 4 (2012), 167–176. http://doi.org/10.1515/gcc-2012-0001 doi: 10.1515/gcc-2012-0001
[6]	M. Sracic, Quantum circuits for matrix multiplication, Comput. Sci. Phys. Math., 2011.
[7]	A. Myasnikov, A. Ushakov, Quantum algorithm for discrete logarithm problem for matrices over finite group rings, Groups Complexity Cryptology, 6 (2014), 31–36. http://doi.org/10.1515/gcc-2014-0003 doi: 10.1515/gcc-2014-0003
[8]	A. Myasnikov, A. Ushakov, Cryptanalysis of matrix conjugation schemes, J. Math. Cryptology, 8 (2014), 95–114. http://doi.org/10.1515/jmc-2012-0033 doi: 10.1515/jmc-2012-0033
[9]	A. Pandey, I. Gupta, D. K. Singh, On the security of DLCSP over $GL_n(\mathbb {F}_q[S_r])$, Appl. Algebra Eng. Commun. Comput., 34 (2023), 619–628. http://doi.org/10.1007/s00200-021-00523-6 doi: 10.1007/s00200-021-00523-6
[10]	D. Boneh, V. Shoup, A graduate course in applied cryptography, Draft 0.5, 2023.
[11]	P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41 (1999), 303–332. http://doi.org/10.1137/S0097539795293172 doi: 10.1137/S0097539795293172

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)