Geodesic
Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices
Kybernetika, Tome 60 (2024) no. 5, pp. 603-623
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2024-5-0603
Classification : 15A80, 94A60
Keywords: public-key cryptography; key exchange protocol; cryptographic attack; tropical cryptography 
@article{10_14736_kyb_2024_5_0603,
     author = {Alhussaini, Sulaiman and Collett, Craig and Sergeev, Serge\u{i}},
     title = {Generalized {Kotov-Ushakov} attack on tropical {Stickel} protocol based on modified tropical circulant matrices},
     journal = {Kybernetika},
     pages = {603--623},
     year = {2024},
     volume = {60},
     number = {5},
     doi = {10.14736/kyb-2024-5-0603},
     mrnumber = {4848303},
     zbl = {07980814},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-5-0603/}
}
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
SP  - 603
EP  - 623
VL  - 60
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-5-0603/
DO  - 10.14736/kyb-2024-5-0603
LA  - en
ID  - 10_14736_kyb_2024_5_0603
ER  - 
%0 Journal Article
%A Alhussaini, Sulaiman
%A Collett, Craig
%A Sergeev, Sergeĭ
%T Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices
%J Kybernetika
%D 2024
%P 603-623
%V 60
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-5-0603/
%R 10.14736/kyb-2024-5-0603
%G en
%F 10_14736_kyb_2024_5_0603
Alhussaini, Sulaiman; Collett, Craig; Sergeev, Sergeĭ. Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices. Kybernetika, Tome 60 (2024) no. 5, pp. 603-623. doi: 10.14736/kyb-2024-5-0603

[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

[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 | Zbl

[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

[8] Grigoriev, D., Shpilrain, V.: Tropical cryptography ii: Extensions by homomorphisms. Commun. Algebra 47 (2019), 10, 4224-4229. | DOI | MR

[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

[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

[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

[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

[16] Plávka, J.: On eigenproblem for circulant matrices in max algebra. Optimization 50 (2001), 477-483. | DOI | MR

[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

[18] Ponmaheshkumar, A., Perumal, R.: Toeplitz matrices based key exchange protocol for the internet of things. Int. J. Inform. Technol. 65 (2023), 11. | DOI

Cité par Sources :