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. This survey is based on a talk given at the Omsk Algebra Seminar in 2025.

Cite: Buchinskiy I. , Kotov M. , Treier A.
Problems in algebra inspired by tropical cryptography
Asian-European Journal of Mathematics. 2026. 2630001 :1-28. DOI: 10.1142/s1793557126300010 OpenAlex

Dates:

Submitted:	May 19, 2026
Accepted:	Sep 13, 2026
Published online:	Oct 13, 2026

Identifiers:

≡ OpenAlex:

W7165047039

Altmetrics: