Forging tropical signatures

Lorenz Panny

Paper 2023/1748

Forging tropical signatures

Lorenz Panny, Technische Universität München

Abstract

A recent preprint [ePrint 2023/1475] 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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. AAC'24
Keywords: cryptanalysis tropical algebra digital signatures factorization
Contact author(s): lorenz @ yx7 cc
History: 2024-01-13: revised; 2023-11-11: received; See all versions
Short URL: https://ia.cr/2023/1748
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1748,
      author = {Lorenz Panny},
      title = {Forging tropical signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1748},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1748}},
      url = {https://eprint.iacr.org/2023/1748}
}