Solving one-sided linear systems over symmetrized and supertropical semirings

Sulaiman Alhussaini; Serge˘ı Sergeev

Paper 2025/1822

Solving one-sided linear systems over symmetrized and supertropical semirings

Sulaiman Alhussaini, University of Birmingham

Serge˘ı Sergeev

, University of Birmingham

Abstract

One-sided linear systems of the form ``$Ax=b$'' are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: public key cryptography key exchange protocol cryptographic attack
Contact author(s): saa399 @ student bham ac uk
s sergeev @ bham ac uk
History: 2026-02-20: revised; 2025-10-03: received; See all versions
Short URL: https://ia.cr/2025/1822
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1822,
      author = {Sulaiman Alhussaini and Serge˘ı Sergeev},
      title = {Solving one-sided linear systems over symmetrized and supertropical semirings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1822},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1822}
}