Abstract

We present a comprehensive cryptanalysis of a tropical key exchange primitive based on the semidirect product of tropical matrices. While the scheme has previously been subjected to three successful attacks, our study introduces a more efficient and robust approach that significantly improves the computational efficiency and reliability compared to the earlier methods that help achieve an almost 100% success rate. This work also highlights significant vulnerabilities in using tropical matrices as tools for secure exchanges. 

Author

K Ahmed 1, S Pal 2, R Mohan   ( Pages 223-242 )
Email:kashif.ahmed@ststephens.edu
Affiliation: 1 St. Stephen’s College, University of Delhi, Delhi, India       DOI: https://doi.org/10.58517/ITMSC.2025.18209

Keyword

Cryptanalysis, Tropical key exchange scheme

References

1. Ahmed, K., Pal, S., Mohan, R.: A review of the tropical approach in cryptography. Cryptologia, 1–25 (2021)

2. Baccelli, F., Cohen, G. A., Olsder, G. A., Quadrat, J. -P.: Synchronization and linearity: An algebra for discrete event systems. Journal of the Operational Research Society 45, 118–119 (1994)

3. Golan, J.: Semirings and their Applications. Springer Science & Business Media, (2013)

4.Gondran, M., Minoux, M.: Graphs, dioids and semirings: new models and algorithms. Springer Science & Business Media, (2008)

5. Isaac, S., Kahrobaei, D.: A closer look at the Tropical Cryptography. International Journal of Computer Mathematics: Computer Systems Theory, 1–6 (2021)

6. Izhakian, Z.: Tropical Arithmetic and Matrix Algebra. Communications in Algebra 37, 1445–1468 (2009)

7. Grigoriev, D., Shpilrain, V.: Tropical Cryptography. Communications in Algebra 42, 2624{2632 (2014)

8. Grigoriev, D., Shpilrain, V.: Tropical Cryptography II. Communications in Algebra 47, 4224{4229 (2019)

9. Kotov, M., Ushakov, A.: Analysis of a Key Exchange Protocol based on Tropical Matrix Algebra. Journal of Mathematical Cryptology 12, 137{141 (2018)

10. Muanalifah, A., Sergeev, S.: On the Tropical Discrete Logarithm Problem and Security of a Protocol based on Tropical Semidirect Product. Communications in Algebra 50(2), 861{879 (2021)

11. Nachtigall, K. et al.: Powers of matrices over an extremal algebra with applications to periodic graphs. Mathematical Methods of Operations Research 46, 87–102 (1997)

12. Pin, J.: Tropical Semirings. In Idempotency, Cambridge Univ. Press, Cambridge, 50–79 (1998)

13. Rudy, D., Monico, C.: Remarks on a Tropical Key Exchange System’. Journal of Mathematical Cryptology 15, 280–283 (2020)

14. Speyer, D., Sturmfels, B.: Tropical Mathematics. Mathematics Magazine 3, 163–173 (2009)