Paper 2025/1822 Original: eprint.iacr.org/2025/1822 ↗
Solving one-sided linear systems over symmetrized and supertropical semirings
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.
- History
- 2026-02-20: last updated
- 2025-10-03: published
- Short URL
- https://ia.cr/2025/1822
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}