Exploiting SNOVA's Structure in the Wedge Product Attack

Published

September 24, 2025

Author(s)

Thai Hung LE, Maxime Bros, Jacob Lichtinger, Brice Minaud, Ray Perlner, Daniel Smith-Tone, Cristian Valenzuela

Abstract

Post-quantum cryptography (PQC) aims to develop cryptographic schemes secure against quantum adversaries. One promising class of digital signature schemes is based on multivariate quadratic equations, with Unbalanced Oil and Vinegar (UOV) being a leading example. UOV has been extensively studied since its introduction in 1999 (Kipnis, Patarin, Goubin, Eurocrypt 1999), and it has remained secure. It offers very small signatures but suffers from very large public keys; to remediate this, some schemes, such as MAYO, QR-UOV, SNOVA, add a structure to reduce the size of the public key. These four multivariate schemes are candidates that made it to the Second Round of NIST PQC Additional Call for Post-Quantum Signature schemes. In this work, we revisit a new algebraic attack proposed recently by Lars Ran at Eurocrypt 2025 Rump Session by showing how to exploit the block–ring structure of SNOVA to reduce the cost of the attack. Our improved attack, which relies on a conjecture (work in progress to confirm it experimentally), improves significantly on the previous one for almost all SNOVA parameters; for instance bringing the security of SNOVA-I ($(v,o,\ell)=(24,5,4)$) down to $94$ bits of security when the previous attack was at $160$ bits. A consequence of our attack is that all parameters of SNOVA updated for Round 2 of NIST Standardization are now broken.

Conference Dates

September 24-26, 2025

Conference Location

Gaithersburg, MD, US

Conference Title

6th PQC Standardization Conference

Pub Type

Conferences

Download Paper

Local Download

Keywords

post-quantum cryptography, UOV, SNOVA, algebraic attack

Citation

LE, T. , Bros, M. , Lichtinger, J. , Minaud, B. , Perlner, R. , Smith-Tone, D. and Valenzuela, C. (2025), Exploiting SNOVA's Structure in the Wedge Product Attack, 6th PQC Standardization Conference, Gaithersburg, MD, US, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=960297 (Accessed February 20, 2026)