Generalized Kotov-Ushakov Attack on Tropical Stickel Protocol Based on Modified Tropical Circulant Matrices

Sulaiman Alhussaini; Craig Collett; Serge˘ı Sergeev

Paper 2023/1904

Generalized Kotov-Ushakov Attack on Tropical Stickel Protocol Based on Modified Tropical Circulant Matrices

Sulaiman Alhussaini, University of Birmingham

Craig Collett, University of Birmingham

Serge˘ı Sergeev

, University of Birmingham

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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: public-key cryptography key exchange protocol cryptographic attack tropical cryptography
Contact author(s): s alhussaini @ bham ac uk
CRC957 @ student bham ac uk
s sergeev @ bham ac uk
History: 2024-06-27: last of 2 revisions; 2023-12-11: received; See all versions
Short URL: https://ia.cr/2023/1904
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1904,
      author = {Sulaiman Alhussaini and Craig Collett and Serge˘ı Sergeev},
      title = {Generalized Kotov-Ushakov Attack on Tropical Stickel Protocol Based on Modified Tropical Circulant Matrices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1904},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1904}
}