Paper 2026/1256 Original: eprint.iacr.org/2026/1256 ↗

Problems in algebra inspired by tropical cryptography

Abstract

In 2011, Grigoriev and Shpilrain proposed using tropical algebraic structures in cryptography. In recent years, numerous protocols based on tropical and related structures have been introduced, as well as many attacks on some of these protocols. This direction of research is now known as tropical cryptography. As a result of the efforts both to design secure schemes and to analyze their vulnerabilities, many purely algebraic and computational problems have emerged. In this paper, we give an overview of several results and open questions in this area. We discuss the complexity of solving certain classes of systems of equations over tropical and similar structures, as well as algorithms and approaches for solving such systems. We also present results on the asymptotic density of satisfiable systems of equations of special forms over tropical algebras. Furthermore, we discuss the discrete logarithm problem, the two-sided discrete logarithm problem, the knapsack problem, and the subset sum problem over tropical matrix structures. We consider a generalization of marginal sets for tropical semirings and semigroups. We also explore different classes of pairwise commuting matrices.