A Total Break of the Scrap Digital Signature Scheme

Daniel Smith-Tone

Paper 2023/1481

A Total Break of the Scrap Digital Signature Scheme

Daniel Smith-Tone

, National Institute of Standards and Technology, University of Louisville

Abstract

Recently a completely new post-quantum digital signature scheme was proposed using the so called ``scrap automorphisms''. The structure is inherently multivariate, but differs significantly from most of the multivariate literature in that it relies on sparsity and rings containing zero divisors. In this article, we derive a complete and total break of Scrap, performing a key recovery in not much more time than verifying a signature. We also generalize the result, breaking unrealistic instances of the scheme for which there is no particularly efficient signing algorithm and key sizes are unmanageable.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Multivariate Cryptography Scrap Cryptanalysis Gr\"obner basis
Contact author(s): daniel smith @ nist gov
History: 2023-10-02: approved; 2023-09-27: received; See all versions
Short URL: https://ia.cr/2023/1481
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1481,
      author = {Daniel Smith-Tone},
      title = {A Total Break of the Scrap Digital Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1481},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1481}},
      url = {https://eprint.iacr.org/2023/1481}
}