Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices
Sulaiman Alhussaini, Craig Collett, Sergeĭ Sergeev · Kybernetika · 2024
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.