Public key exchange protocols based on tropical lower circulant and anti circulant matrices

B. Amutha; R. Perumal; B. Amutha; R. Perumal

doi:10.3934/math.2023885

AIMS Mathematics

2023, Volume 8, Issue 7: 17307-17334. doi: 10.3934/math.2023885

Previous Article Next Article

Research article

Public key exchange protocols based on tropical lower circulant and anti circulant matrices

B. Amutha ,
R. Perumal ^,

Department of Mathematics, Faculty of Engineering and Technology, SRM Institute of Science and Technology, Kattankulathur 603203, Tamilnadu, India

Received: 27 January 2023 Revised: 24 April 2023 Accepted: 08 May 2023 Published: 19 May 2023
MSC : 11T71, 14G50, 14M25, 15B51, 52B20

In recent years, many efficient key exchange protocols have been proposed based on matrices over the tropical semirings. The tropical addition of two elements is the minimum of the elements, while the tropical multiplication is the sum of the two elements. This paper proposes a novel key exchange protocol based on the min-plus semiring ($ \mathbb{Z}\cup\{\infty\}, \oplus, \otimes $) by introducing anti-$ s $-$ p $-circulant matrices, which forms a commutative subset of $ M_{n \times n}(\mathbb{Z}\cup \{\infty\}) $. We have given further analysis of the protocol in detail using upper or lower-$ s $-circulant matrices. Additionally, we prove that the set of all lower-$ s $-circulant matrices is a sub-semiring of the tropical semiring $ M_{n \times n}(\mathbb{Z}\cup \{\infty\}) $. We discuss the detailed security analysis of the protocol with upper or lower-$ s $-circulant matrices and provide cryptographic algorithms for both key exchange protocols with detailed explanations. We compare the protocol based on upper or lower-$ s $-circulant matrices and our proposed protocol in terms of time complexity and memory usage. Finally, we analyse the security and show that our protocol is safe against popular attacks of tropical key exchange protocols. The security of these protocols relies on the difficulty of solving tropical non-linear equations.
- lower-$ s $-circulant matrix,
- anti-$ s $-$ p $-circulant matrix,
- tropical semiring,
- tropical cryptography,
- key exchange protocol
Citation: B. Amutha, R. Perumal. Public key exchange protocols based on tropical lower circulant and anti circulant matrices[J]. AIMS Mathematics, 2023, 8(7): 17307-17334. doi: 10.3934/math.2023885

Related Papers:

Abstract

In recent years, many efficient key exchange protocols have been proposed based on matrices over the tropical semirings. The tropical addition of two elements is the minimum of the elements, while the tropical multiplication is the sum of the two elements. This paper proposes a novel key exchange protocol based on the min-plus semiring ($ \mathbb{Z}\cup\{\infty\}, \oplus, \otimes $) by introducing anti-$ s $-$ p $-circulant matrices, which forms a commutative subset of $ M_{n \times n}(\mathbb{Z}\cup \{\infty\}) $. We have given further analysis of the protocol in detail using upper or lower-$ s $-circulant matrices. Additionally, we prove that the set of all lower-$ s $-circulant matrices is a sub-semiring of the tropical semiring $ M_{n \times n}(\mathbb{Z}\cup \{\infty\}) $. We discuss the detailed security analysis of the protocol with upper or lower-$ s $-circulant matrices and provide cryptographic algorithms for both key exchange protocols with detailed explanations. We compare the protocol based on upper or lower-$ s $-circulant matrices and our proposed protocol in terms of time complexity and memory usage. Finally, we analyse the security and show that our protocol is safe against popular attacks of tropical key exchange protocols. The security of these protocols relies on the difficulty of solving tropical non-linear equations.

References

[1]	F. Piper, S. Murphy, Cryptography: a very short introduction, New York: Oxford Academic, 2002. https://doi.org/10.1093/actrade/9780192803153.003.0001
[2]	G. Manikandan, R. Perumal, Symmetric cryptography for secure communication in IoT, Materials Today: Proceedings, 2020 (2020), 737. https://doi.org/10.1016/j.matpr.2020.09.737 doi: 10.1016/j.matpr.2020.09.737
[3]	S. Arshad, M. Khan, New extension of data encryption standard over 128-bit key for digital images, Neural Comput. Applic., 33 (2021), 13845–13858. https://doi.org/10.1007/s00521-021-06023-5 doi: 10.1007/s00521-021-06023-5
[4]	E. Fernando, D. Agustin, M. Irsan, D. F. Murad, H. Rohayani, D. Sujana, Performance comparison of symmetries encryption algorithm AES and DES with raspberry Pi, 2019 International Conference on Sustainable Information Engineering and Technology (SIET), Lombok, Indonesia, 2019,353–357. http://doi.org/10.1109/SIET48054.2019.8986122
[5]	A. J. Menezes, P. C. V. Oorschot, S. A. Vanstone, Handbook of applied cryptography, 1 Eds., Boca Raton: CRC Press, 1997. https://doi.org/10.1201/9780429466335
[6]	K. Ahmed, S. Pal, R. Mohan, A review of the tropical approach in cryptography, Cryptologia, 47 (2023), 63–87. https://doi.org/10.1080/01611194.2021.1994486 doi: 10.1080/01611194.2021.1994486
[7]	Y. W. Kao, K. Y. Huang, H. Z. Gu, S. M. Yuan, uCloud: a user-centric key management scheme for cloud data protection, IET Inform. Secur., 7 (2013), 144–154. https://doi.org/10.1049/iet-ifs.2012.0198 doi: 10.1049/iet-ifs.2012.0198
[8]	M. Habeeb, D. Kahrobaei, C. Koupparis, V. Shpilrain, Public key exchange using semidirect product of (semi) groups, In: Applied cryptography and network security, Heidelberg: Springer, 2013,475–486. https://doi.org/10.1007/978-3-642-38980-1_30
[9]	M. Kreuzer, A. D. Myasnikov, A. Ushakov, A linear algebra attack to group-ring-based key exchange protocols, In: Applied cryptography and network security, Cham: Springer, 2014, 37–43. https://doi.org/10.1007/978-3-319-07536-5_3
[10]	D. Kahrobaei, C. Koupparis, V. Shpilrain, A CCA secure cryptosystem using matrices over group rings, Contemporary Mathematics, 633 (2015), 73–81. http://doi.org/10.1090/conm/633/12652 doi: 10.1090/conm/633/12652
[11]	W. Diffie, M. Hellman, New directions in cryptography, IEEE T. Inform. Theory, 22 (1976), 644–654. http://doi.org/10.1109/TIT.1976.1055638 doi: 10.1109/TIT.1976.1055638
[12]	V. Shpilrain, Cryptanalysis of Stickel's key exchange scheme, In: Computer science–theory and applications, Berlin: Springer, 2008,283–288. http://doi.org/10.1007/978-3-540-79709-8_29
[13]	D. Grigoriev, V. Shpilrain, Tropical cryptography, Commun. Algebra, 42 (2014), 2624–2632. http://doi.org/10.1080/00927872.2013.766827 doi: 10.1080/00927872.2013.766827
[14]	Z. Izhakian, Basics of linear algebra over the extended tropical semiring, Contemporary Mathematics, 495 (2009), 173–191.
[15]	Z. Izhakian, L. Rowen, The tropical rank of a tropical matrix, Commun. Algebra, 37 (2009), 3912–3927. https://doi.org/10.1080/00927870902828793 doi: 10.1080/00927870902828793
[16]	D. Jones, Matrix roots in the max-plus algebra, Linear Algebra Appl., 631 (2021), 10–34. https://doi.org/10.1016/j.laa.2021.08.008 doi: 10.1016/j.laa.2021.08.008
[17]	M. Kotov, A. Ushakov, Analysis of a key exchange protocol based on tropical matrix algebra, J. Math. Cryptol., 12 (2018), 137–141. https://doi.org/10.1515/jmc-2016-0064 doi: 10.1515/jmc-2016-0064
[18]	D. Grigoriev, V. Shpilrain, Tropical cryptography Ⅱ: extensions by homomorphisms, Commun. Algebra, 47 (2019), 4224–4229. https://doi.org/10.1080/00927872.2019.1581213 doi: 10.1080/00927872.2019.1581213
[19]	D. Rudy, C. Monico, Remarks on a tropical key exchange system, J. Math. Cryptol., 15 (2021), 280–283. https://doi.org/10.1515/jmc-2019-0061 doi: 10.1515/jmc-2019-0061
[20]	S. Isaac, D. Kahrobaei, A closer look at the tropical cryptography, Int. J. Comput. Math., 6 (2021), 137–142. https://doi.org/10.1080/23799927.2020.1862303 doi: 10.1080/23799927.2020.1862303
[21]	H. Huang, C. Li, L. Deng, Public-key cryptography based on tropical circular matrices, Appl. Sci., 12 (2022), 7401. https://doi.org/10.3390/app12157401 doi: 10.3390/app12157401
[22]	F. Olia, S. Ghalandarzadeh, A. Amiraslani, S. Jamshidvand, Solving linear systems over tropical semirings through normalization method and its applications, J. Algebra Appl., 20 (2021), 2150159. https://doi.org/10.1142/S0219498821501590 doi: 10.1142/S0219498821501590
[23]	F. Mohammadi, M. Michałek, B. Sturmfels: "invitation to nonlinear algebra", Jahresber. Dtsch. Math. Ver., 124 (2022), 197–204. https://doi.org/10.1365/s13291-022-00252-w doi: 10.1365/s13291-022-00252-w
[24]	A. Muanalifah, S. Sergeev, Modifying the tropical version of stickel's key exchange protocol, Appl. Math., 65 (2020), 727–753. https://doi.org/10.21136/AM.2020.0325-19 doi: 10.21136/AM.2020.0325-19
[25]	S. Mehmood, Key exchange protocol based on matrices using tropical algebra, Master Thesis, Capital University of Science and Science and Technology, 2019.
[26]	M. I. Durcheva, Public key cryptography with max-plus matrices and polynomials, AIP Conference Proceedings, 1570 (2013), 491–498. http://doi.org/10.1063/1.4854794 doi: 10.1063/1.4854794

Reader Comments

Your name:*

Email:*
© 2023 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)