Paper 2026/237

Exploiting SNOVA’s Structure in the Wedge Product Attack

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, where Unbalanced Oil and Vinegar (UOV) is a leading example. UOV has been extensively studied since its introduction by Kipnis, Patarin, and Goubin at Eurocrypt 1999, and it has remained secure. The signature sizes the scheme allows are quite small; however the key sizes are very large, making the scheme less attractive for some common protocols. To remediate this deficiency, some schemes---such as MAYO, QRUOV, and SNOVA---add a structure to reduce the size of the public key. These multivariate schemes are candidates that made it to the third round of the National Institute of Standards and Technology's Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. In this work, we revisit a recently proposed algebraic attack by Ran at Eurocrypt 2026 on UOV and extend this approach to a new attack on SNOVA by exploiting its block-ring structure. In addition to improving the attack complexity, the exploitation of the block-ring structure rules out spurious solutions, which prevents the generic version of Ran's attack from applying to SNOVA. This attack breaks 6 of the 11 second-round SNOVA parameter sets and improves on the previous best result for an additional 2 sets; it is significantly more effective against larger $\ell$ in comparison to several earlier attacks. For example, for SNOVA-V with parameters $(v,o,\ell) = (29,6,5)$, the estimated security drops to $181$ bits, compared to $310$ bits for the previous best known attack.