TrES: Tropical Encryption Scheme Based on Double Key Exchange


  •   Mariana Ivanova Durcheva


Shor’s quantum algorithm establishes a polynomial time attack on the discrete logarithm problem in any group. Recent announcements of progress in building quantum computers highlight the need for new concepts to create cryptosystems that are resistant to quantum attacks. In this paper, we present а new message encryption scheme. To enhance the security of the scheme, we suggest double key-exchange protocol (KEP). The first stage of the key exchange uses a matrix power function (MPF) in a tropical semiring. These functions are based on the action of a matrix semiring acting on some matrix set. MPFs can be considered as one-way functions because they are based on some generalized satisfiability problems that are potentially NP-complete. The obtained shared secret key at the first stage of the key exchange serves as an input for the second stage. The security of the second phase relies on the difficulty of the semiring action problem. In our protocol, we suggest using left or right action of the tropical semiring (which can be both min-plus and max-plus) on the group of commutative matrices (circulant matrices, in our case). The fact that the key-exchange protocol works in two phases contributes to its security, since an attacker needs to solve two difficult problems in order to break it. The main advantages of the presented protocol are: the increased efficiency and improved security.

Keywords: Key-exchange protocol, matrix power function, message encryption scheme, tropical semiring


Sakalauskas E, Listopadskis N, Tvarijonas P. Key agreement protocol (KAP) based on matrix power function. Advanced Studies in Software and Knowledge Engineering, Information Science and Computing. 2008: 92–96.

Sakalauskas E, Mihalkovich A. New Asymmetric Cipher of Non-Commuting Cryptography Class Based on Matrix Power Function. INFORMATICA. 2014; 25(2): 283–298.

Liu J, Zhang H, Jia J. A linear algebra attack on the non-commuting cryptography class based on matrix power function. International Conference on Information Security and Cryptology, Springer: Cham, Switzerland, 2016: 343–354.

Sakalauskas E, Mihalkovich A. MPF Problem over Modified Medial Semigroup Is NP‐complete. Symmetry 2018; 10: 571.

Mihalkovich A, Sakalauskas E, Luksys K. Key Exchange Protocol Defined over a Non‐Commuting Group Based on an NP‐ complete Decisional Problem. Symmetry 2020; 12(9): 1389,

Sakalauskas E. Enhanced matrix power function for cryptographic primitive construction, Symmetry. 2018; 10(2): 43.

Sakalauskas E, Mihalkovich A. New Asymmetric Cipher of Non-Commuting Cryptography Class Based on Matrix Power Function. INFORMATICA. 2017; 28(3): 517–524.

Grigoriev D, Shpilrain V. Tropical cryptography. Communications in Algebra. 2014; 42: 2624–2632.

Grigoriev D, Shpilrain V. Tropical cryptography II: extensions by homomorphisms. Communications in Algebra. 2019; 47(10): 4224–4229,

Durcheva M, Trendafilov I. Public Key Cryptosystem Based on Max – Semirings. AMEE, 38th International Conference, AIP Conference Proceeding. 2012; 1497(1): 357- 364.

Durcheva M. Public Key Cryptography with max-plus matrices and polynomials. AMEE 39th International Conference, AIP Conference Proceeding. 2013, 1570(1): 491–498.

Durcheva M. An application of different dioids in public key cryptography. AMEE 40th International Conference, AIP Conference Proceeding. 2014; 1631(1): 336–345.

Durcheva M, Rachev M. A public key encryption scheme based on idempotent semirings. AMEE 41th International Conference, AIP Conference Proceeding. 2015; 1690(1): 060008.

Ahmed K, Pal S, Mohan R. A review of the tropical approach in cryptography. Cryptologia. 2022.

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

Isaac S, Kahrobaei D. A closer look at the tropical cryptography. International Journal of Computer Mathematics: Computer Systems Theory. 2021; 6(2): 137-142.

Muanalifah A, Sergeev S. On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product. Communications in Algebra. 2020.

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

Rahman N, Shpilrain V. MAKE: A matrix action key exchange. Journal of Mathematical Cryptology. 2022; 16(1): 64-72.

Brown DRL, Koblitz N, LeGrow JT. Cryptanalysis of “MAKE”, Journal of Mathematical Cryptology. 2022; 16: 98–102.

Battarbee C, Kahrobaei D, Shahandashti S. Semidirect Product Key Exchange: the State of Play, Arxiv. [Preprint] 2022. Available from:

Ayoub M. Key Exchange Protocol Based on MPF and Circulant Matrix over Tropical Algebras. M. S. Thesis. Capital University of Science and Technology, Islamabad, 2021.

Durcheva M. Semirings as building blocks in cryptography. Monograph, Cambridge Scholars Publishing. 2020.

Pin J-E. Tropical Semirings. 1998: 50-69.

Davis PJ. Circulant Matrices. 1994.

Fuhrmann PA. A Polynomial Approach to Linear Algebra. Universitext, Springer. 1996.

Bassino F, Kapovich I, Lohrey M, Miasnikov A, Nicaud C, Nikolaev A, et al. 6 Problems in group theory motivated by cryptography, Complexity and Randomness in Group Theory: GAGTA BOOK 1. 2020: 317-348.

Singh G, Supriya. A Study of Encryption Algorithms (RSA, DES, 3DES and AES) for Information Security. International Journal of Computer Applications. 2013; 67(19).

Marqas RB, Almufti SM, Ihsan RR. Comparing Symmetric and Asymmetric cryptography in message encryption and decryption by using AES and RSA algorithms. Journal of Xi'an University of Architecture & Technology. 2020; III(1006-7930).

Mihalkovich A, Levinskas M. Investigation of Matrix Power Asymmetric Cipher Resistant to Linear Algebra Attack. Springer Nature Switzerland AG 2019. 2019: 197–208.


How to Cite
Durcheva, M. I. (2022). TrES: Tropical Encryption Scheme Based on Double Key Exchange. European Journal of Information Technologies and Computer Science, 2(4), 11–17.