Institute of Mathematics of the Czech Academy of Sciences

Given that the tropical Stickel protocol and its variants are all vulnerable to the generalized Kotov–Ushakov attack, we suggest employing the max-min semiring and, more generally, max- T semiring where the multiplication is based on a T -norm, as a framework to implement the Stickel protocol. While the Stickel protocol over max-min semiring or max- T semiring remains susceptible to a form of Kotov–Ushakov attack, we demonstrate that it exhibits significantly increased resistance against this attack when compared to the tropical (max-plus) implementation.

Known attacks on the tropical implementation of Stickel protocol involve finding minimal covers for a certain covering problem, and this leads to an exponential growth in the worst case time required to recover the secret key as the used polynomial degree increases. The computational inefficiency of this attack is also observed in practice, unless the number of explored covers is limited, on the expense of the success rate of the attack. Consequently, it can be argued that Alice and Bob can still repel these attacks on tropical Stickel protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some other semirings with idempotent addition (such as the max–min or digital semiring). In this paper, we propose alternative methods to attack the Stickel protocols that avoid solving the covering problem. These methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain heuristic global optimization techniques. We also include a number of numerical experiments to analyze the success rate and the time required to execute the suggested attacks in practice.

We introduce a notion of dimension of max–min convex sets, following the approach of tropical convexity. We introduce a max–min analogue of the tropical rank of a matrix and show that it is equal to the dimension of the associated polytope. We describe the relation between this rank and the notion of strong regularity in max–min algebra, which is traditionally defined in terms of unique solvability of linear systems and the trapezoidal property