TrES: Tropical Encryption Scheme Based on Double Key Exchange



Abstract Views
359

Downloads
342

Citations

Share

##plugins.themes.bootstrap3.article.sidebar##

Submitted Jun 4, 2022
Published Aug 29, 2022
10.24018/compute.2022.2.4.70

Abstract viewed = 359 times

Table of Contents

##plugins.themes.bootstrap3.article.main##

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

References

  1. 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.
     Google Scholar
  2. Sakalauskas E, Mihalkovich A. New Asymmetric Cipher of Non-Commuting Cryptography Class Based on Matrix Power Function. INFORMATICA. 2014; 25(2): 283–298.
     Google Scholar
  3. 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.
     Google Scholar
  4. Sakalauskas E, Mihalkovich A. MPF Problem over Modified Medial Semigroup Is NP‐complete. Symmetry 2018; 10: 571.
     Google Scholar
  5. 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,
     Google Scholar
  6. Sakalauskas E. Enhanced matrix power function for cryptographic primitive construction, Symmetry. 2018; 10(2): 43.
     Google Scholar
  7. Sakalauskas E, Mihalkovich A. New Asymmetric Cipher of Non-Commuting Cryptography Class Based on Matrix Power Function. INFORMATICA. 2017; 28(3): 517–524.
     Google Scholar
  8. Grigoriev D, Shpilrain V. Tropical cryptography. Communications in Algebra. 2014; 42: 2624–2632.
     Google Scholar
  9. Grigoriev D, Shpilrain V. Tropical cryptography II: extensions by homomorphisms. Communications in Algebra. 2019; 47(10): 4224–4229,
     Google Scholar
  10. Durcheva M, Trendafilov I. Public Key Cryptosystem Based on Max – Semirings. AMEE, 38th International Conference, AIP Conference Proceeding. 2012; 1497(1): 357- 364.
     Google Scholar
  11. Durcheva M. Public Key Cryptography with max-plus matrices and polynomials. AMEE 39th International Conference, AIP Conference Proceeding. 2013, 1570(1): 491–498.
     Google Scholar
  12. Durcheva M. An application of different dioids in public key cryptography. AMEE 40th International Conference, AIP Conference Proceeding. 2014; 1631(1): 336–345.
     Google Scholar
  13. Durcheva M, Rachev M. A public key encryption scheme based on idempotent semirings. AMEE 41th International Conference, AIP Conference Proceeding. 2015; 1690(1): 060008.
     Google Scholar
  14. Ahmed K, Pal S, Mohan R. A review of the tropical approach in cryptography. Cryptologia. 2022.
     Google Scholar
  15. Kotov M, Ushakov A. Analysis of a Key Exchange Protocol based on Tropical Matrix Algebra. Journal of Mathematical Cryptology. 2018; 12(3): 137–141.
     Google Scholar
  16. Isaac S, Kahrobaei D. A closer look at the tropical cryptography. International Journal of Computer Mathematics: Computer Systems Theory. 2021; 6(2): 137-142.
     Google Scholar
  17. Muanalifah A, Sergeev S. On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product. Communications in Algebra. 2020.
     Google Scholar
  18. Rudy D, Monico C. Remarks on a Tropical Key Exchange System. Journal of Mathematical Cryptology. 2020; 15(1): 280–283.
     Google Scholar
  19. Rahman N, Shpilrain V. MAKE: A matrix action key exchange. Journal of Mathematical Cryptology. 2022; 16(1): 64-72.
     Google Scholar
  20. Brown DRL, Koblitz N, LeGrow JT. Cryptanalysis of “MAKE”, Journal of Mathematical Cryptology. 2022; 16: 98–102.
     Google Scholar
  21. Battarbee C, Kahrobaei D, Shahandashti S. Semidirect Product Key Exchange: the State of Play, Arxiv. [Preprint] 2022. Available from: https://arxiv.org/pdf/2202.05178.pdf.
     Google Scholar
  22. 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.
     Google Scholar
  23. Durcheva M. Semirings as building blocks in cryptography. Monograph, Cambridge Scholars Publishing. 2020.
     Google Scholar
  24. Pin J-E. Tropical Semirings. 1998: 50-69.
     Google Scholar
  25. Davis PJ. Circulant Matrices. 1994.
     Google Scholar
  26. Fuhrmann PA. A Polynomial Approach to Linear Algebra. Universitext, Springer. 1996.
     Google Scholar
  27. 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.
     Google Scholar
  28. Singh G, Supriya. A Study of Encryption Algorithms (RSA, DES, 3DES and AES) for Information Security. International Journal of Computer Applications. 2013; 67(19).
     Google Scholar
  29. 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).
     Google Scholar
  30. Mihalkovich A, Levinskas M. Investigation of Matrix Power Asymmetric Cipher Resistant to Linear Algebra Attack. Springer Nature Switzerland AG 2019. 2019: 197–208.
     Google Scholar