| Title:
|
Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices (English) |
| Author:
|
Alhussaini, Sulaiman |
| Author:
|
Collett, Craig |
| Author:
|
Sergeev, Sergeĭ |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
60 |
| Issue:
|
5 |
| Year:
|
2024 |
| Pages:
|
603-623 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
public-key cryptography |
| Keyword:
|
key exchange protocol |
| Keyword:
|
cryptographic attack |
| Keyword:
|
tropical cryptography |
| MSC:
|
15A80 |
| MSC:
|
94A60 |
| DOI:
|
10.14736/kyb-2024-5-0603 |
| . |
| Date available:
|
2025-01-02T15:45:30Z |
| Last updated:
|
2025-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152717 |
| . |
| Reference:
|
[1] Ahmed, K., Pal, S., Mohan, R.: A review of the tropical approach in cryptography..Cryptologia 47 (2023), 1, 63-87. |
| Reference:
|
[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. MR 4601583, |
| Reference:
|
[3] Buchinskiy, I., Kotov, M., Treier, A.: Analysis of four protocols based on tropical circulant matrices..Cryptology ePrint Archive, Paper 2023/1707, 2023. |
| Reference:
|
[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms..Springer, London 2010. Zbl 1202.15032, MR 2681232 |
| Reference:
|
[5] Durcheva, M. I.: TrES: Tropical encryption scheme based on double key exchange..Eur. J. Inf. Tech. Comp. Sci. 2 (2022), 4. |
| Reference:
|
[6] Gavalec, M.: Periodicity in Extremal Algebras..Gaudeamus, Hradec Králové 2004. |
| Reference:
|
[7] Grigoriev, D., Shpilrain, V.: Tropical cryptography..Commun. Algebra 42 (2013), 2624-2632. MR 3169729, |
| Reference:
|
[8] Grigoriev, D., Shpilrain, V.: Tropical cryptography ii: Extensions by homomorphisms..Commun. Algebra 47 (2019), 10, 4224-4229. MR 3976001, |
| Reference:
|
[9] Huang, H., Li, C., Deng, L.: Public-key cryptography based on tropical circular matrices..Appl. Sci. 12 (2022), 15. |
| Reference:
|
[10] Isaac, S., Kahrobaei, D.: A closer look at the tropical cryptography..Int. J. Computer Math.: Computer Systems Theory 6 (2021), 2, 137-142. MR 4262938, |
| Reference:
|
[11] Kotov, M., Ushakov, A.: Analysis of a key exchange protocol based on tropical matrix algebra..J. Math. Cryptology 12 (2018), 3, 137-141. MR 3849682, |
| Reference:
|
[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. |
| Reference:
|
[13] Mach, M.: Cryptography Based on Semirings..Master's Thesis, Univerzita Karlova, Matematicko-fyzikální fakulta, Prague 2019. |
| Reference:
|
[14] Muanalifah, A., Sergeev, S.: Modifying the tropical version of {S}tickel’s key exchange protocol..Appl. Math. 65 (2020), 727-753. MR 4191366, |
| Reference:
|
[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. MR 4375546, |
| Reference:
|
[16] Plávka, J.: On eigenproblem for circulant matrices in max algebra..Optimization 50 (2001), 477-483. MR 1892917, |
| Reference:
|
[17] Plávka, J., Sergeev, S.: Reachability of eigenspaces for interval circulant matrices in max-algebra..Linear Algebra Appl. 550 (2018), 59-86. MR 3786247, |
| Reference:
|
[18] Ponmaheshkumar, A., Perumal, R.: Toeplitz matrices based key exchange protocol for the internet of things..Int. J. Inform. Technol. 65 (2023), 11. |
| . |
