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 in 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, and 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 the National Institute of Standards and Technology PQC Additional Call for Post-Quantum Signature schemes. In this work, we revisit a recently proposed algebraic attack by Ran 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, our exploitation of the block-ring structure rules out spurious solutions, which prevents generic version of Ran's attack from applying to SNOVA. Our attack breaks 6 of the 11 currently proposed 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.