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, ℓ) = (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.
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...
See full 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, ℓ) = (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.
Hide full abstract
