More forging (and patching) of tropical signatures

Daniel R. L. Brown; Chris Monico

Paper 2023/1837

More forging (and patching) of tropical signatures

Daniel R. L. Brown, BlackBerry

Chris Monico, Texas Tech University

Abstract

Panny [3] described how to forge the “tropical signatures” proposed by Chen, Grigoriev and Shpilrain [1]. (These signatures are loosely related to the NP-complete problem of factoring tropical polynomials). We describe more methods to forge these tropical signatures. We also describe some patches that thwart all but one of these forgery methods (which we summarize as re-hashing an honest signature).

Note: Typographical corrections.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: forgery signature tropical
Contact author(s): danibrown @ blackberry com
c monico @ ttu edu
History: 2023-12-21: revised; 2023-11-29: received; See all versions
Short URL: https://ia.cr/2023/1837
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1837,
      author = {Daniel R. L. Brown and Chris Monico},
      title = {More forging (and patching) of tropical signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1837},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1837}},
      url = {https://eprint.iacr.org/2023/1837}
}