Paper 2026/387
A Comprehensive Break of the Tropical Matrix-Based Signature Scheme
, Department of Mathematics, Shri Vyankatesh Arts, Commerce and Science College, Deulgaon Raja, Buldhana, 443204, Maharashtra, India., School of Mathematical Sciences, K.B.C. North Maharashtra University, Umavi Nagar, Jalgaon, 425001, Maharashtra, India.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.
- Keywords
- digital signaturetropical semiringcryptanalysismatrix factorizationmalleabilitySMT solving
- Contact author(s)
-
sjchavhanmath17 @ gmail com
drsrchaudhari @ nmu ac in - History
- 2026-03-15: revised
- 2026-02-25: received
- See all versions
- Short URL
- https://ia.cr/2026/387
- License
-
CC BY
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}
}
