Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A Total Break of the Scrap Digital Signature Scheme

Published

Author(s)

Daniel Smith-Tone

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.
Citation
Cryptology Eprint Archive
Volume
2023

Keywords

Multivariate Cryptography, Scrap, Cryptanalysis, Gr\"obner basis

Citation

Smith-Tone, D. (2023), A Total Break of the Scrap Digital Signature Scheme, Cryptology Eprint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=956292, https://ia.cr/2023/1481 (Accessed June 23, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created October 2, 2023, Updated October 13, 2023