Paper 2026/387 Original: eprint.iacr.org/2026/387 ↗
A Comprehensive Break of the Tropical Matrix-Based Signature Scheme
Abstract
In the recent preprint [GMS26], Grigoriev, Monico and Shpilrain proposed a digital signature protocol based on matrices over the tropical integer semiring. we show that the scheme can be completely broken. We present a chosen‑hash forgery, a malleability attack that breaks strong unforgeability, and an SMT‑based key recovery attack demonstrating that a single valid signature together with the public key suffices to recover a full private key in within one second for the recommended parameters. Our attacks exploit algebraic properties of the signing equations rather than the claimed NP‑hard problem. Independent work by Sferlazza concurrently identified related vulnerabilities.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2026-03-15: last updated
- 2026-02-25: published
- Short URL
- https://ia.cr/2026/387
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/387,
author = {Sopan Chavhan and Shrikant Chaudhari},
title = {A Comprehensive Break of the Tropical Matrix-Based Signature Scheme},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/387},
year = {2026},
url = {https://eprint.iacr.org/2026/387}
}