Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices

Sulaiman Alhussaini; Craig Collett; Sergeĭ Sergeev

Kybernetika (2024)

  • Volume: 60, Issue: 5, page 603-623
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Alhussaini, Sulaiman, Collett, Craig, and Sergeev, Sergeĭ. "Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices." Kybernetika 60.5 (2024): 603-623. <http://eudml.org/doc/299704>.

@article{Alhussaini2024,
abstract = {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.},
author = {Alhussaini, Sulaiman, Collett, Craig, Sergeev, Sergeĭ},
journal = {Kybernetika},
keywords = {public-key cryptography; key exchange protocol; cryptographic attack; tropical cryptography},
language = {eng},
number = {5},
pages = {603-623},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices},
url = {http://eudml.org/doc/299704},
volume = {60},
year = {2024},
}

TY - JOUR
AU - Alhussaini, Sulaiman
AU - Collett, Craig
AU - Sergeev, Sergeĭ
TI - Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices
JO - Kybernetika
PY - 2024
PB - Institute of Information Theory and Automation AS CR
VL - 60
IS - 5
SP - 603
EP - 623
AB - 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.
LA - eng
KW - public-key cryptography; key exchange protocol; cryptographic attack; tropical cryptography
UR - http://eudml.org/doc/299704
ER -

References

top
  1. Ahmed, K., Pal, S., Mohan, R., , Cryptologia 47 (2023), 1, 63-87. DOI
  2. Amutha, B., Perumal, R., , AIMS Math. 8 (2023), 7, 17307-17334. MR4601583DOI
  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. Zbl1202.15032MR2681232
  5. Durcheva, M. I., , 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., , Commun. Algebra 42 (2013), 2624-2632. MR3169729DOI
  8. Grigoriev, D., Shpilrain, V., , Commun. Algebra 47 (2019), 10, 4224-4229. MR3976001DOI
  9. Huang, H., Li, C., Deng, L., , Appl. Sci. 12 (2022), 15. DOI
  10. Isaac, S., Kahrobaei, D., , Int. J. Computer Math.: Computer Systems Theory 6 (2021), 2, 137-142. MR4262938DOI
  11. Kotov, M., Ushakov, A., , J. Math. Cryptology 12 (2018), 3, 137-141. MR3849682DOI
  12. Litvinov, G. L., Rodionov, A. Ya., Sergeev, S. N., Sobolevski, A. N., , 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., , Appl. Math. 65 (2020), 727-753. MR4191366DOI
  15. Muanalifah, A., Sergeev, S., , Commun. Algebra 50 (2022), 2, 861-879. MR4375546DOI
  16. Plávka, J., , Optimization 50 (2001), 477-483. MR1892917DOI
  17. Plávka, J., Sergeev, S., , Linear Algebra Appl. 550 (2018), 59-86. MR3786247DOI
  18. Ponmaheshkumar, A., Perumal, R., , Int. J. Inform. Technol. 65 (2023), 11. DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.