Article
Full entry |
PDF
(0.8 MB)
Feedback
PDF
(0.8 MB)
Feedback
Keywords:
public-key cryptography; key exchange protocol; cryptographic attack; tropical cryptography
public-key cryptography; key exchange protocol; cryptographic attack; tropical cryptography
Summary:
After the Kotov-Ushakov attack on the tropical implementation of Stickel protocol, various attempts have been made to create a secure variant of such implementation. Some of these attempts used a special class of commuting matrices resembling tropical circulants, and they have been proposed with claims of resilience against the Kotov-Ushakov attack, and even being potential post-quantum candidates. This paper, however, reveals that a form of the Kotov-Ushakov attack remains applicable and, moreover, there are heuristic implementations of that attack which have a polynomial time complexity and show an overwhelmingly good success rate.
References:
[1] Ahmed, K., Pal, S., Mohan, R.: A review of the tropical approach in cryptography. Cryptologia 47 (2023), 1, 63-87. DOI
[2] Amutha, B., Perumal, R.: Public key exchange protocols based on tropical lower circulant and anti circulant matrices. AIMS Math. 8 (2023), 7, 17307-17334. DOI | MR 4601583
[3] Buchinskiy, I., Kotov, M., Treier, A.: Analysis of four protocols based on tropical circulant matrices. Cryptology ePrint Archive, Paper 2023/1707, 2023.
[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, London 2010. MR 2681232 | Zbl 1202.15032
[5] Durcheva, M. I.: TrES: Tropical encryption scheme based on double key exchange. Eur. J. Inf. Tech. Comp. Sci. 2 (2022), 4. DOI
[6] Gavalec, M.: Periodicity in Extremal Algebras. Gaudeamus, Hradec Králové 2004.
[7] Grigoriev, D., Shpilrain, V.: Tropical cryptography. Commun. Algebra 42 (2013), 2624-2632. DOI | MR 3169729
[8] Grigoriev, D., Shpilrain, V.: Tropical cryptography ii: Extensions by homomorphisms. Commun. Algebra 47 (2019), 10, 4224-4229. DOI | MR 3976001
[9] Huang, H., Li, C., Deng, L.: Public-key cryptography based on tropical circular matrices. Appl. Sci. 12 (2022), 15. DOI
[10] Isaac, S., Kahrobaei, D.: A closer look at the tropical cryptography. Int. J. Computer Math.: Computer Systems Theory 6 (2021), 2, 137-142. DOI | MR 4262938
[11] Kotov, M., Ushakov, A.: Analysis of a key exchange protocol based on tropical matrix algebra. J. Math. Cryptology 12 (2018), 3, 137-141. DOI | MR 3849682
[12] Litvinov, G. L., Rodionov, A. Ya., Sergeev, S. N., Sobolevski, A. N.: Universal algorithms for solving the matrix bellman equations over semirings. Soft Computing 17 (2013), 10, 1767-1785. DOI
[13] Mach, M.: Cryptography Based on Semirings. Master's Thesis, Univerzita Karlova, Matematicko-fyzikální fakulta, Prague 2019.
[14] Muanalifah, A., Sergeev, S.: Modifying the tropical version of {S}tickel’s key exchange protocol. Appl. Math. 65 (2020), 727-753. DOI | MR 4191366
[15] Muanalifah, A., Sergeev, S.: On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product. Commun. Algebra 50 (2022), 2, 861-879. DOI | MR 4375546
[16] Plávka, J.: On eigenproblem for circulant matrices in max algebra. Optimization 50 (2001), 477-483. DOI | MR 1892917
[17] Plávka, J., Sergeev, S.: Reachability of eigenspaces for interval circulant matrices in max-algebra. Linear Algebra Appl. 550 (2018), 59-86. DOI | MR 3786247
[18] Ponmaheshkumar, A., Perumal, R.: Toeplitz matrices based key exchange protocol for the internet of things. Int. J. Inform. Technol. 65 (2023), 11. DOI
Search
Partner of
