Forging Tropical Signatures

A recent preprint  [3] suggests the use of polynomials over a tropical algebra to construct a digital signature scheme “based on” the problem of factoring such polynomials, which is known to be NP-hard. This short note presents two very efficient forgery attacks on the scheme, bypassing the need to factorize tropical polynomials and thus demonstrating that security in fact rests on a different, empirically easier problem.