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
cryptanalysistropical algebradigital signaturesfactorization
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1748,
      author = {Lorenz Panny},
      title = {Forging tropical signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1748},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1748}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.