Paper 2024/1770

Improved Attacks for SNOVA by Exploiting Stability under a Group Action

Abstract

SNOVA is a post-quantum digital signature scheme based on multivariate polynomials. It is a first-round candidate in an ongoing NIST standardization process for post-quantum signatures, where it stands out for its efficiency and compactness. Since its initial submission, there have been several improvements to its security analysis, both on key recovery and forgery attacks. All these works reduce to solving a structured system of quadratic polynomials, which we refer to as SNOVA system. In this work, we propose a polynomial solving algorithm tailored for SNOVA systems, which exploits the stability of the system under the action of a commutative group of matrices. This new algorithm reduces the complexity to solve SNOVA systems, over generic ones. We show how to adapt the reconciliation and direct attacks in order to profit from the new algorithm. Consequently, we improve the reconciliation attack for all SNOVA parameter sets with speedup factors ranging between $2^3$ and $2^{22}$. Our algorithm also reduces the complexity of the direct attack for several parameter sets. It is particularly effective for the parameters that give the best performance to SNOVA $(l=4)$, and which were not taken below NIST's security threshold by previous attacks. Our attack brings these parameter sets $(l=4)$ below that threshold with speedup factors between $2^{33}$ and $2^{52}$, over the state-of-the-art.